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

4 files changed, 87 insertions, 59 deletions

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<Simplex_handle> 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()