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

3 files changed, 78 insertions, 51 deletions

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<Simplex_tree, Dictionary> Siblings;
 
-  /** \brief Element of a flat_map.
-   * 'value_type' is Map_element. */
-  typedef typename std::pair<Vertex_handle, Node> 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 {