diff options
Diffstat (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h')
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 188 |
1 files changed, 164 insertions, 24 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 096270ee..b6dc8e13 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -30,24 +30,28 @@ #include <gudhi/reader_utils.h> #include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Debug_utils.h> #include <boost/container/flat_map.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/graph/adjacency_list.hpp> +#include <boost/range/adaptor/reversed.hpp> #ifdef GUDHI_USE_TBB #include <tbb/parallel_sort.h> #endif -#include <algorithm> #include <utility> #include <vector> #include <functional> // for greater<> +#include <stdexcept> +#include <limits> // Inf #include <initializer_list> +#include <algorithm> // for std::max namespace Gudhi { - /** \defgroup simplex_tree Filtered Complexes + * \author Clément Maria * * A simplicial complex \f$\mathbf{K}\f$ * on a set of vertices \f$V = \{1, \cdots ,|V|\}\f$ is a collection of simplices @@ -68,16 +72,13 @@ namespace Gudhi { The simplex tree is an efficient and flexible data structure for representing general (filtered) simplicial complexes. The data structure is described in \cite boissonnatmariasimplextreealgorithmica + \image html "Simplex_tree_representation.png" "Simplex tree representation" The second one is the Hasse_complex. The Hasse complex is a data structure representing explicitly all co-dimension 1 incidence relations in a complex. It is consequently faster when accessing the boundary of a simplex, but is less compact and harder to construct from scratch. - - * \author ClĂ©ment Maria - * \version 1.0 - * \date 2014 * \copyright GNU General Public License v3. * @{ */ @@ -85,6 +86,7 @@ namespace Gudhi { struct Simplex_tree_options_full_featured; /** + * \class Simplex_tree Simplex_tree.h gudhi/Simplex_tree.h * \brief Simplex Tree data structure for representing simplicial complexes. * * \details Every simplex \f$[v_0, \cdots ,v_d]\f$ admits a canonical orientation @@ -138,7 +140,8 @@ class Simplex_tree { void assign_key(Simplex_key) { } Simplex_key key() const { assert(false); return -1; } }; - typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base; + typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type + Key_simplex_base; struct Filtration_simplex_base_real { Filtration_simplex_base_real() : filt_(0) {} @@ -304,7 +307,8 @@ class Simplex_tree { * of the simplex. * * @param[in] sh Simplex for which the boundary is computed. */ - Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) { + template<class SimplexHandle> + Boundary_simplex_range boundary_simplex_range(SimplexHandle sh) { return Boundary_simplex_range(Boundary_simplex_iterator(this, sh), Boundary_simplex_iterator(this)); } @@ -445,6 +449,15 @@ class Simplex_tree { } } + /** \brief Sets the filtration value of a simplex. + * \exception std::invalid_argument In debug mode, if sh is a null_simplex. + */ + void assign_filtration(Simplex_handle sh, Filtration_value fv) { + GUDHI_CHECK(sh != null_simplex(), + std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on 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_; @@ -514,9 +527,10 @@ class Simplex_tree { return dimension_; } - /** \brief Returns true iff the node in the simplex tree pointed by + /** \brief Returns true if the node in the simplex tree pointed by * sh has children.*/ - bool has_children(Simplex_handle sh) const { + template<class SimplexHandle> + bool has_children(SimplexHandle sh) const { return (sh->second.children()->parent() == sh->first); } @@ -576,13 +590,25 @@ class Simplex_tree { bool contiguous_vertices() const { if (root_.members_.empty()) return true; if (root_.members_.begin()->first != 0) return false; - if (std::prev(root_.members_.end())->first != root_.members_.size()-1) return false; + if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false; return true; } private: /** \brief Inserts a simplex represented by a vector of vertex. - \warning the vector must be sorted by increasing vertex handle order */ + * @param[in] simplex vector of Vertex_handles, representing the vertices of the new simplex. The vector must be + * sorted by increasing vertex handle order. + * @param[in] filtration the filtration value assigned to the new simplex. + * @return If the new simplex is inserted successfully (i.e. it was not in the + * simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned + * to the new simplex. + * If the insertion fails (the simplex is already there), the bool is set to false. If the insertion + * fails and the simplex already in the complex has a filtration value strictly bigger than 'filtration', + * we assign this simplex with the new value 'filtration', and set the Simplex_handle field of the + * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to + * null_simplex. + * + */ std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex, Filtration_value filtration) { Siblings * curr_sib = &root_; @@ -615,7 +641,7 @@ class Simplex_tree { * * @param[in] simplex range of Vertex_handles, representing the vertices of the new simplex * @param[in] filtration the filtration value assigned to the new simplex. - * The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the + * @return If the new simplex is inserted successfully (i.e. it was not in the * simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned * to the new simplex. * If the insertion fails (the simplex is already there), the bool is set to false. If the insertion @@ -654,7 +680,7 @@ 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. - * The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the + * @return If the new simplex is inserted successfully (i.e. it was not in the * simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned * to the new simplex. * If the insertion fails (the simplex is already there), the bool is set to false. If the insertion @@ -663,7 +689,7 @@ class Simplex_tree { * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to * null_simplex. */ - template<class InputVertexRange=std::initializer_list<Vertex_handle>> + template<class InputVertexRange = std::initializer_list<Vertex_handle>> std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, Filtration_value filtration = 0) { auto first = std::begin(Nsimplex); @@ -717,7 +743,7 @@ class Simplex_tree { } else if (the_simplex.size() == 1) { // When reaching the end of recursivity, vector of simplices shall be empty and filled on back recursive if ((to_be_inserted.size() != 0) || (to_be_propagated.size() != 0)) { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty" << std::endl; + std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty\n"; exit(-1); } std::vector<Vertex_handle> first_simplex(1, the_simplex.back()); @@ -726,7 +752,7 @@ class Simplex_tree { insert_result = insert_vertex_vector(first_simplex, filtration); } else { - std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error" << std::endl; + std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error\n"; exit(-1); } return insert_result; @@ -739,7 +765,6 @@ class Simplex_tree { sh->second.assign_key(key); } - public: /** Returns the two Simplex_handle corresponding to the endpoints of * and edge. sh must point to a 1-dimensional simplex. This is an * optimized version of the boundary computation. */ @@ -749,7 +774,8 @@ class Simplex_tree { } /** Returns the Siblings containing a simplex.*/ - Siblings * self_siblings(Simplex_handle sh) { + template<class SimplexHandle> + Siblings* self_siblings(SimplexHandle sh) { if (sh->second.children()->parent() == sh->first) return sh->second.children()->oncles(); else @@ -798,10 +824,11 @@ class Simplex_tree { * possible. */ #ifdef GUDHI_USE_TBB - tbb::parallel_sort(filtration_vect_, is_before_in_filtration(this)); + std::cout << "TBB is ON !!!" << std::endl; + tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); #else - std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), - is_before_in_filtration(this)); + std::cout << "TBB is OFF..." << std::endl; + std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); #endif } @@ -928,7 +955,7 @@ class Simplex_tree { bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const { // Not using st_->filtration(sh1) because it uselessly tests for null_simplex. if (sh1->second.filtration() != sh2->second.filtration()) { - return sh1->second.filtration() < sh2->second.filtration(); + return sh1->second.filtration() < sh2->second.filtration(); } // is sh1 a proper subface of sh2 return st_->reverse_lexicographic_order(sh1, sh2); @@ -1105,6 +1132,120 @@ class Simplex_tree { } } + public: + /** \brief Browse the simplex tree to ensure the filtration is not decreasing. + * The simplex tree is browsed starting from the root until the leaf, and the filtration values are set with their + * parent value (increased), in case the values are decreasing. + * @return The filtration modification information. + * \post Some simplex tree functions require the filtration to be valid. `make_filtration_non_decreasing()` + * function is not launching `initialize_filtration()` but returns the filtration modification information. If the + * complex has changed , please call `initialize_filtration()` to recompute it. + */ + bool make_filtration_non_decreasing() { + bool modified = false; + // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree + for (auto& simplex : boost::adaptors::reverse(root_.members())) { + if (has_children(&simplex)) { + modified |= rec_make_filtration_non_decreasing(simplex.second.children()); + } + } + return modified; + } + + private: + /** \brief Recursively Browse the simplex tree to ensure the filtration is not decreasing. + * @param[in] sib Siblings to be parsed. + * @return The filtration modification information in order to trigger initialize_filtration. + */ + bool rec_make_filtration_non_decreasing(Siblings * sib) { + bool modified = false; + + // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree + for (auto& simplex : boost::adaptors::reverse(sib->members())) { + // Find the maximum filtration value in the border + Boundary_simplex_range boundary = boundary_simplex_range(&simplex); + Boundary_simplex_iterator max_border = std::max_element(std::begin(boundary), std::end(boundary), + [](Simplex_handle sh1, Simplex_handle sh2) { + return filtration(sh1) < filtration(sh2); + }); + + Filtration_value max_filt_border_value = filtration(*max_border); + if (simplex.second.filtration() < max_filt_border_value) { + // Store the filtration modification information + modified = true; + simplex.second.assign_filtration(max_filt_border_value); + } + if (has_children(&simplex)) { + modified |= rec_make_filtration_non_decreasing(simplex.second.children()); + } + } + // Make the modified information to be traced by upper call + return modified; + } + + public: + /** \brief Prune above filtration value given as parameter. + * @param[in] filtration Maximum threshold value. + * @return The filtration modification information. + * \post Some simplex tree functions require the filtration to be valid. `prune_above_filtration()` + * function is not launching `initialize_filtration()` but returns the filtration modification information. If the + * complex has changed , please call `initialize_filtration()` to recompute it. + */ + bool prune_above_filtration(Filtration_value filtration) { + return rec_prune_above_filtration(root(), filtration); + } + + private: + bool rec_prune_above_filtration(Siblings* sib, Filtration_value filt) { + auto&& list = sib->members(); + auto last = std::remove_if(list.begin(), list.end(), [=](Dit_value_t& simplex) { + if (simplex.second.filtration() <= filt) return false; + if (has_children(&simplex)) rec_delete(simplex.second.children()); + return true; + }); + + bool modified = (last != list.end()); + if (last == list.begin() && sib != root()) { + // Removing the whole siblings, parent becomes a leaf. + sib->oncles()->members()[sib->parent()].assign_children(sib->oncles()); + delete sib; + return true; + } else { + // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones. + list.erase(last, list.end()); + for (auto&& simplex : list) + if (has_children(&simplex)) + modified |= rec_prune_above_filtration(simplex.second.children(), filt); + } + return modified; + } + + public: + /** \brief Remove a maximal simplex. + * @param[in] sh Simplex handle on the maximal simplex to remove. + * \pre Please check the simplex has no coface before removing it. + * \exception std::invalid_argument In debug mode, if sh has children. + * \post Be aware that removing is shifting data in a flat_map (initialize_filtration to be done). + */ + void remove_maximal_simplex(Simplex_handle sh) { + // Guarantee the simplex has no children + GUDHI_CHECK(!has_children(sh), + std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children")); + + // Simplex is a leaf, it means the child is the Siblings owning the leaf + Siblings* child = sh->second.children(); + + if ((child->size() > 1) || (child == root())) { + // Not alone, just remove it from members + // Special case when child is the root of the simplex tree, just remove it from members + child->erase(sh); + } else { + // Sibling is emptied : must be deleted, and its parent must point on his own Sibling + child->oncles()->members().at(child->parent()).assign_children(child->oncles()); + delete child; + } + } + private: Vertex_handle null_vertex_; /** \brief Upper bound on the filtration values of the simplices.*/ @@ -1119,7 +1260,6 @@ class Simplex_tree { }; // Print a Simplex_tree in os. - template<typename...T> std::ostream& operator<<(std::ostream & os, Simplex_tree<T...> & st) { for (auto sh : st.filtration_simplex_range()) { |