summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree.h64
-rw-r--r--src/Simplex_tree/test/simplex_tree_unit_test.cpp67
2 files changed, 86 insertions, 45 deletions
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 <stdexcept>
#include <limits> // Inf
#include <initializer_list>
+#include <algorithm> // 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<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; }
@@ -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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-20 06:44:42 +0000