diff options
author | glisse <glisse@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-04-08 16:19:20 +0000 |
---|---|---|
committer | glisse <glisse@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-04-08 16:19:20 +0000 |
commit | a44155daa5ae4253a874dad4a22b6da4bd017fee (patch) | |
tree | dca668d3ada0f45329f80b3f7c49b74ea576523f /src/Simplex_tree | |
parent | 50327ad1f3fbf370fcdd3aa877b6e75644329662 (diff) | |
parent | baf1b5b39be90694b512fff9c79438bf362916f3 (diff) |
Merge from trunk.
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/debian@1112 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 82a43e89115f09449d4f31ebfd9ff56170d8771f
Diffstat (limited to 'src/Simplex_tree')
-rw-r--r-- | src/Simplex_tree/doc/Simplex_tree_representation.png | bin | 0 -> 39217 bytes | |||
-rw-r--r-- | src/Simplex_tree/example/CMakeLists.txt | 9 | ||||
-rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 186 | ||||
-rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h | 3 | ||||
-rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h | 4 | ||||
-rw-r--r-- | src/Simplex_tree/test/CMakeLists.txt | 3 | ||||
-rw-r--r-- | src/Simplex_tree/test/simplex_tree_unit_test.cpp | 352 |
7 files changed, 533 insertions, 24 deletions
diff --git a/src/Simplex_tree/doc/Simplex_tree_representation.png b/src/Simplex_tree/doc/Simplex_tree_representation.png Binary files differnew file mode 100644 index 00000000..9d401520 --- /dev/null +++ b/src/Simplex_tree/doc/Simplex_tree_representation.png diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt index 200161a6..89a4e053 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -2,10 +2,16 @@ cmake_minimum_required(VERSION 2.6) project(GUDHISimplexTreeFromFile) add_executable ( simplex_tree_from_cliques_of_graph simplex_tree_from_cliques_of_graph.cpp ) +if (TBB_FOUND) + target_link_libraries(simplex_tree_from_cliques_of_graph ${TBB_RELEASE_LIBRARY}) +endif() add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 2) add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 3) add_executable ( simple_simplex_tree simple_simplex_tree.cpp ) +if (TBB_FOUND) + target_link_libraries(simple_simplex_tree ${TBB_RELEASE_LIBRARY}) +endif() add_test(simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/simple_simplex_tree) add_executable ( mini_simplex_tree mini_simplex_tree.cpp ) @@ -16,5 +22,8 @@ add_test(mini_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/mini_simplex_tree) if(GMP_FOUND AND CGAL_FOUND) add_executable ( simplex_tree_from_alpha_shapes_3 simplex_tree_from_alpha_shapes_3.cpp ) target_link_libraries(simplex_tree_from_alpha_shapes_3 ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(simplex_tree_from_alpha_shapes_3 ${TBB_RELEASE_LIBRARY}) + endif() add_test(simplex_tree_from_alpha_shapes_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_alpha_shapes_3 ${CMAKE_SOURCE_DIR}/data/points/bunny_5000) endif() diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 8a1a1344..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); } @@ -582,7 +596,19 @@ class Simplex_tree { 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()) { 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..1eca7f6f 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 Dictionary_it iterator) { + members_.erase(iterator); + } + Simplex_tree_siblings * oncles_; Vertex_handle parent_; Dictionary members_; diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt index 1f2f7d33..609d8669 100644 --- a/src/Simplex_tree/test/CMakeLists.txt +++ b/src/Simplex_tree/test/CMakeLists.txt @@ -12,6 +12,9 @@ endif() add_executable ( SimplexTreeUT simplex_tree_unit_test.cpp ) target_link_libraries(SimplexTreeUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(SimplexTreeUT ${TBB_RELEASE_LIBRARY}) +endif() # Do not forget to copy test files in current binary dir file(COPY "simplex_tree_for_unit_test.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 874c3363..b1bb23b1 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -795,3 +795,355 @@ 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); + + // 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 + + bool simplex_is_changed = false; + // Check the no action cases + // greater than initial filtration value + simplex_is_changed = st.prune_above_filtration(10.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + // equal to initial filtration value + simplex_is_changed = st.prune_above_filtration(6.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + // lower than initial filtration value, but still greater than the maximum filtration value + simplex_is_changed = st.prune_above_filtration(5.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_complete); + BOOST_CHECK(!simplex_is_changed); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << 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 + simplex_is_changed = st.prune_above_filtration(2.5); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_pruned); + BOOST_CHECK(simplex_is_changed); + + // Display the Simplex_tree + std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + + simplex_is_changed = st.prune_above_filtration(2.0); + if (simplex_is_changed) + st.initialize_filtration(); + + std::cout << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + + BOOST_CHECK(st == st_pruned); + BOOST_CHECK(!simplex_is_changed); + + typeST st_empty; + // FIXME + st_empty.set_dimension(3); + simplex_is_changed = st.prune_above_filtration(0.0); + if (simplex_is_changed) + st.initialize_filtration(); + + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices"; + std::cout << " - dimension " << st.dimension() << std::endl; + + BOOST_CHECK(st == st_empty); + BOOST_CHECK(simplex_is_changed); + + // Test case to the limit + simplex_is_changed = st.prune_above_filtration(-1.0); + if (simplex_is_changed) + st.initialize_filtration(); + BOOST_CHECK(st == st_empty); + BOOST_CHECK(!simplex_is_changed); +} + +BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) { + std::cout << "********************************************************************" << std::endl; + std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl; + typedef Simplex_tree<MyOptions> typeST; + typeST st; + + // FIXME + st.set_dimension(3); + + st.insert_simplex_and_subfaces({0, 1, 6, 7}); + st.insert_simplex_and_subfaces({3, 4, 5}); + st.insert_simplex_and_subfaces({3, 0}); + st.insert_simplex_and_subfaces({2, 1, 0}); + + // st: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + st.initialize_filtration(); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(st.num_simplices() == 27); + + // Test case to the limit - With these options, there is no filtration, which means filtration is 0 + bool simplex_is_changed = st.prune_above_filtration(1.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(!simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 27); + + simplex_is_changed = st.prune_above_filtration(0.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at 0.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(!simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 27); + + // Test case to the limit + simplex_is_changed = st.prune_above_filtration(-1.0); + if (simplex_is_changed) + st.initialize_filtration(); + // Display the Simplex_tree + std::cout << "The complex pruned at -1.0 contains " << st.num_simplices() << " simplices" << std::endl; + BOOST_CHECK(simplex_is_changed); + BOOST_CHECK(st.num_simplices() == 0); + + // Display the Simplex_tree + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + +}
\ No newline at end of file |