diff options
Diffstat (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h')
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 137 |
1 files changed, 59 insertions, 78 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 95a6d090..247630cc 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -38,7 +38,6 @@ #include <functional> // for greater<> namespace Gudhi { - /** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ @@ -73,7 +72,6 @@ namespace Gudhi { * \copyright GNU General Public License v3. * @{ */ - /** * \brief Simplex Tree data structure for representing simplicial complexes. * @@ -190,12 +188,12 @@ class Simplex_tree { /** \name Range and iterator methods * @{ */ - /** \brief Returns a range over the vertices of the simplicial complex. + /** \brief Returns a range over the vertices of the simplicial complex. * The order is increasing according to < on Vertex_handles.*/ Complex_vertex_range complex_vertex_range() { return Complex_vertex_range( - boost::make_transform_iterator(root_.members_.begin(), return_first()), - boost::make_transform_iterator(root_.members_.end(), return_first())); + boost::make_transform_iterator(root_.members_.begin(), return_first()), + boost::make_transform_iterator(root_.members_.end(), return_first())); } /** \brief Returns a range over the simplices of the simplicial complex. @@ -286,11 +284,12 @@ class Simplex_tree { /** \brief Constructs an empty simplex tree. */ Simplex_tree() : null_vertex_(-1), - threshold_(0), - num_simplices_(0), - root_(NULL, null_vertex_), - filtration_vect_(), - dimension_(-1) { } + threshold_(0), + num_simplices_(0), + root_(NULL, null_vertex_), + filtration_vect_(), + dimension_(-1) { + } /** \brief Destructor; deallocates the whole tree structure. */ ~Simplex_tree() { @@ -316,21 +315,21 @@ class Simplex_tree { /** \brief Returns the key associated to a simplex. * * The filtration must be initialized. */ - Simplex_key key(Simplex_handle sh) { + static Simplex_key key(Simplex_handle sh) { return sh->second.key(); } /** \brief Returns the simplex associated to a key. * * The filtration must be initialized. */ - Simplex_handle simplex(Simplex_key key) { + Simplex_handle simplex(Simplex_key key) const { return filtration_vect_[key]; } /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ - Filtration_value filtration(Simplex_handle sh) const { + static Filtration_value filtration(Simplex_handle sh) { if (sh != null_simplex()) { return sh->second.filtration(); } else { @@ -338,6 +337,15 @@ class Simplex_tree { } } + /** \brief Sets the filtration value of a simplex. + * + * No action if called on the null_simplex*/ + void assign_filtration(Simplex_handle sh, Filtration_value fv) { + if (sh != null_simplex()) { + sh->second.assign_filtration(fv); + } + } + /** \brief Returns an upper bound of the filtration values of the simplices. */ Filtration_value filtration() const { return threshold_; @@ -347,13 +355,13 @@ class Simplex_tree { * associated to the simplices in the simplicial complex. * * One can call filtration(null_simplex()). */ - Simplex_handle null_simplex() const { + static Simplex_handle null_simplex() { return Dictionary_it(NULL); } /** \brief Returns a key different for all keys associated to the * simplices of the simplicial complex. */ - Simplex_key null_key() const { + static Simplex_key null_key() { return -1; } @@ -399,7 +407,6 @@ class Simplex_tree { return (sh->second.children()->parent() == sh->first); } - public: /** \brief Given a range of Vertex_handles, returns the Simplex_handle * of the simplex in the simplicial complex containing the corresponding * vertices. Return null_simplex() if the simplex is not in the complex. @@ -436,7 +443,6 @@ class Simplex_tree { Simplex_handle find_vertex(Vertex_handle v) { return root_.members_.begin() + v; } - //{ return root_.members_.find(v); } /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. * @@ -463,7 +469,7 @@ class Simplex_tree { * .end() return random access iterators, with 'value_type' Vertex_handle. */ template<class RandomAccessVertexRange> std::pair<Simplex_handle, bool> insert_simplex(RandomAccessVertexRange & simplex, - Filtration_value filtration) { + Filtration_value filtration) { if (simplex.empty()) { return std::pair<Simplex_handle, bool>(null_simplex(), true); } @@ -500,10 +506,11 @@ class Simplex_tree { * * @param[in] Nsimplex range of Vertex_handles, representing the vertices of the new N-simplex * @param[in] filtration the filtration value assigned to the new N-simplex. - */ + */ template<class RandomAccessVertexRange> - void insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, - Filtration_value filtration = 0.0) { + std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, + Filtration_value filtration = 0.0) { + std::pair<Simplex_handle, bool> returned; if (Nsimplex.size() > 1) { for (unsigned int NIndex = 0; NIndex < Nsimplex.size(); NIndex++) { // insert N (N-1)-Simplex @@ -513,22 +520,23 @@ class Simplex_tree { NsimplexMinusOne.push_back(Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); } // (N-1)-Simplex recursive call - insert_simplex_and_subfaces(NsimplexMinusOne, filtration); + returned = insert_simplex_and_subfaces(NsimplexMinusOne, filtration); } // N-Simplex insert - std::pair<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + returned = insert_simplex(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } } else if (Nsimplex.size() == 1) { // 1-Simplex insert - End of recursivity - std::pair<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + returned = insert_simplex(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } } else { // Nothing to insert - empty vector } + return returned; } /** \brief Assign a value 'key' to the key of the simplex @@ -543,8 +551,8 @@ class Simplex_tree { * optimized version of the boundary computation. */ std::pair<Simplex_handle, Simplex_handle> endpoints(Simplex_handle sh) { return std::pair<Simplex_handle, Simplex_handle>( - root_.members_.find(sh->first), - root_.members_.find(self_siblings(sh)->parent())); + root_.members_.find(sh->first), + root_.members_.find(self_siblings(sh)->parent())); } /** Returns the Siblings containing a simplex.*/ @@ -555,23 +563,13 @@ class Simplex_tree { return sh->second.children(); } - // void display_simplex(Simplex_handle sh) - // { - // std::cout << " " << "[" << filtration(sh) << "] "; - // for( auto vertex : simplex_vertex_range(sh) ) - // { std::cout << vertex << " "; } - // } - - // void print(Simplex_handle sh, std::ostream& os = std::cout) - // { for(auto v : simplex_vertex_range(sh)) {os << v << " ";} - // os << std::endl; } - public: /** Returns a pointer to the root nodes of the simplex tree. */ Siblings * root() { return &root_; } + public: /** Set an upper bound for the filtration values. */ void set_filtration(Filtration_value fil) { threshold_ = fil; @@ -606,10 +604,8 @@ class Simplex_tree { void initialize_filtration() { filtration_vect_.clear(); filtration_vect_.reserve(num_simplices()); - for (auto cpx_it = complex_simplex_range().begin(); - cpx_it != complex_simplex_range().end(); ++cpx_it) { - filtration_vect_.push_back(*cpx_it); - } + for (Simplex_handle sh : complex_simplex_range()) + filtration_vect_.push_back(sh); // the stable sort ensures the ordering heuristic std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), @@ -787,15 +783,15 @@ class Simplex_tree { typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it, v_it_end; for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end; - ++v_it) { + ++v_it) { root_.members_.emplace_hint( - root_.members_.end(), *v_it, - Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); + root_.members_.end(), *v_it, + Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); } typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it, e_it_end; for (std::tie(e_it, e_it_end) = boost::edges(skel_graph); e_it != e_it_end; - ++e_it) { + ++e_it) { auto u = source(*e_it, skel_graph); auto v = target(*e_it, skel_graph); if (u < v) { @@ -806,9 +802,9 @@ class Simplex_tree { } sh->second.children()->members().emplace( - v, - Node(sh->second.children(), - boost::get(edge_filtration_t(), skel_graph, *e_it))); + v, + Node(sh->second.children(), + boost::get(edge_filtration_t(), skel_graph, *e_it))); } } } @@ -827,7 +823,7 @@ class Simplex_tree { void expansion(int max_dim) { dimension_ = max_dim; for (Dictionary_it root_it = root_.members_.begin(); - root_it != root_.members_.end(); ++root_it) { + root_it != root_.members_.end(); ++root_it) { if (has_children(root_it)) { siblings_expansion(root_it->second.children(), max_dim - 1); } @@ -836,9 +832,10 @@ class Simplex_tree { } private: + /** \brief Recursive expansion of the simplex tree.*/ void siblings_expansion(Siblings * siblings, // must contain elements - int k) { + int k) { if (dimension_ > k) { dimension_ = k; } @@ -862,8 +859,8 @@ class Simplex_tree { if (inter.size() != 0) { this->num_simplices_ += inter.size(); Siblings * new_sib = new Siblings(siblings, // oncles - s_h->first, // parent - inter); // boost::container::ordered_unique_range_t + s_h->first, // parent + inter); // boost::container::ordered_unique_range_t inter.clear(); s_h->second.assign_children(new_sib); siblings_expansion(new_sib, k - 1); @@ -881,40 +878,25 @@ class Simplex_tree { static void intersection(std::vector<std::pair<Vertex_handle, Node> >& intersection, Dictionary_it begin1, Dictionary_it end1, Dictionary_it begin2, Dictionary_it end2, - Filtration_value filtration) { + Filtration_value filtration_) { if (begin1 == end1 || begin2 == end2) return; // ----->> while (true) { if (begin1->first == begin2->first) { - intersection.push_back(std::pair<Vertex_handle, Node>(begin1->first, - Node(NULL, - maximum(begin1->second.filtration(), - begin2->second.filtration(), filtration)))); - ++begin1; - ++begin2; - if (begin1 == end1 || begin2 == end2) + Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_}); + intersection.emplace_back(begin1->first, Node(NULL, filt)); + if (++begin1 == end1 || ++begin2 == end2) + return; // ----->> + } else if (begin1->first < begin2->first) { + if (++begin1 == end1) + return; + } else /* begin1->first > begin2->first */ { + if (++begin2 == end2) return; // ----->> - } else { - if (begin1->first < begin2->first) { - ++begin1; - if (begin1 == end1) - return; - } else { - ++begin2; - if (begin2 == end2) - return; // ----->> - } } } } - /** Maximum over 3 values.*/ - static Filtration_value maximum(Filtration_value a, Filtration_value b, - Filtration_value c) { - Filtration_value max = (a < b) ? b : a; - return ((max < c) ? c : max); - } - public: /** \brief Write the hasse diagram of the simplicial complex in os. * @@ -948,7 +930,6 @@ class Simplex_tree { }; // Print a Simplex_tree in os. - template<typename T1, typename T2, typename T3> std::ostream& operator<<(std::ostream & os, Simplex_tree<T1, T2, T3> & st) { for (auto sh : st.filtration_simplex_range()) { |