diff options
Diffstat (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h')
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 111 |
1 files changed, 106 insertions, 5 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index ea61fa2e..3adf06d3 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -30,6 +30,7 @@ #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> @@ -39,10 +40,11 @@ #include <utility> #include <vector> #include <functional> // for greater<> +#include <stdexcept> +#include <limits> // Inf #include <initializer_list> namespace Gudhi { - /** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ @@ -450,6 +452,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_; @@ -709,7 +720,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()); @@ -718,7 +729,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; @@ -731,7 +742,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. */ @@ -1092,7 +1102,99 @@ class Simplex_tree { os << filtration(sh) << " \n"; } } + + 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. + * \warning 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; + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { + if (has_children(sh)) { + modified |= rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); + } + } + return modified; + } + + private: + /** \brief Recursively Browse the simplex tree to ensure the filtration is not decreasing. + * @param[in] sib Siblings to be parsed. + * @param[in] upper_filtration Upper level filtration value in the simplex tree. + * @return The filtration modification information in order to trigger initialize_filtration. + */ + bool rec_make_filtration_non_decreasing(Siblings * sib, Filtration_value upper_filtration) { + bool modified = false; + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { + if (sh->second.filtration() < upper_filtration) { + // Store the filtration modification information + modified = true; + std::cout << "modified" << std::endl; + sh->second.assign_filtration(upper_filtration); + } + if (has_children(sh)) { + modified |= rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); + } + } + // 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. + * \warning threshold_ is set from filtration given as parameter. + * \warning The filtration must be valid. If the filtration has not been initialized yet, the method initializes it + * (i.e. order the simplices). If the complex has changed since the last time the filtration was initialized, please + * call `initialize_filtration()` to recompute it. + */ + void prune_above_filtration(Filtration_value filtration) { + if (filtration < threshold_) { + threshold_ = filtration; + // Initialize filtration_vect_ if required + if (filtration_vect_.empty()) { + initialize_filtration(); + } + + // Loop in reverse mode until threshold is reached + auto f_simplex = filtration_vect_.rbegin(); + for (; f_simplex != filtration_vect_.rend() && ((*f_simplex)->second.filtration() > threshold_); f_simplex++) { + remove_maximal_simplex(*f_simplex); + } + // Do not forget to update filtration_vect_ - resize is enough + std::size_t new_size = filtration_vect_.size() - (f_simplex - filtration_vect_.rbegin()); + filtration_vect_.resize(new_size); + } + } + + /** \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. + * \warning In debug mode, the exception std::invalid_argument is thrown if sh has children. + */ + 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->members().erase(sh->first); + } 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.*/ @@ -1107,7 +1209,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()) { |