From 73e025369bd50511b67b4f8e290a2c3a533ded88 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 19 Jan 2016 10:28:37 +0000 Subject: make_filtration_non_decreasing fix Ut rewrite git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/alphashapes@974 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 3326338b9454923b59d3e42add0f3530c6dbe16f --- src/Alpha_complex/include/gudhi/Alpha_complex.h | 4 +- src/Simplex_tree/include/gudhi/Simplex_tree.h | 37 ++++------ src/Simplex_tree/test/simplex_tree_unit_test.cpp | 88 ++++++++++++++++-------- 3 files changed, 78 insertions(+), 51 deletions(-) (limited to 'src') diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 9f931066..1ab6766c 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -308,7 +308,9 @@ class Alpha_complex : public Simplex_tree<> { // -------------------------------------------------------------------------------------------- // As Alpha value is an approximation, we have to make filtration non decreasing while increasing the dimension - make_filtration_non_decreasing(); + if (make_filtration_non_decreasing()) { + initialize_filtration(); + } // Remove all simplices that have a filtration value greater than max_alpha_square prune_above_filtration(max_alpha_square); // -------------------------------------------------------------------------------------------- diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 16485c89..dbef8517 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -129,10 +129,6 @@ 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; } @@ -1131,15 +1127,10 @@ 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) { + // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree + for (auto sh = (root_.members().end() - 1); sh >= root_.members().begin(); --sh) { if (has_children(sh)) { - modified |= rec_make_filtration_non_decreasing(sh->second.children(), max_border_value->second.filtration()); + modified |= rec_make_filtration_non_decreasing(sh->second.children()); } } return modified; @@ -1148,25 +1139,27 @@ class Simplex_tree { 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 rec_make_filtration_non_decreasing(Siblings * sib) { 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) { + // Find the maximum filtration value in the border + Boundary_simplex_range boundary = boundary_simplex_range(sh); + 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 (sh->second.filtration() < max_filt_border_value) { // Store the filtration modification information modified = true; - sh->second.assign_filtration(upper_filtration); + sh->second.assign_filtration(max_filt_border_value); } if (has_children(sh)) { - modified |= rec_make_filtration_non_decreasing(sh->second.children(), max_border_value->second.filtration()); + modified |= rec_make_filtration_non_decreasing(sh->second.children()); } } // Make the modified information to be traced by upper call diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 25ae5ed3..cd6746a6 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -806,46 +806,78 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { st.insert_simplex_and_subfaces({3, 0}, 2.0); st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - typeST st_bis = st; - // Check default insertion ensures the filtration values are non decreasing + // 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 */ - - BOOST_CHECK(st.make_filtration_non_decreasing()); + // Inserted simplex: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 - // 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); + std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_bis); + // Copy original simplex tree + typeST st_copy = st; - // 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); + // 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_bis); + BOOST_CHECK(st == st_copy); - // 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); + // 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 { -- cgit v1.2.3