From 8f7e5a1259287ee39595623e87149cb07ab2e293 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 26 Oct 2017 20:16:33 +0000 Subject: Code review: downgrade_dimension renamed lower_upper_bound_dimension and make it private. Automatically when dimension_to_be_lowered_ is set (on removal) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST_automatic_dimension_set@2810 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c764433bcc5357acc6454683d4f4182c7c960d6d --- src/Alpha_complex/test/Alpha_complex_unit_test.cpp | 2 +- src/Simplex_tree/include/gudhi/Simplex_tree.h | 34 ++++++-- .../test/simplex_tree_remove_unit_test.cpp | 98 ++++++++++++---------- src/cython/test/test_simplex_tree.py | 12 +-- 4 files changed, 87 insertions(+), 59 deletions(-) (limited to 'src') diff --git a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp index e60089c4..166373fe 100644 --- a/src/Alpha_complex/test/Alpha_complex_unit_test.cpp +++ b/src/Alpha_complex/test/Alpha_complex_unit_test.cpp @@ -232,7 +232,7 @@ BOOST_AUTO_TEST_CASE(Alpha_complex_from_points) { BOOST_CHECK(simplex_tree.num_simplices() == 10); std::cout << "simplex_tree.dimension()=" << simplex_tree.dimension() << std::endl; - BOOST_CHECK(simplex_tree.dimension() == 3); + BOOST_CHECK(simplex_tree.dimension() == 1); std::cout << "simplex_tree.num_vertices()=" << simplex_tree.num_vertices() << std::endl; BOOST_CHECK(simplex_tree.num_vertices() == 4); diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index ce0994da..54f5de13 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -492,7 +492,16 @@ class Simplex_tree { } /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() const { + int upper_bound_dimension() const { + return dimension_; + } + + /** \brief Returns the dimension of the simplicial complex. + \details This function is not constant time because it can trigger `lower_upper_bound_dimension()` if required. + */ + int dimension() { + if (dimension_to_be_lowered_) + lower_upper_bound_dimension(); return dimension_; } @@ -1162,8 +1171,8 @@ class Simplex_tree { * function is not launching `initialize_filtration()` but returns the filtration modification information. If the * complex has changed , please call `initialize_filtration()` to recompute it. * \post Note that the dimension of the simplicial complex may be lower after calling `prune_above_filtration()` - * than it was before. However, `Simplex_tree::dimension()` will return the old value, which remains a valid upper - * bound. If you care, you can call `downgrade_dimension()` to recompute the exact dimension. + * than it was before. However, `upper_bond_dimension()` will return the old value, which remains a valid upper + * bound. If you care, you can call `dimension()` to recompute the exact dimension. */ bool prune_above_filtration(Filtration_value filtration) { return rec_prune_above_filtration(root(), filtration); @@ -1175,6 +1184,8 @@ class Simplex_tree { 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()); + // dimension may need to be lowered + dimension_to_be_lowered_ = true; return true; }); @@ -1183,6 +1194,8 @@ class Simplex_tree { // Removing the whole siblings, parent becomes a leaf. sib->oncles()->members()[sib->parent()].assign_children(sib->oncles()); delete sib; + // dimension may need to be lowered + dimension_to_be_lowered_ = true; return true; } else { // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones. @@ -1194,13 +1207,15 @@ class Simplex_tree { return modified; } - public: + private: /** \brief Deep search simplex tree dimension recompute. * @return True if the dimension was modified, false otherwise. * \pre Be sure the simplex tree has not a too low dimension value as the deep search stops when the former dimension - * has been reached (cf. `dimension()` and `set_dimension()` methods). + * has been reached (cf. `upper_bound_dimension()` and `set_dimension()` methods). */ - bool downgrade_dimension() { + bool lower_upper_bound_dimension() { + // reset automatic detection to recompute + dimension_to_be_lowered_ = false; int new_dimension = -1; // Browse the tree from the left to the right as higher dimension cells are more likely on the left part of the tree for (Simplex_handle sh : complex_simplex_range()) { @@ -1229,8 +1244,8 @@ class Simplex_tree { * \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). * \post Note that the dimension of the simplicial complex may be lower after calling `remove_maximal_simplex()` - * than it was before. However, `Simplex_tree::dimension()` will return the old value, which remains a valid upper - * bound. If you care, you can call `downgrade_dimension()` to recompute the exact dimension. + * than it was before. However, `upper_bond_dimension()` will return the old value, which remains a valid upper + * bound. If you care, you can call `dimension()` to recompute the exact dimension. */ void remove_maximal_simplex(Simplex_handle sh) { // Guarantee the simplex has no children @@ -1248,6 +1263,8 @@ class Simplex_tree { // 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; + // dimension may need to be lowered + dimension_to_be_lowered_ = true; } } @@ -1262,6 +1279,7 @@ class Simplex_tree { std::vector filtration_vect_; /** \brief Upper bound on the dimension of the simplicial complex.*/ int dimension_; + bool dimension_to_be_lowered_ = false; }; // Print a Simplex_tree in os. diff --git a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp index 747e7eeb..dc37375c 100644 --- a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp @@ -109,11 +109,15 @@ BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { std::cout << "st.remove_maximal_simplex({7})" << std::endl; st.remove_maximal_simplex(st.find({7})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 3); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); - st.downgrade_dimension(); + // Check dimension calls lower_upper_bound_dimension to recompute dimension + BOOST_CHECK(st.dimension() == 2); + BOOST_CHECK(st.upper_bound_dimension() == 2); + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() + << " | st_wo_seven.upper_bound_dimension()=" << st_wo_seven.upper_bound_dimension() << std::endl; std::cout << "st.dimension()=" << st.dimension() << " | st_wo_seven.dimension()=" << st_wo_seven.dimension() << std::endl; BOOST_CHECK(st == st_wo_seven); } @@ -131,116 +135,121 @@ BOOST_AUTO_TEST_CASE(auto_dimension_set) { st.insert_simplex_and_subfaces({6, 7, 8, 9}); st.insert_simplex_and_subfaces({6, 7, 8, 10}); + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.remove_maximal_simplex({6, 7, 8, 10})" << std::endl; st.remove_maximal_simplex(st.find({6, 7, 8, 10})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.remove_maximal_simplex({6, 7, 8, 9})" << std::endl; st.remove_maximal_simplex(st.find({6, 7, 8, 9})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.remove_maximal_simplex({1, 2, 3, 4})" << std::endl; st.remove_maximal_simplex(st.find({1, 2, 3, 4})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.remove_maximal_simplex({1, 2, 3, 5})" << std::endl; st.remove_maximal_simplex(st.find({1, 2, 3, 5})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 3); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; st.insert_simplex_and_subfaces({1, 2, 3, 5}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 4})" << std::endl; st.insert_simplex_and_subfaces({1, 2, 3, 4}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); + std::cout << "st.remove_maximal_simplex({1, 2, 3, 5})" << std::endl; st.remove_maximal_simplex(st.find({1, 2, 3, 5})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); + std::cout << "st.remove_maximal_simplex({1, 2, 3, 4})" << std::endl; st.remove_maximal_simplex(st.find({1, 2, 3, 4})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 3); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; std::cout << "st.insert_simplex_and_subfaces({0, 1, 3, 4})" << std::endl; st.insert_simplex_and_subfaces({0, 1, 3, 4}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.remove_maximal_simplex({0, 1, 3, 4})" << std::endl; st.remove_maximal_simplex(st.find({0, 1, 3, 4})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 3); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 2); + std::cout << "st.dimension()=" << st.dimension() << std::endl; std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 5})" << std::endl; st.insert_simplex_and_subfaces({1, 2, 3, 5}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.insert_simplex_and_subfaces({1, 2, 3, 4})" << std::endl; st.insert_simplex_and_subfaces({1, 2, 3, 4}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); // Check you can override the dimension // This is a limit test case - shall not happen st.set_dimension(1); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 1); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - // check downgrade_dimension() is not giving the rigt answer because dimension is too low + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 1); + // check dimension() and lower_upper_bound_dimension() is not giving the right answer because dimension is too low BOOST_CHECK(st.dimension() == 1); // Check you can override the dimension // This is a limit test case - shall not happen st.set_dimension(6); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); + // check dimension() do not launch lower_upper_bound_dimension() BOOST_CHECK(st.dimension() == 6); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - // check downgrade_dimension() resets the correct dimension - BOOST_CHECK(st.dimension() == 3); // Reset with the correct value st.set_dimension(3); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); BOOST_CHECK(st.dimension() == 3); std::cout << "st.insert_simplex_and_subfaces({0, 1, 2, 3, 4, 5, 6})" << std::endl; st.insert_simplex_and_subfaces({0, 1, 2, 3, 4, 5, 6}); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); BOOST_CHECK(st.dimension() == 6); std::cout << "st.remove_maximal_simplex({0, 1, 2, 3, 4, 5, 6})" << std::endl; st.remove_maximal_simplex(st.find({0, 1, 2, 3, 4, 5, 6})); - std::cout << "st.dimension()=" << st.dimension() << std::endl; - BOOST_CHECK(st.dimension() == 6); - st.downgrade_dimension(); - std::cout << "st.dimension()=" << st.dimension() << std::endl; + std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 6); BOOST_CHECK(st.dimension() == 5); } @@ -336,17 +345,18 @@ BOOST_AUTO_TEST_CASE(prune_above_filtration) { Stree st_empty; simplex_is_changed = st.prune_above_filtration(0.0); + BOOST_CHECK(simplex_is_changed == true); 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.dimension() == 3); + std::cout << " - upper_bound_dimension " << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == 3); - st.downgrade_dimension(); - std::cout << "dimension=" << st.dimension() << std::endl; BOOST_CHECK(st.dimension() == -1); + std::cout << "upper_bound_dimension=" << st.upper_bound_dimension() << std::endl; + BOOST_CHECK(st.upper_bound_dimension() == -1); BOOST_CHECK(st == st_empty); BOOST_CHECK(simplex_is_changed); diff --git a/src/cython/test/test_simplex_tree.py b/src/cython/test/test_simplex_tree.py index 177cfdad..a6d6a9f3 100755 --- a/src/cython/test/test_simplex_tree.py +++ b/src/cython/test/test_simplex_tree.py @@ -94,12 +94,12 @@ def test_insertion(): assert st.persistence(persistence_dim_max = True) == [(1, (4.0, float('inf'))), (0, (0.0, float('inf')))] assert st.__is_persistence_defined() == True - assert st.betti_numbers() == [1, 1, 0] - assert st.persistent_betti_numbers(-0.1, 10000.0) == [0, 0, 0] - assert st.persistent_betti_numbers(0.0, 10000.0) == [1, 0, 0] - assert st.persistent_betti_numbers(3.9, 10000.0) == [1, 0, 0] - assert st.persistent_betti_numbers(4.0, 10000.0) == [1, 1, 0] - assert st.persistent_betti_numbers(9999.0, 10000.0) == [1, 1, 0] + assert st.betti_numbers() == [1, 1] + assert st.persistent_betti_numbers(-0.1, 10000.0) == [0, 0] + assert st.persistent_betti_numbers(0.0, 10000.0) == [1, 0] + assert st.persistent_betti_numbers(3.9, 10000.0) == [1, 0] + assert st.persistent_betti_numbers(4.0, 10000.0) == [1, 1] + assert st.persistent_betti_numbers(9999.0, 10000.0) == [1, 1] def test_expansion(): st = SimplexTree() -- cgit v1.2.3