diff options
Diffstat (limited to 'src/Simplex_tree')
4 files changed, 471 insertions, 11 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 096270ee..3569b323 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -30,10 +30,12 @@ #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> @@ -43,10 +45,12 @@ #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 * * A simplicial complex \f$\mathbf{K}\f$ @@ -219,7 +223,7 @@ class Simplex_tree { * * 'value_type' is Simplex_handle. */ typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator; - + /* @} */ // end name range and iterator types /** \name Range and iterator methods * @{ */ @@ -304,7 +308,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 +450,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_; @@ -514,9 +528,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); } @@ -717,7 +732,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 +741,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 +754,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 +763,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 @@ -1104,6 +1119,159 @@ 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; + // 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. + * \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) { + // No action if filtration is not stored + if (Options::store_filtration) { + if (filtration < threshold_) { + threshold_ = filtration; + // Initialize filtration_vect_ if required + if (filtration_vect_.empty()) { + initialize_filtration(); + } + + std::vector<std::vector<Vertex_handle>> simplex_list_to_removed; + // Loop in reverse mode until threshold is reached + // Do not erase while looping, because removing is shifting data in a flat_map + for (auto f_simplex = filtration_vect_.rbegin(); + (f_simplex != filtration_vect_.rend()) && ((*f_simplex)->second.filtration() > threshold_); + f_simplex++) { + std::vector<Vertex_handle> simplex_to_remove; + for (auto vertex : simplex_vertex_range(*f_simplex)) + simplex_to_remove.insert(simplex_to_remove.begin(), vertex); + simplex_list_to_removed.push_back(simplex_to_remove); + } + for (auto simplex_to_remove : simplex_list_to_removed) { + Simplex_handle sh = find_simplex(simplex_to_remove); + if (sh != null_simplex()) + remove_maximal_simplex(sh); + } + // Re-initialize filtration_vect_ if dta were removed, because removing is shifting data in a flat_map + if (simplex_list_to_removed.size() > 0) + initialize_filtration(); + } + } + } + + /** \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. + * \warning 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->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; + } + } +/***************************************************************************************************************/ + public: + /** \brief Prints the simplex_tree hierarchically. + * Since it prints the vertices recursively, one can watch its tree shape. + */ + void debug_tree() { + std::cout << "{" << &root_ << "} -------------------------------------------------------------------" << std::endl; + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { + std::cout << sh->first << " [" << sh->second.filtration() << "] "; + if (has_children(sh)) { + rec_debug_tree(sh->second.children()); + } else { + std::cout << " {- " << sh->second.children() << "} "; + } + std::cout << std::endl; + } + std::cout << "--------------------------------------------------------------------------------------" << std::endl; + } + + + /** \brief Recursively prints the simplex_tree, using depth first search. */ + private: + void rec_debug_tree(Siblings * sib) { + std::cout << " {" << sib << "} ("; + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { + std::cout << " " << sh->first << " [" << sh->second.filtration() << "] "; + if (has_children(sh)) { + rec_debug_tree(sh->second.children()); + } else { + std::cout << " {- " << sh->second.children() << "} "; + } + } + std::cout << ")"; + } + +/*****************************************************************************************************************/ private: Vertex_handle null_vertex_; @@ -1119,7 +1287,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()) { diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h index 936b7a1f..7e0a454d 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h @@ -104,7 +104,8 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< st_(st) { } - Simplex_tree_boundary_simplex_iterator(SimplexTree * st, Simplex_handle sh) + template<class SimplexHandle> + Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh) : last_(sh->first), sib_(nullptr), st_(st) { diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index 072afc8d..8942d92c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -116,6 +116,10 @@ class Simplex_tree_siblings { return members_.size(); } + void erase(const Vertex_handle vh) { + members_.erase(vh); + } + Simplex_tree_siblings * oncles_; Vertex_handle parent_; Dictionary members_; diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 874c3363..cd6746a6 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -795,3 +795,291 @@ BOOST_AUTO_TEST_CASE(non_contiguous) { test_simplex_is_vertex(st, *++i, 3); BOOST_CHECK(++i == std::end(b)); } + +BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { + std::cout << "********************************************************************" << std::endl; + std::cout << "MAKE FILTRATION NON DECREASING" << std::endl; + typedef Simplex_tree<> typeST; + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + + // Inserted simplex: + // 1 + // o + // /X\ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + std::cout << "Check default insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 2.0 + // to 1.0 + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Inserted simplex: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Copy original simplex tree + typeST st_copy = st; + + // Modify specific values for st to become like st_copy thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({0,1,6,7}), 0.8); + st.assign_filtration(st.find({0,1,6}), 0.9); + st.assign_filtration(st.find({0,6}), 0.6); + st.assign_filtration(st.find({3,4,5}), 1.2); + st.assign_filtration(st.find({3,4}), 1.1); + st.assign_filtration(st.find({4,5}), 1.99); + + std::cout << "Check the simplex_tree is rolled back in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_copy); + + // Other simplex tree + typeST st_other; + st_other.insert_simplex_and_subfaces({2, 1, 0}, 3.0); // This one is different from st + st_other.insert_simplex_and_subfaces({3, 0}, 2.0); + st_other.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + st_other.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Modify specific values for st to become like st_other thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({2}), 3.0); + // By modifying just the simplex {2} + // {0,1,2}, {1,2} and {0,2} will be modified + + std::cout << "Check the simplex_tree is repaired in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other); + + // Modify specific values for st still to be non-decreasing + st.assign_filtration(st.find({0,1,2}), 10.0); + st.assign_filtration(st.find({0,2}), 9.0); + st.assign_filtration(st.find({0,1,6,7}), 50.0); + st.assign_filtration(st.find({0,1,6}), 49.0); + st.assign_filtration(st.find({0,1,7}), 48.0); + // Other copy simplex tree + typeST st_other_copy = st; + + std::cout << "Check the simplex_tree is not modified in case of non-decreasing filtration values" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other_copy); + +} + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; + +BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { + std::cout << "********************************************************************" << std::endl; + std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; + + + typedef Simplex_tree<MyOptions> miniST; + miniST st; + + // FIXME + st.set_dimension(3); + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + + // Constructs a copy at this state for further test purpose + miniST st_pruned = st; + + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + // Constructs a copy at this state for further test purpose + miniST st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + +#ifdef GUDHI_DEBUG + std::cout << "Check exception throw in debug mode" << std::endl; + // throw excpt because sh has children + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument); + BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument); + BOOST_CHECK(st == st_complete); +#endif + + st.remove_maximal_simplex(st.find({0, 2})); + st.remove_maximal_simplex(st.find({0, 1, 2})); + st.remove_maximal_simplex(st.find({1, 2})); + st.remove_maximal_simplex(st.find({2})); + st.remove_maximal_simplex(st.find({0, 3})); + + BOOST_CHECK(st == st_pruned); + // Remove all, but as the simplex tree is not storing filtration, there is no modification + st.prune_above_filtration(0.0); + BOOST_CHECK(st == st_pruned); + + miniST st_wo_seven; + // FIXME + st_wo_seven.set_dimension(3); + + st_wo_seven.insert_simplex_and_subfaces({0, 1, 6}); + st_wo_seven.insert_simplex_and_subfaces({3, 4, 5}); + // st_wo_seven: + // 1 6 + // o---o + // \X/ + // o o---o + // 0 3\X/4 + // o + // 5 + + // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not) + st.remove_maximal_simplex(st.find({0, 1, 6, 7})); + st.remove_maximal_simplex(st.find({0, 1, 7})); + st.remove_maximal_simplex(st.find({0, 6, 7})); + st.remove_maximal_simplex(st.find({0, 7})); + st.remove_maximal_simplex(st.find({1, 6, 7})); + st.remove_maximal_simplex(st.find({1, 7})); + st.remove_maximal_simplex(st.find({6, 7})); + st.remove_maximal_simplex(st.find({7})); + + BOOST_CHECK(st == st_wo_seven); +} + +BOOST_AUTO_TEST_CASE(prune_above_filtration) { + std::cout << "********************************************************************" << std::endl; + std::cout << "PRUNE ABOVE FILTRATION" << std::endl; + typedef Simplex_tree<> typeST; + typeST st; + + // FIXME + st.set_dimension(3); + + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + st.set_filtration(6.0); + + // Constructs a copy at this state for further test purpose + typeST st_pruned = st; + st_pruned.initialize_filtration(); // reset + + st.insert_simplex_and_subfaces({3, 0}, 3.0); + st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); + + // Constructs a copy at this state for further test purpose + typeST st_complete = st; + // st_complete and st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + // st_pruned: + // 1 6 + // o---o + // \7/ + // o o---o + // 0 3\X/4 + // o + // 5 + + // Check the no action cases + // greater than initial filtration value + st.prune_above_filtration(10.0); + BOOST_CHECK(st == st_complete); + // equal to initial filtration value + st.prune_above_filtration(6.0); + BOOST_CHECK(st == st_complete); + // lower than initial filtration value, but still greater than the maximum filtration value + st_complete.set_filtration(5.0); + st.prune_above_filtration(5.0); + BOOST_CHECK(st == st_complete); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + // Check the pruned cases + // Set the st_pruned filtration for operator== + st_pruned.set_filtration(2.5); + st.prune_above_filtration(2.5); + BOOST_CHECK(st == st_pruned); + + // Display the Simplex_tree + std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + st_pruned.set_filtration(2.0); + st.prune_above_filtration(2.0); + BOOST_CHECK(st == st_pruned); + + typeST st_empty; + // FIXME + st_empty.set_dimension(3); + st.prune_above_filtration(0.0); + + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + BOOST_CHECK(st == st_empty); + + // Test case to the limit + st.prune_above_filtration(-1.0); + st_empty.set_filtration(-1.0); + BOOST_CHECK(st == st_empty); +} |