From f443bbd06cac275284f75936d6803105eb99fec6 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 15 Jan 2016 13:00:53 +0000 Subject: make_filtration_non_decreasing fix. Make it non decreasing for border and not only for parent. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@972 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e71f40baa56de53e68b02603b64fb504b1f5d978 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 64 +++++++++++++++++++--- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 67 ++++++++++-------------- 2 files changed, 86 insertions(+), 45 deletions(-) (limited to 'src/Simplex_tree') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 3ba838a7..16485c89 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -47,6 +47,7 @@ #include #include // Inf #include +#include // for std::max namespace Gudhi { /** \defgroup simplex_tree Filtered Complexes @@ -128,6 +129,10 @@ class Simplex_tree { /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings Siblings; + /** \brief Element of a flat_map. + * 'value_type' is Map_element. */ + typedef typename std::pair Map_element; + struct Key_simplex_base_real { Key_simplex_base_real() : key_(-1) {} void assign_key(Simplex_key k) { key_ = k; } @@ -221,7 +226,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 * @{ */ @@ -327,11 +332,10 @@ class Simplex_tree { Simplex_tree(const Simplex_tree& simplex_source) : null_vertex_(simplex_source.null_vertex_), threshold_(simplex_source.threshold_), + root_(nullptr, null_vertex_ , simplex_source.root_.members_), filtration_vect_(), dimension_(simplex_source.dimension_) { auto root_source = simplex_source.root_; - auto memb_source = root_source.members(); - root_ = Siblings(nullptr, null_vertex_, memb_source); rec_copy(&root_, &root_source); } @@ -343,7 +347,7 @@ class Simplex_tree { Siblings * newsib = new Siblings(sib, sh_source->first); newsib->members_.reserve(sh_source->second.children()->members().size()); for (auto & child : sh_source->second.children()->members()) - newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(sib, child.second.filtration())); + newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration())); rec_copy(newsib, sh_source->second.children()); sh->second.assign_children(newsib); } @@ -1127,9 +1131,15 @@ class Simplex_tree { */ bool make_filtration_non_decreasing() { bool modified = false; + + // Find the maximum filtration value in the border + Simplex_handle max_border_value = std::max_element( std::begin(root_.members()), std::end(root_.members()), + [](const Map_element& sh1, const Map_element& sh2) { + return sh1.second.filtration() < sh2.second.filtration(); + }); 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()); + modified |= rec_make_filtration_non_decreasing(sh->second.children(), max_border_value->second.filtration()); } } return modified; @@ -1143,6 +1153,12 @@ class Simplex_tree { */ bool rec_make_filtration_non_decreasing(Siblings * sib, Filtration_value upper_filtration) { bool modified = false; + // Find the maximum filtration value in the border + Simplex_handle max_border_value = std::max_element( std::begin(sib->members()), std::end(sib->members()), + [](const Map_element& sh1, const Map_element& sh2) { + return sh1.second.filtration() < sh2.second.filtration(); + }); + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { if (sh->second.filtration() < upper_filtration) { // Store the filtration modification information @@ -1150,7 +1166,7 @@ class Simplex_tree { sh->second.assign_filtration(upper_filtration); } if (has_children(sh)) { - modified |= rec_make_filtration_non_decreasing(sh->second.children(), sh->second.filtration()); + modified |= rec_make_filtration_non_decreasing(sh->second.children(), max_border_value->second.filtration()); } } // Make the modified information to be traced by upper call @@ -1223,6 +1239,42 @@ std::cout << "prune_above_filtration - filtration=" << filtration << std::endl; 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_; diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 1a050a25..25ae5ed3 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -802,13 +802,18 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { typedef Simplex_tree<> typeST; typeST st; - st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); - st.insert_simplex_and_subfaces({3, 0}, 3.0); + 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); - // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 4.0 + + typeST st_bis = st; + // Check default insertion ensures the filtration values are non decreasing + 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 */ @@ -817,45 +822,29 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { /* 2 0 3\X/4 */ /* o */ /* 5 */ - - // FIXME - st.set_dimension(3); - - // Copy constructor - typeST st_copy = st; - - // Check default insertion ensures the filtration values are non decreasing - BOOST_CHECK(!st.make_filtration_non_decreasing()); - // Check the simplex tree is not modified by the function - BOOST_CHECK(st == st_copy); - - // Make { 0, 1 } decreasing - st.assign_filtration(st.find({0, 1}), 0.5); - // Make { 1, 6, 7 } decreasing - st.assign_filtration(st.find({1, 6, 7}), 0.4); - // Make { 3, 4 } decreasing - st.assign_filtration(st.find({3, 4}), 0.3); - // Make { 4, 5 } decreasing - st.assign_filtration(st.find({4, 5}), 0.1); - - // Check the filtration values were decreasing + BOOST_CHECK(st.make_filtration_non_decreasing()); - // Check the simplex tree has been modified by the function to retrieve the initial simplex tree - BOOST_CHECK(st == st_copy); + + // Check make_filtration_non_decreasing is just not modifying root values + st_bis.insert_simplex_and_subfaces({0, 1, 6, 7}, 2.0); + st_bis.assign_filtration(st_bis.find({0}), 1.0); + st_bis.assign_filtration(st_bis.find({1}), 1.0); + st_bis.assign_filtration(st_bis.find({6}), 1.0); + st_bis.assign_filtration(st_bis.find({7}), 1.0); + + BOOST_CHECK(st == st_bis); - // Change { 0, 3 }, but still non decreasing - st.assign_filtration(st.find({0, 3}), 1.01); - // Change { 0, 1, 6, 7 }, but still non decreasing - st.assign_filtration(st.find({0, 1, 6, 7}), 1.201); - // Change { 1, 2 }, but still non decreasing - st.assign_filtration(st.find({1, 2}), 1.05); - // Change { 4 }, but still non decreasing - st.assign_filtration(st.find({4}), 1.123); + // Check make_filtration_non_decreasing can modify non-root values (leaves and non-leaf) + st.assign_filtration(st.find({0, 1, 6, 7}), 1.99); + st.assign_filtration(st.find({3, 4}), 1.5); + st.assign_filtration(st.find({0, 3}), -1.0); + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_bis); - // Check the filtration values are non decreasing + // Check make_filtration_non_decreasing is not modifying when increasing + st.assign_filtration(st.find({0, 1, 6, 7}), 4.5); + st.assign_filtration(st.find({3, 4, 5}), 15.0); BOOST_CHECK(!st.make_filtration_non_decreasing()); - // Check the simplex tree has been modified from the original - BOOST_CHECK(st != st_copy); } -- cgit v1.2.3