summaryrefslogtreecommitdiff
path: root/src/Simplex_tree
diff options
context:
space:
mode:
Diffstat (limited to 'src/Simplex_tree')
-rw-r--r--src/Simplex_tree/doc/Intro_simplex_tree.h9
-rw-r--r--src/Simplex_tree/example/CMakeLists.txt15
-rw-r--r--src/Simplex_tree/example/graph_expansion_with_blocker.cpp79
-rw-r--r--src/Simplex_tree/example/mini_simplex_tree.cpp2
-rw-r--r--src/Simplex_tree/example/simple_simplex_tree.cpp38
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree.h207
-rw-r--r--src/Simplex_tree/test/CMakeLists.txt24
-rw-r--r--src/Simplex_tree/test/README2
-rw-r--r--src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp235
-rw-r--r--src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp136
-rw-r--r--src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp427
-rw-r--r--src/Simplex_tree/test/simplex_tree_unit_test.cpp295
12 files changed, 1133 insertions, 336 deletions
diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h
index f5b72ff6..769491d9 100644
--- a/src/Simplex_tree/doc/Intro_simplex_tree.h
+++ b/src/Simplex_tree/doc/Intro_simplex_tree.h
@@ -67,10 +67,13 @@ Information of the Simplex Tree:
Number of vertices = 10 Number of simplices = 98 \endcode
*
* \li <a href="_simplex_tree_2example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html">
- * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - Simplex tree is computed and displayed from a 3D alpha
- * complex (Requires CGAL, GMP and GMPXX to be installed)
- *
+ * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - Simplex tree is computed and displayed
+ * from a 3D alpha complex (Requires CGAL, GMP and GMPXX to be installed).
*
+ * \li <a href="_simplex_tree_2graph_expansion_with_blocker_8cpp-example.html">
+ * Simplex_tree/graph_expansion_with_blocker.cpp</a> - Simple simplex tree construction from a one-skeleton graph with
+ * a simple blocker expansion method.
+ *
* \subsection filteredcomplexeshassecomplex Hasse complex
* The second one is the Hasse_complex. The Hasse complex is a data structure representing explicitly all co-dimension
* 1 incidence relations in a complex. It is consequently faster when accessing the boundary of a simplex, but is less
diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt
index b1ea98d4..8bc4ad53 100644
--- a/src/Simplex_tree/example/CMakeLists.txt
+++ b/src/Simplex_tree/example/CMakeLists.txt
@@ -19,14 +19,27 @@ add_test(NAME Simplex_tree_example_simple_simplex_tree COMMAND $<TARGET_FILE:Sim
add_executable ( Simplex_tree_example_mini_simplex_tree mini_simplex_tree.cpp )
add_test(NAME Simplex_tree_example_mini_simplex_tree COMMAND $<TARGET_FILE:Simplex_tree_example_mini_simplex_tree>)
+install(TARGETS Simplex_tree_example_from_cliques_of_graph DESTINATION bin)
+install(TARGETS Simplex_tree_example_simple_simplex_tree DESTINATION bin)
+install(TARGETS Simplex_tree_example_mini_simplex_tree DESTINATION bin)
# An example with Simplex-tree using CGAL alpha_shapes_3
if(GMP_FOUND AND CGAL_FOUND)
add_executable ( Simplex_tree_example_alpha_shapes_3_from_off example_alpha_shapes_3_simplex_tree_from_off_file.cpp )
- target_link_libraries(Simplex_tree_example_alpha_shapes_3_from_off ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY})
+ target_link_libraries(Simplex_tree_example_alpha_shapes_3_from_off ${GMP_LIBRARIES} ${CGAL_LIBRARY})
if (TBB_FOUND)
target_link_libraries(Simplex_tree_example_alpha_shapes_3_from_off ${TBB_LIBRARIES})
endif()
add_test(NAME Simplex_tree_example_alpha_shapes_3_from_off COMMAND $<TARGET_FILE:Simplex_tree_example_alpha_shapes_3_from_off>
"${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off")
+
+ install(TARGETS Simplex_tree_example_alpha_shapes_3_from_off DESTINATION bin)
endif()
+
+add_executable ( Simplex_tree_example_graph_expansion_with_blocker graph_expansion_with_blocker.cpp )
+if (TBB_FOUND)
+ target_link_libraries(Simplex_tree_example_graph_expansion_with_blocker ${TBB_LIBRARIES})
+endif()
+add_test(NAME Simplex_tree_example_graph_expansion_with_blocker COMMAND $<TARGET_FILE:Simplex_tree_example_graph_expansion_with_blocker>)
+
+install(TARGETS Simplex_tree_example_graph_expansion_with_blocker DESTINATION bin)
diff --git a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp
new file mode 100644
index 00000000..86bfb8cb
--- /dev/null
+++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp
@@ -0,0 +1,79 @@
+/* This file is part of the Gudhi Library. The Gudhi library
+ * (Geometric Understanding in Higher Dimensions) is a generic C++
+ * library for computational topology.
+ *
+ * Author(s): Vincent Rouvreau
+ *
+ * Copyright (C) 2014
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <gudhi/Simplex_tree.h>
+
+#include <iostream>
+
+using Simplex_tree = Gudhi::Simplex_tree<>;
+using Simplex_handle = Simplex_tree::Simplex_handle;
+
+int main(int argc, char * const argv[]) {
+
+ // Construct the Simplex Tree with a 1-skeleton graph example
+ Simplex_tree simplexTree;
+
+ simplexTree.insert_simplex({0, 1}, 0.);
+ simplexTree.insert_simplex({0, 2}, 1.);
+ simplexTree.insert_simplex({0, 3}, 2.);
+ simplexTree.insert_simplex({1, 2}, 3.);
+ simplexTree.insert_simplex({1, 3}, 4.);
+ simplexTree.insert_simplex({2, 3}, 5.);
+ simplexTree.insert_simplex({2, 4}, 6.);
+ simplexTree.insert_simplex({3, 6}, 7.);
+ simplexTree.insert_simplex({4, 5}, 8.);
+ simplexTree.insert_simplex({4, 6}, 9.);
+ simplexTree.insert_simplex({5, 6}, 10.);
+ simplexTree.insert_simplex({6}, 10.);
+
+ simplexTree.expansion_with_blockers(3, [&](Simplex_handle sh){
+ bool result = false;
+ std::cout << "Blocker on [";
+ // User can loop on the vertices from the given simplex_handle i.e.
+ for (auto vertex : simplexTree.simplex_vertex_range(sh)) {
+ // We block the expansion, if the vertex '6' is in the given list of vertices
+ if (vertex == 6)
+ result = true;
+ std::cout << vertex << ", ";
+ }
+ std::cout << "] ( " << simplexTree.filtration(sh);
+ // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries)
+ simplexTree.assign_filtration(sh, simplexTree.filtration(sh) + 1.);
+
+ std::cout << " + 1. ) = " << result << std::endl;
+
+ return result;
+ });
+
+ std::cout << "********************************************************************\n";
+ std::cout << "* The complex contains " << simplexTree.num_simplices() << " simplices";
+ std::cout << " - dimension " << simplexTree.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ for (auto f_simplex : simplexTree.filtration_simplex_range()) {
+ std::cout << " " << "[" << simplexTree.filtration(f_simplex) << "] ";
+ for (auto vertex : simplexTree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ return 0;
+}
diff --git a/src/Simplex_tree/example/mini_simplex_tree.cpp b/src/Simplex_tree/example/mini_simplex_tree.cpp
index ad99df23..19e45361 100644
--- a/src/Simplex_tree/example/mini_simplex_tree.cpp
+++ b/src/Simplex_tree/example/mini_simplex_tree.cpp
@@ -52,8 +52,6 @@ int main() {
auto edge03 = {0, 3};
st.insert_simplex_and_subfaces(triangle012);
st.insert_simplex_and_subfaces(edge03);
- // FIXME: Remove this line
- st.set_dimension(2);
auto edge02 = {0, 2};
ST::Simplex_handle e = st.find(edge02);
diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp
index 60f9a35e..b6b65b88 100644
--- a/src/Simplex_tree/example/simple_simplex_tree.cpp
+++ b/src/Simplex_tree/example/simple_simplex_tree.cpp
@@ -185,19 +185,16 @@ int main(int argc, char * const argv[]) {
}
// ++ GENERAL VARIABLE SET
- simplexTree.set_filtration(FOURTH_FILTRATION_VALUE); // Max filtration value
- simplexTree.set_dimension(2); // Max dimension = 2 -> (2,1,0)
std::cout << "********************************************************************\n";
// Display the Simplex_tree - Can not be done in the middle of 2 inserts
std::cout << "* The complex contains " << simplexTree.num_simplices() << " simplices\n";
- std::cout << " - dimension " << simplexTree.dimension() << " - filtration " << simplexTree.filtration() << "\n";
+ std::cout << " - dimension " << simplexTree.dimension() << "\n";
std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
for (auto f_simplex : simplexTree.filtration_simplex_range()) {
std::cout << " " << "[" << simplexTree.filtration(f_simplex) << "] ";
- for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) {
- std::cout << static_cast<int>(vertex) << " ";
- }
+ for (auto vertex : simplexTree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
std::cout << std::endl;
}
// [0.1] 0
@@ -250,5 +247,34 @@ int main(int argc, char * const argv[]) {
std::cout << "***+ YES IT IS!\n";
else
std::cout << "***- NO IT ISN'T\n";
+
+ simplexFound = simplexTree.find({ 0, 1 });
+ std::cout << "**************IS THE SIMPLEX {0,1} IN THE SIMPLEX TREE ?\n";
+ if (simplexFound != simplexTree.null_simplex())
+ std::cout << "***+ YES IT IS!\n";
+ else
+ std::cout << "***- NO IT ISN'T\n";
+
+ std::cout << "**************COFACES OF {0,1} IN CODIMENSION 1 ARE\n";
+ for (auto& simplex : simplexTree.cofaces_simplex_range(simplexTree.find({0,1}), 1)) {
+ for (auto vertex : simplexTree.simplex_vertex_range(simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ std::cout << "**************STARS OF {0,1} ARE\n";
+ for (auto& simplex : simplexTree.star_simplex_range(simplexTree.find({0,1}))) {
+ for (auto vertex : simplexTree.simplex_vertex_range(simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ std::cout << "**************BOUNDARIES OF {0,1,2} ARE\n";
+ for (auto& simplex : simplexTree.boundary_simplex_range(simplexTree.find({0,1,2}))) {
+ for (auto vertex : simplexTree.simplex_vertex_range(simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
return 0;
}
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 317bce23..7da767cb 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -289,7 +289,6 @@ class Simplex_tree {
/** \brief Constructs an empty simplex tree. */
Simplex_tree()
: null_vertex_(-1),
- threshold_(0),
root_(nullptr, null_vertex_),
filtration_vect_(),
dimension_(-1) { }
@@ -297,7 +296,6 @@ class Simplex_tree {
/** \brief User-defined copy constructor reproduces the whole tree structure. */
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_) {
@@ -323,12 +321,10 @@ class Simplex_tree {
/** \brief User-defined move constructor moves the whole tree structure. */
Simplex_tree(Simplex_tree && old)
: null_vertex_(std::move(old.null_vertex_)),
- threshold_(std::move(old.threshold_)),
root_(std::move(old.root_)),
filtration_vect_(std::move(old.filtration_vect_)),
dimension_(std::move(old.dimension_)) {
old.dimension_ = -1;
- old.threshold_ = 0;
old.root_ = Siblings(nullptr, null_vertex_);
}
@@ -356,7 +352,6 @@ class Simplex_tree {
/** \brief Checks if two simplex trees are equal. */
bool operator==(Simplex_tree& st2) {
if ((null_vertex_ != st2.null_vertex_) ||
- (threshold_ != st2.threshold_) ||
(dimension_ != st2.dimension_))
return false;
return rec_equal(&root_, &st2.root_);
@@ -407,14 +402,14 @@ class Simplex_tree {
/** \brief Returns the filtration value of a simplex.
*
- * Called on the null_simplex, returns INFINITY.
+ * Called on the null_simplex, it returns infinity.
* If SimplexTreeOptions::store_filtration is false, returns 0.
*/
static Filtration_value filtration(Simplex_handle sh) {
if (sh != null_simplex()) {
return sh->second.filtration();
} else {
- return INFINITY;
+ return std::numeric_limits<Filtration_value>::infinity();
}
}
@@ -427,11 +422,6 @@ class Simplex_tree {
sh->second.assign_filtration(fv);
}
- /** \brief Returns an upper bound of the filtration values of the simplices. */
- Filtration_value filtration() const {
- return threshold_;
- }
-
/** \brief Returns a Simplex_handle different from all Simplex_handles
* associated to the simplices in the simplicial complex.
*
@@ -492,7 +482,17 @@ 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 recompute dimension if required (can be triggered by
+ `remove_maximal_simplex()` or `prune_above_filtration()`).
+ */
+ int dimension() {
+ if (dimension_to_be_lowered_)
+ lower_upper_bound_dimension();
return dimension_;
}
@@ -601,7 +601,11 @@ class Simplex_tree {
// if filtration value unchanged
return std::pair<Simplex_handle, bool>(null_simplex(), false);
}
- // otherwise the insertion has succeeded
+ // otherwise the insertion has succeeded - size is a size_type
+ if (static_cast<int>(simplex.size()) - 1 > dimension_) {
+ // Update dimension if needed
+ dimension_ = static_cast<int>(simplex.size()) - 1;
+ }
return res_insert;
}
@@ -757,11 +761,6 @@ class Simplex_tree {
return &root_;
}
- /** Set an upper bound for the filtration values. */
- void set_filtration(Filtration_value fil) {
- threshold_ = fil;
- }
-
/** Set a dimension for the simplicial complex. */
void set_dimension(int dimension) {
dimension_ = dimension;
@@ -1082,6 +1081,118 @@ class Simplex_tree {
}
public:
+ /** \brief Expands a simplex tree containing only a graph. Simplices corresponding to cliques in the graph are added
+ * incrementally, faces before cofaces, unless the simplex has dimension larger than `max_dim` or `block_simplex`
+ * returns true for this simplex.
+ *
+ * @param[in] max_dim Expansion maximal dimension value.
+ * @param[in] block_simplex Blocker oracle. Its concept is <CODE>bool block_simplex(Simplex_handle sh)</CODE>
+ *
+ * The function identifies a candidate simplex whose faces are all already in the complex, inserts
+ * it with a filtration value corresponding to the maximum of the filtration values of the faces, then calls
+ * `block_simplex` on a `Simplex_handle` for this new simplex. If `block_simplex` returns true, the simplex is
+ * removed, otherwise it is kept. Note that the evaluation of `block_simplex` is a good time to update the
+ * filtration value of the simplex if you want a customized value. The algorithm then proceeds with the next
+ * candidate.
+ *
+ * @warning several candidates of the same dimension may be inserted simultaneously before calling `block_simplex`,
+ * so if you examine the complex in `block_simplex`, you may hit a few simplices of the same dimension that have not
+ * been vetted by `block_simplex` yet, or have already been rejected but not yet removed.
+ */
+ template< typename Blocker >
+ void expansion_with_blockers(int max_dim, Blocker block_simplex) {
+ // Loop must be from the end to the beginning, as higher dimension simplex are always on the left part of the tree
+ for (auto& simplex : boost::adaptors::reverse(root_.members())) {
+ if (has_children(&simplex)) {
+ siblings_expansion_with_blockers(simplex.second.children(), max_dim, max_dim - 1, block_simplex);
+ }
+ }
+ }
+
+ private:
+ /** \brief Recursive expansion with blockers of the simplex tree.*/
+ template< typename Blocker >
+ void siblings_expansion_with_blockers(Siblings* siblings, int max_dim, int k, Blocker block_simplex) {
+ if (dimension_ < max_dim - k) {
+ dimension_ = max_dim - k;
+ }
+ if (k == 0)
+ return;
+ // No need to go deeper
+ if (siblings->members().size() < 2)
+ return;
+ // Reverse loop starting before the last one for 'next' to be the last one
+ for (auto simplex = siblings->members().rbegin() + 1; simplex != siblings->members().rend(); simplex++) {
+ std::vector<std::pair<Vertex_handle, Node> > intersection;
+ for(auto next = siblings->members().rbegin(); next != simplex; next++) {
+ bool to_be_inserted = true;
+ Filtration_value filt = simplex->second.filtration();
+ // If all the boundaries are present, 'next' needs to be inserted
+ for (Simplex_handle border : boundary_simplex_range(simplex)) {
+ Simplex_handle border_child = find_child(border, next->first);
+ if (border_child == null_simplex()) {
+ to_be_inserted=false;
+ break;
+ }
+ filt = std::max(filt, filtration(border_child));
+ }
+ if (to_be_inserted) {
+ intersection.emplace_back(next->first, Node(nullptr, filt));
+ }
+ }
+ if (intersection.size() != 0) {
+ // Reverse the order to insert
+ Siblings * new_sib = new Siblings(siblings, // oncles
+ simplex->first, // parent
+ boost::adaptors::reverse(intersection)); // boost::container::ordered_unique_range_t
+ std::vector<Simplex_handle> blocked_new_sib_list;
+ // As all intersections are inserted, we can call the blocker function on all new_sib members
+ for (auto new_sib_member = new_sib->members().begin();
+ new_sib_member != new_sib->members().end();
+ new_sib_member++) {
+ bool blocker_result = block_simplex(new_sib_member);
+ // new_sib member has been blocked by the blocker function
+ // add it to the list to be removed - do not perform it while looping on it
+ if (blocker_result)
+ blocked_new_sib_list.push_back(new_sib_member);
+ }
+ bool removed = false;
+ for (auto& blocked_new_sib_member : blocked_new_sib_list){
+ removed = removed || remove_maximal_simplex(blocked_new_sib_member);
+ }
+ if (removed) {
+ // ensure the children property
+ simplex->second.assign_children(siblings);
+ } else {
+ // ensure recursive call
+ simplex->second.assign_children(new_sib);
+ siblings_expansion_with_blockers(new_sib, max_dim, k - 1, block_simplex);
+ }
+ } else {
+ // ensure the children property
+ simplex->second.assign_children(siblings);
+ }
+ }
+ }
+
+ /* \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given
+ * Vertex_handle if the Vertex_handle is found in the Simplex_handle children list.
+ * Returns null_simplex() if it does not exist
+ */
+ Simplex_handle find_child(Simplex_handle sh, Vertex_handle vh) const {
+ if (!has_children(sh))
+ return null_simplex();
+
+ Simplex_handle child = sh->second.children()->find(vh);
+ // Specific case of boost::flat_map does not find, returns boost::flat_map::end()
+ // in simplex tree we want a null_simplex()
+ if (child == sh->second.children()->members().end())
+ return null_simplex();
+
+ return child;
+ }
+
+ public:
/** \brief Write the hasse diagram of the simplicial complex in os.
*
* Each row in the file correspond to a simplex. A line is written:
@@ -1157,6 +1268,9 @@ class Simplex_tree {
* \post Some simplex tree functions require the filtration to be valid. `prune_above_filtration()`
* 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, `upper_bound_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);
@@ -1168,6 +1282,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;
});
@@ -1176,6 +1292,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.
@@ -1187,14 +1305,49 @@ class Simplex_tree {
return modified;
}
+ 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. `upper_bound_dimension()` and `set_dimension()` methods).
+ */
+ 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()) {
+#ifdef DEBUG_TRACES
+ for (auto vertex : simplex_vertex_range(sh)) {
+ std::cout << " " << vertex;
+ }
+ std::cout << std::endl;
+#endif // DEBUG_TRACES
+
+ int sh_dimension = dimension(sh);
+ if (sh_dimension >= dimension_)
+ // Stop browsing as soon as the dimension is reached, no need to go furter
+ return false;
+ new_dimension = std::max(new_dimension, sh_dimension);
+ }
+ dimension_ = new_dimension;
+ return true;
+ }
+
+
public:
/** \brief Remove a maximal simplex.
* @param[in] sh Simplex handle on the maximal simplex to remove.
+ * @return a boolean value that is an implementation detail, and that the user is supposed to ignore
* \pre Please check the simplex has no coface before removing it.
* \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 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, `upper_bound_dimension()` will return the old value, which remains a valid upper
+ * bound. If you care, you can call `dimension()` to recompute the exact dimension.
+ * \internal @return true if the leaf's branch has no other leaves (branch's children has been re-assigned), false otherwise.
*/
- void remove_maximal_simplex(Simplex_handle sh) {
+ bool remove_maximal_simplex(Simplex_handle sh) {
// Guarantee the simplex has no children
GUDHI_CHECK(!has_children(sh),
std::invalid_argument("Simplex_tree::remove_maximal_simplex - argument has children"));
@@ -1210,13 +1363,15 @@ 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;
+ return true;
}
+ return false;
}
private:
Vertex_handle null_vertex_;
- /** \brief Upper bound on the filtration values of the simplices.*/
- Filtration_value threshold_;
/** \brief Total number of simplices in the complex, without the empty simplex.*/
/** \brief Set of simplex tree Nodes representing the vertices.*/
Siblings root_;
@@ -1224,6 +1379,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.
@@ -1244,7 +1400,6 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
typedef Simplex_tree<T...> ST;
std::vector<typename ST::Vertex_handle> simplex;
typename ST::Filtration_value fil;
- typename ST::Filtration_value max_fil = 0;
int max_dim = -1;
while (read_simplex(is, simplex, fil)) {
// read all simplices in the file as a list of vertices
@@ -1253,15 +1408,11 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
if (max_dim < dim) {
max_dim = dim;
}
- if (max_fil < fil) {
- max_fil = fil;
- }
// insert every simplex in the simplex tree
st.insert_simplex(simplex, fil);
simplex.clear();
}
st.set_dimension(max_dim);
- st.set_filtration(max_fil);
return is;
}
diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt
index 17b0f2c2..8684ad2a 100644
--- a/src/Simplex_tree/test/CMakeLists.txt
+++ b/src/Simplex_tree/test/CMakeLists.txt
@@ -3,13 +3,29 @@ project(Simplex_tree_tests)
include(GUDHI_test_coverage)
+# Do not forget to copy test files in current binary dir
+file(COPY "simplex_tree_for_unit_test.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/)
+
add_executable ( Simplex_tree_test_unit simplex_tree_unit_test.cpp )
-target_link_libraries(Simplex_tree_test_unit ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+target_link_libraries(Simplex_tree_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
if (TBB_FOUND)
target_link_libraries(Simplex_tree_test_unit ${TBB_LIBRARIES})
endif()
-# Do not forget to copy test files in current binary dir
-file(COPY "simplex_tree_for_unit_test.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/)
-
gudhi_add_coverage_test(Simplex_tree_test_unit)
+
+add_executable ( Simplex_tree_remove_test_unit simplex_tree_remove_unit_test.cpp )
+target_link_libraries(Simplex_tree_remove_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+if (TBB_FOUND)
+ target_link_libraries(Simplex_tree_remove_test_unit ${TBB_LIBRARIES})
+endif()
+
+gudhi_add_coverage_test(Simplex_tree_remove_test_unit)
+
+add_executable ( Simplex_tree_iostream_operator_test_unit simplex_tree_iostream_operator_unit_test.cpp )
+target_link_libraries(Simplex_tree_iostream_operator_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+if (TBB_FOUND)
+ target_link_libraries(Simplex_tree_iostream_operator_test_unit ${TBB_LIBRARIES})
+endif()
+
+gudhi_add_coverage_test(Simplex_tree_iostream_operator_test_unit)
diff --git a/src/Simplex_tree/test/README b/src/Simplex_tree/test/README
index 21c3d871..df2ab89a 100644
--- a/src/Simplex_tree/test/README
+++ b/src/Simplex_tree/test/README
@@ -9,6 +9,6 @@ make
To launch with details:
***********************
-./SimplexTreeUT --report_level=detailed --log_level=all
+./Simplex_tree_test_unit --report_level=detailed --log_level=all
==> echo $? returns 0 in case of success (non-zero otherwise)
diff --git a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp
new file mode 100644
index 00000000..19ce3321
--- /dev/null
+++ b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp
@@ -0,0 +1,235 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <algorithm>
+#include <utility> // std::pair, std::make_pair
+#include <cmath> // float comparison
+#include <limits>
+#include <functional> // greater
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "simplex_tree"
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+// ^
+// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined.
+#include "gudhi/Simplex_tree.h"
+
+using namespace Gudhi;
+
+typedef boost::mpl::list<Simplex_tree<>, Simplex_tree<Simplex_tree_options_fast_persistence>> list_of_tested_variants;
+
+
+bool AreAlmostTheSame(float a, float b) {
+ return std::fabs(a - b) < std::numeric_limits<float>::epsilon();
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, list_of_tested_variants) {
+ using Simplex_handle = typename typeST::Simplex_handle;
+ // Construct the Simplex Tree with a 1-skeleton graph example
+ typeST simplex_tree;
+
+ simplex_tree.insert_simplex({0, 1}, 0.);
+ simplex_tree.insert_simplex({0, 2}, 1.);
+ simplex_tree.insert_simplex({0, 3}, 2.);
+ simplex_tree.insert_simplex({1, 2}, 3.);
+ simplex_tree.insert_simplex({1, 3}, 4.);
+ simplex_tree.insert_simplex({2, 3}, 5.);
+ simplex_tree.insert_simplex({2, 4}, 6.);
+ simplex_tree.insert_simplex({3, 6}, 7.);
+ simplex_tree.insert_simplex({4, 5}, 8.);
+ simplex_tree.insert_simplex({4, 6}, 9.);
+ simplex_tree.insert_simplex({5, 6}, 10.);
+ simplex_tree.insert_simplex({6}, 10.);
+
+ simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){
+ bool result = false;
+ std::cout << "Blocker on [";
+ // User can loop on the vertices from the given simplex_handle i.e.
+ for (auto vertex : simplex_tree.simplex_vertex_range(sh)) {
+ // We block the expansion, if the vertex '6' is in the given list of vertices
+ if (vertex == 6)
+ result = true;
+ std::cout << vertex << ", ";
+ }
+ std::cout << "] ( " << simplex_tree.filtration(sh);
+ // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries)
+ simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.);
+
+ std::cout << " + 1. ) = " << result << std::endl;
+
+ return result;
+ });
+
+ std::cout << "********************************************************************\n";
+ std::cout << "simplex_tree_expansion_with_blockers_3\n";
+ std::cout << "********************************************************************\n";
+ std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices";
+ std::cout << " - dimension " << simplex_tree.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ for (auto f_simplex : simplex_tree.filtration_simplex_range()) {
+ std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] ";
+ for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(simplex_tree.num_simplices() == 23);
+ BOOST_CHECK(simplex_tree.dimension() == 3);
+ // {4, 5, 6} shall be blocked
+ BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex());
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 7.));
+
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, list_of_tested_variants) {
+ using Simplex_handle = typename typeST::Simplex_handle;
+ // Construct the Simplex Tree with a 1-skeleton graph example
+ typeST simplex_tree;
+
+ simplex_tree.insert_simplex({0, 1}, 0.);
+ simplex_tree.insert_simplex({0, 2}, 1.);
+ simplex_tree.insert_simplex({0, 3}, 2.);
+ simplex_tree.insert_simplex({1, 2}, 3.);
+ simplex_tree.insert_simplex({1, 3}, 4.);
+ simplex_tree.insert_simplex({2, 3}, 5.);
+ simplex_tree.insert_simplex({2, 4}, 6.);
+ simplex_tree.insert_simplex({3, 6}, 7.);
+ simplex_tree.insert_simplex({4, 5}, 8.);
+ simplex_tree.insert_simplex({4, 6}, 9.);
+ simplex_tree.insert_simplex({5, 6}, 10.);
+ simplex_tree.insert_simplex({6}, 10.);
+
+ simplex_tree.expansion_with_blockers(2, [&](Simplex_handle sh){
+ bool result = false;
+ std::cout << "Blocker on [";
+ // User can loop on the vertices from the given simplex_handle i.e.
+ for (auto vertex : simplex_tree.simplex_vertex_range(sh)) {
+ // We block the expansion, if the vertex '6' is in the given list of vertices
+ if (vertex == 6)
+ result = true;
+ std::cout << vertex << ", ";
+ }
+ std::cout << "] ( " << simplex_tree.filtration(sh);
+ // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries)
+ simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.);
+
+ std::cout << " + 1. ) = " << result << std::endl;
+
+ return result;
+ });
+
+ std::cout << "********************************************************************\n";
+ std::cout << "simplex_tree_expansion_with_blockers_2\n";
+ std::cout << "********************************************************************\n";
+ std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices";
+ std::cout << " - dimension " << simplex_tree.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ for (auto f_simplex : simplex_tree.filtration_simplex_range()) {
+ std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] ";
+ for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(simplex_tree.num_simplices() == 22);
+ BOOST_CHECK(simplex_tree.dimension() == 2);
+ // {4, 5, 6} shall be blocked
+ BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex());
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.));
+ BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex());
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_variants) {
+ // Construct the Simplex Tree with a 1-skeleton graph example
+ typeST simplex_tree;
+
+ simplex_tree.insert_simplex({0, 1}, 0.);
+ simplex_tree.insert_simplex({0, 2}, 1.);
+ simplex_tree.insert_simplex({0, 3}, 2.);
+ simplex_tree.insert_simplex({1, 2}, 3.);
+ simplex_tree.insert_simplex({1, 3}, 4.);
+ simplex_tree.insert_simplex({2, 3}, 5.);
+ simplex_tree.insert_simplex({2, 4}, 6.);
+ simplex_tree.insert_simplex({3, 6}, 7.);
+ simplex_tree.insert_simplex({4, 5}, 8.);
+ simplex_tree.insert_simplex({4, 6}, 9.);
+ simplex_tree.insert_simplex({5, 6}, 10.);
+ simplex_tree.insert_simplex({6}, 10.);
+
+ simplex_tree.expansion(3);
+ std::cout << "********************************************************************\n";
+ std::cout << "simplex_tree_expansion_3\n";
+ std::cout << "********************************************************************\n";
+ std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices";
+ std::cout << " - dimension " << simplex_tree.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ for (auto f_simplex : simplex_tree.filtration_simplex_range()) {
+ std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] ";
+ for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(simplex_tree.num_simplices() == 24);
+ BOOST_CHECK(simplex_tree.dimension() == 3);
+
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 5.));
+
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_variants) {
+ // Construct the Simplex Tree with a 1-skeleton graph example
+ typeST simplex_tree;
+
+ simplex_tree.insert_simplex({0, 1}, 0.);
+ simplex_tree.insert_simplex({0, 2}, 1.);
+ simplex_tree.insert_simplex({0, 3}, 2.);
+ simplex_tree.insert_simplex({1, 2}, 3.);
+ simplex_tree.insert_simplex({1, 3}, 4.);
+ simplex_tree.insert_simplex({2, 3}, 5.);
+ simplex_tree.insert_simplex({2, 4}, 6.);
+ simplex_tree.insert_simplex({3, 6}, 7.);
+ simplex_tree.insert_simplex({4, 5}, 8.);
+ simplex_tree.insert_simplex({4, 6}, 9.);
+ simplex_tree.insert_simplex({5, 6}, 10.);
+ simplex_tree.insert_simplex({6}, 10.);
+
+ simplex_tree.expansion(2);
+
+ std::cout << "********************************************************************\n";
+ std::cout << "simplex_tree_expansion_2\n";
+ std::cout << "********************************************************************\n";
+ std::cout << "* The complex contains " << simplex_tree.num_simplices() << " simplices";
+ std::cout << " - dimension " << simplex_tree.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ for (auto f_simplex : simplex_tree.filtration_simplex_range()) {
+ std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] ";
+ for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex))
+ std::cout << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(simplex_tree.num_simplices() == 23);
+ BOOST_CHECK(simplex_tree.dimension() == 2);
+
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.));
+ BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.));
+ BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex());
+}
diff --git a/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp
new file mode 100644
index 00000000..ecb9f025
--- /dev/null
+++ b/src/Simplex_tree/test/simplex_tree_iostream_operator_unit_test.cpp
@@ -0,0 +1,136 @@
+#include <iostream>
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "simplex_tree_iostream_operator"
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+// ^
+// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined.
+#include "gudhi/Simplex_tree.h"
+
+using namespace Gudhi;
+
+struct MyOptions : Simplex_tree_options_full_featured {
+ // Not doing persistence, so we don't need those
+ static const bool store_key = false;
+ static const bool store_filtration = false;
+ // I have few vertices
+ typedef short Vertex_handle;
+};
+
+typedef boost::mpl::list<Simplex_tree<>,
+ Simplex_tree<Simplex_tree_options_fast_persistence>
+ > list_of_tested_variants;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(iostream_operator, Stree_type, list_of_tested_variants) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "SIMPLEX TREE IOSTREAM OPERATOR" << std::endl;
+
+ Stree_type st;
+
+ st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.0);
+ st.insert_simplex_and_subfaces({3, 4, 5}, 3.0);
+ st.insert_simplex_and_subfaces({3, 0}, 2.0);
+ st.insert_simplex_and_subfaces({2, 1, 0}, 3.0);
+
+ st.initialize_filtration();
+ // Display the Simplex_tree
+ std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = "
+ << st.dimension() << std::endl;
+ std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
+ for (auto f_simplex : st.filtration_simplex_range()) {
+ std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
+ for (auto vertex : st.simplex_vertex_range(f_simplex)) {
+ std::cout << (int) vertex << " ";
+ }
+ std::cout << std::endl;
+ }
+
+ // st:
+ // 1 6
+ // o---o
+ // /X\7/
+ // o---o---o---o
+ // 2 0 3\X/4
+ // o
+ // 5
+ std::string iostream_file("simplex_tree_for_iostream_operator_unit_test.txt");
+ std::ofstream simplex_tree_ostream(iostream_file.c_str());
+ simplex_tree_ostream << st;
+ simplex_tree_ostream.close();
+
+ Stree_type read_st;
+ std::ifstream simplex_tree_istream(iostream_file.c_str());
+ simplex_tree_istream >> read_st;
+
+ // Display the Simplex_tree
+ std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = "
+ << read_st.dimension() << std::endl;
+ std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
+ for (auto f_simplex : read_st.filtration_simplex_range()) {
+ std::cout << " " << "[" << read_st.filtration(f_simplex) << "] ";
+ for (auto vertex : read_st.simplex_vertex_range(f_simplex)) {
+ std::cout << (int) vertex << " ";
+ }
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(st == read_st);
+}
+
+
+BOOST_AUTO_TEST_CASE(mini_iostream_operator) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "MINI SIMPLEX TREE IOSTREAM OPERATOR" << std::endl;
+
+ Simplex_tree<MyOptions> st;
+
+ st.insert_simplex_and_subfaces({0, 1, 6, 7});
+ st.insert_simplex_and_subfaces({3, 4, 5});
+ st.insert_simplex_and_subfaces({3, 0});
+ st.insert_simplex_and_subfaces({2, 1, 0});
+
+ st.initialize_filtration();
+ // Display the Simplex_tree
+ std::cout << "The ORIGINAL complex contains " << st.num_simplices() << " simplices - dimension = "
+ << st.dimension() << std::endl;
+ for (auto f_simplex : st.filtration_simplex_range()) {
+ std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
+ for (auto vertex : st.simplex_vertex_range(f_simplex)) {
+ std::cout << (int) vertex << " ";
+ }
+ std::cout << std::endl;
+ }
+
+ // st:
+ // 1 6
+ // o---o
+ // /X\7/
+ // o---o---o---o
+ // 2 0 3\X/4
+ // o
+ // 5
+ std::string iostream_file("simplex_tree_for_iostream_operator_unit_test.txt");
+ std::ofstream simplex_tree_ostream(iostream_file.c_str());
+ simplex_tree_ostream << st;
+ simplex_tree_ostream.close();
+
+ Simplex_tree<MyOptions> read_st;
+ std::ifstream simplex_tree_istream(iostream_file.c_str());
+ simplex_tree_istream >> read_st;
+
+ // Display the Simplex_tree
+ std::cout << "The READ complex contains " << read_st.num_simplices() << " simplices - dimension = "
+ << read_st.dimension() << std::endl;
+ std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
+ for (auto f_simplex : read_st.filtration_simplex_range()) {
+ std::cout << " " << "[" << read_st.filtration(f_simplex) << "] ";
+ for (auto vertex : read_st.simplex_vertex_range(f_simplex)) {
+ std::cout << (int) vertex << " ";
+ }
+ std::cout << std::endl;
+ }
+
+ BOOST_CHECK(st == read_st);
+}
diff --git a/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp
new file mode 100644
index 00000000..dc37375c
--- /dev/null
+++ b/src/Simplex_tree/test/simplex_tree_remove_unit_test.cpp
@@ -0,0 +1,427 @@
+#include <iostream>
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "simplex_tree_remove"
+#include <boost/test/unit_test.hpp>
+
+// ^
+// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined.
+#include "gudhi/Simplex_tree.h"
+
+using namespace Gudhi;
+
+struct MyOptions : Simplex_tree_options_full_featured {
+ // Not doing persistence, so we don't need those
+ static const bool store_key = false;
+ static const bool store_filtration = false;
+ // I have few vertices
+ typedef short Vertex_handle;
+};
+
+using Mini_stree = Simplex_tree<MyOptions>;
+using Stree = Simplex_tree<>;
+
+BOOST_AUTO_TEST_CASE(remove_maximal_simplex) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl;
+
+ Mini_stree st;
+
+ st.insert_simplex_and_subfaces({0, 1, 6, 7});
+ st.insert_simplex_and_subfaces({3, 4, 5});
+
+ // Constructs a copy at this state for further test purpose
+ Mini_stree st_pruned = st;
+
+ st.insert_simplex_and_subfaces({3, 0});
+ st.insert_simplex_and_subfaces({2, 1, 0});
+
+ // Constructs a copy at this state for further test purpose
+ Mini_stree st_complete = st;
+ // st_complete and st:
+ // 1 6
+ // o---o
+ // /X\7/
+ // o---o---o---o
+ // 2 0 3\X/4
+ // o
+ // 5
+ // st_pruned:
+ // 1 6
+ // o---o
+ // \7/
+ // o o---o
+ // 0 3\X/4
+ // o
+ // 5
+
+#ifdef GUDHI_DEBUG
+ std::cout << "Check exception throw in debug mode" << std::endl;
+ // throw excpt because sh has children
+ BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument);
+ BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument);
+ BOOST_CHECK(st == st_complete);
+#endif
+ std::cout << "st.remove_maximal_simplex({0, 2})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 2}));
+ std::cout << "st.remove_maximal_simplex({0, 1, 2})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 1, 2}));
+ std::cout << "st.remove_maximal_simplex({1, 2})" << std::endl;
+ st.remove_maximal_simplex(st.find({1, 2}));
+ std::cout << "st.remove_maximal_simplex({2})" << std::endl;
+ st.remove_maximal_simplex(st.find({2}));
+ std::cout << "st.remove_maximal_simplex({3})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 3}));
+
+ BOOST_CHECK(st == st_pruned);
+ // Remove all, but as the simplex tree is not storing filtration, there is no modification
+ st.prune_above_filtration(0.0);
+ BOOST_CHECK(st == st_pruned);
+
+ Mini_stree st_wo_seven;
+
+ st_wo_seven.insert_simplex_and_subfaces({0, 1, 6});
+ st_wo_seven.insert_simplex_and_subfaces({3, 4, 5});
+ // st_wo_seven:
+ // 1 6
+ // o---o
+ // \X/
+ // o o---o
+ // 0 3\X/4
+ // o
+ // 5
+
+ // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not)
+ std::cout << "st.remove_maximal_simplex({0, 1, 6, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 1, 6, 7}));
+ std::cout << "st.remove_maximal_simplex({0, 1, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 1, 7}));
+ std::cout << "st.remove_maximal_simplex({0, 6, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 6, 7}));
+ std::cout << "st.remove_maximal_simplex({0, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({0, 7}));
+ std::cout << "st.remove_maximal_simplex({1, 6, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({1, 6, 7}));
+ std::cout << "st.remove_maximal_simplex({1, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({1, 7}));
+ std::cout << "st.remove_maximal_simplex({6, 7})" << std::endl;
+ st.remove_maximal_simplex(st.find({6, 7}));
+ std::cout << "st.remove_maximal_simplex({7})" << std::endl;
+ st.remove_maximal_simplex(st.find({7}));
+
+ std::cout << "st.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl;
+ BOOST_CHECK(st.upper_bound_dimension() == 3);
+
+ // 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);
+}
+
+BOOST_AUTO_TEST_CASE(auto_dimension_set) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "DIMENSION ON REMOVE MAXIMAL SIMPLEX" << std::endl;
+
+ Mini_stree st;
+
+ st.insert_simplex_and_subfaces({0, 1, 2});
+ st.insert_simplex_and_subfaces({0, 1, 3});
+ st.insert_simplex_and_subfaces({1, 2, 3, 4});
+ st.insert_simplex_and_subfaces({1, 2, 3, 5});
+ 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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);
+
+
+ // Reset with the correct value
+ st.set_dimension(3);
+ 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.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.upper_bound_dimension()=" << st.upper_bound_dimension() << std::endl;
+ BOOST_CHECK(st.upper_bound_dimension() == 6);
+ BOOST_CHECK(st.dimension() == 5);
+
+}
+
+BOOST_AUTO_TEST_CASE(prune_above_filtration) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "PRUNE ABOVE FILTRATION" << std::endl;
+
+ Stree st;
+
+ st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0);
+ st.insert_simplex_and_subfaces({3, 4, 5}, 2.0);
+
+ // Constructs a copy at this state for further test purpose
+ Stree st_pruned = st;
+ st_pruned.initialize_filtration(); // reset
+
+ st.insert_simplex_and_subfaces({3, 0}, 3.0);
+ st.insert_simplex_and_subfaces({2, 1, 0}, 4.0);
+
+ // Constructs a copy at this state for further test purpose
+ Stree st_complete = st;
+ // st_complete and st:
+ // 1 6
+ // o---o
+ // /X\7/
+ // o---o---o---o
+ // 2 0 3\X/4
+ // o
+ // 5
+ // st_pruned:
+ // 1 6
+ // o---o
+ // \7/
+ // o o---o
+ // 0 3\X/4
+ // o
+ // 5
+
+ bool simplex_is_changed = false;
+ // Check the no action cases
+ // greater than initial filtration value
+ simplex_is_changed = st.prune_above_filtration(10.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ BOOST_CHECK(st == st_complete);
+ BOOST_CHECK(!simplex_is_changed);
+ // equal to initial filtration value
+ simplex_is_changed = st.prune_above_filtration(6.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ BOOST_CHECK(st == st_complete);
+ BOOST_CHECK(!simplex_is_changed);
+ // lower than initial filtration value, but still greater than the maximum filtration value
+ simplex_is_changed = st.prune_above_filtration(5.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ BOOST_CHECK(st == st_complete);
+ BOOST_CHECK(!simplex_is_changed);
+
+ // Display the Simplex_tree
+ std::cout << "The complex contains " << st.num_simplices() << " simplices";
+ std::cout << " - dimension " << st.dimension() << std::endl;
+ std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
+ for (auto f_simplex : st.filtration_simplex_range()) {
+ std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
+ for (auto vertex : st.simplex_vertex_range(f_simplex)) {
+ std::cout << (int) vertex << " ";
+ }
+ std::cout << std::endl;
+ }
+
+ // Check the pruned cases
+ simplex_is_changed = st.prune_above_filtration(2.5);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ BOOST_CHECK(st == st_pruned);
+ BOOST_CHECK(simplex_is_changed);
+
+ // Display the Simplex_tree
+ std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices";
+ std::cout << " - dimension " << st.dimension() << std::endl;
+
+ simplex_is_changed = st.prune_above_filtration(2.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+
+ std::cout << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices";
+ std::cout << " - dimension " << st.dimension() << std::endl;
+
+ BOOST_CHECK(st == st_pruned);
+ BOOST_CHECK(!simplex_is_changed);
+
+ 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 << " - upper_bound_dimension " << st.upper_bound_dimension() << std::endl;
+ BOOST_CHECK(st.upper_bound_dimension() == 3);
+
+ 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);
+
+ // Test case to the limit
+ simplex_is_changed = st.prune_above_filtration(-1.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ BOOST_CHECK(st == st_empty);
+ BOOST_CHECK(!simplex_is_changed);
+}
+
+BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl;
+
+ Mini_stree st;
+
+ st.insert_simplex_and_subfaces({0, 1, 6, 7});
+ st.insert_simplex_and_subfaces({3, 4, 5});
+ st.insert_simplex_and_subfaces({3, 0});
+ st.insert_simplex_and_subfaces({2, 1, 0});
+
+ // st:
+ // 1 6
+ // o---o
+ // /X\7/
+ // o---o---o---o
+ // 2 0 3\X/4
+ // o
+ // 5
+
+ st.initialize_filtration();
+
+ // Display the Simplex_tree
+ std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
+ BOOST_CHECK(st.num_simplices() == 27);
+
+ // Test case to the limit - With these options, there is no filtration, which means filtration is 0
+ bool simplex_is_changed = st.prune_above_filtration(1.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ // Display the Simplex_tree
+ std::cout << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl;
+ BOOST_CHECK(!simplex_is_changed);
+ BOOST_CHECK(st.num_simplices() == 27);
+
+ simplex_is_changed = st.prune_above_filtration(0.0);
+ 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::endl;
+ BOOST_CHECK(!simplex_is_changed);
+ BOOST_CHECK(st.num_simplices() == 27);
+
+ // Test case to the limit
+ simplex_is_changed = st.prune_above_filtration(-1.0);
+ if (simplex_is_changed)
+ st.initialize_filtration();
+ // Display the Simplex_tree
+ std::cout << "The complex pruned at -1.0 contains " << st.num_simplices() << " simplices" << std::endl;
+ BOOST_CHECK(simplex_is_changed);
+ BOOST_CHECK(st.num_simplices() == 0);
+
+ // Display the Simplex_tree
+ std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
+
+}
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index b06d7ec9..580d610a 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -26,7 +26,6 @@ void test_empty_simplex_tree(typeST& tst) {
typedef typename typeST::Vertex_handle Vertex_handle;
const Vertex_handle DEFAULT_VERTEX_VALUE = Vertex_handle(- 1);
BOOST_CHECK(tst.null_vertex() == DEFAULT_VERTEX_VALUE);
- BOOST_CHECK(tst.filtration() == 0.0);
BOOST_CHECK(tst.num_vertices() == (size_t) 0);
BOOST_CHECK(tst.num_simplices() == (size_t) 0);
typename typeST::Siblings* STRoot = tst.root();
@@ -98,12 +97,11 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_from_file, typeST, list_of_tested_var
// Display the Simplex_tree
std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
- std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl;
+ std::cout << " - dimension " << st.dimension() << std::endl;
// Check
BOOST_CHECK(st.num_simplices() == 143353);
BOOST_CHECK(st.dimension() == 3);
- BOOST_CHECK(AreAlmostTheSame(st.filtration(), 0.4));
int previous_size = 0;
for (auto f_simplex : st.filtration_simplex_range()) {
@@ -147,7 +145,6 @@ void test_simplex_tree_insert_returns_true(const typePairSimplexBool& returnValu
}
// Global variables
-double max_fil = 0.0;
int dim_max = -1;
template<class typeST, class Filtration_value>
@@ -158,15 +155,8 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons
std::cout << " set_and_test_simplex_tree_dim_fil - dim_max=" << dim_max
<< std::endl;
}
- if (fil > max_fil) {
- max_fil = fil;
- simplexTree.set_filtration(max_fil);
- std::cout << " set_and_test_simplex_tree_dim_fil - max_fil=" << max_fil
- << std::endl;
- }
BOOST_CHECK(simplexTree.dimension() == dim_max);
- BOOST_CHECK(AreAlmostTheSame(simplexTree.filtration(), max_fil));
// Another way to count simplices:
size_t num_simp = 0;
@@ -190,7 +180,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var
const Filtration_value FOURTH_FILTRATION_VALUE = 0.4;
// reset since we run the test several times
dim_max = -1;
- max_fil = 0.0;
// TEST OF INSERTION
std::cout << "********************************************************************" << std::endl;
@@ -308,9 +297,9 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var
// Simplex_handle = boost::container::flat_map< typeST::Vertex_handle, Node >::iterator
typename typeST::Simplex_handle shReturned = returnValue.first;
BOOST_CHECK(shReturned == typename typeST::Simplex_handle(nullptr));
+ std::cout << "st.num_vertices()=" << st.num_vertices() << std::endl;
BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !!
BOOST_CHECK(st.dimension() == dim_max);
- BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil));
// ++ ELEVENTH
std::cout << " - INSERT (2,1,0) (already inserted)" << std::endl;
@@ -325,7 +314,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var
BOOST_CHECK(shReturned == typename typeST::Simplex_handle(nullptr));
BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !!
BOOST_CHECK(st.dimension() == dim_max);
- BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil));
/* Inserted simplex: */
/* 1 */
@@ -365,7 +353,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var
// Display the Simplex_tree - Can not be done in the middle of 2 inserts
std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
- std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl;
+ std::cout << " - dimension " << st.dimension() << std::endl;
std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
for (auto f_simplex : st.filtration_simplex_range()) {
std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
@@ -575,7 +563,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_o
// Display the Simplex_tree - Can not be done in the middle of 2 inserts
std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
- std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl;
+ std::cout << " - dimension " << st.dimension() << std::endl;
std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
for (auto f_simplex : st.filtration_simplex_range()) {
std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
@@ -630,9 +618,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_var
/* o */
/* 5 */
- // FIXME
- st.set_dimension(3);
-
std::vector<typename typeST::Vertex_handle> simplex_result;
std::vector<typename typeST::Simplex_handle> result;
std::cout << "First test - Star of (3):" << std::endl;
@@ -729,9 +714,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_
/* o */
/* 5 */
- // FIXME
- st.set_dimension(3);
-
std::cout << "Printing st - address = " << &st << std::endl;
// Copy constructor
@@ -756,7 +738,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_
typeST st_empty;
// Check st has been emptied by the move
BOOST_CHECK(st == st_empty);
- BOOST_CHECK(st.filtration() == 0);
BOOST_CHECK(st.dimension() == -1);
BOOST_CHECK(st.num_simplices() == 0);
BOOST_CHECK(st.num_vertices() == (size_t)0);
@@ -882,271 +863,3 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) {
BOOST_CHECK(st == st_other_copy);
}
-
-struct MyOptions : Simplex_tree_options_full_featured {
- // Not doing persistence, so we don't need those
- static const bool store_key = false;
- static const bool store_filtration = false;
- // I have few vertices
- typedef short Vertex_handle;
-};
-
-BOOST_AUTO_TEST_CASE(remove_maximal_simplex) {
- std::cout << "********************************************************************" << std::endl;
- std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl;
-
-
- typedef Simplex_tree<MyOptions> miniST;
- miniST st;
-
- // FIXME
- st.set_dimension(3);
-
- st.insert_simplex_and_subfaces({0, 1, 6, 7});
- st.insert_simplex_and_subfaces({3, 4, 5});
-
- // Constructs a copy at this state for further test purpose
- miniST st_pruned = st;
-
- st.insert_simplex_and_subfaces({3, 0});
- st.insert_simplex_and_subfaces({2, 1, 0});
-
- // Constructs a copy at this state for further test purpose
- miniST st_complete = st;
- // st_complete and st:
- // 1 6
- // o---o
- // /X\7/
- // o---o---o---o
- // 2 0 3\X/4
- // o
- // 5
- // st_pruned:
- // 1 6
- // o---o
- // \7/
- // o o---o
- // 0 3\X/4
- // o
- // 5
-
-#ifdef GUDHI_DEBUG
- std::cout << "Check exception throw in debug mode" << std::endl;
- // throw excpt because sh has children
- BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({0, 1, 6})), std::invalid_argument);
- BOOST_CHECK_THROW (st.remove_maximal_simplex(st.find({3})), std::invalid_argument);
- BOOST_CHECK(st == st_complete);
-#endif
-
- st.remove_maximal_simplex(st.find({0, 2}));
- st.remove_maximal_simplex(st.find({0, 1, 2}));
- st.remove_maximal_simplex(st.find({1, 2}));
- st.remove_maximal_simplex(st.find({2}));
- st.remove_maximal_simplex(st.find({0, 3}));
-
- BOOST_CHECK(st == st_pruned);
- // Remove all, but as the simplex tree is not storing filtration, there is no modification
- st.prune_above_filtration(0.0);
- BOOST_CHECK(st == st_pruned);
-
- miniST st_wo_seven;
- // FIXME
- st_wo_seven.set_dimension(3);
-
- st_wo_seven.insert_simplex_and_subfaces({0, 1, 6});
- st_wo_seven.insert_simplex_and_subfaces({3, 4, 5});
- // st_wo_seven:
- // 1 6
- // o---o
- // \X/
- // o o---o
- // 0 3\X/4
- // o
- // 5
-
- // Remove all 7 to test the both remove_maximal_simplex cases (when _members is empty or not)
- st.remove_maximal_simplex(st.find({0, 1, 6, 7}));
- st.remove_maximal_simplex(st.find({0, 1, 7}));
- st.remove_maximal_simplex(st.find({0, 6, 7}));
- st.remove_maximal_simplex(st.find({0, 7}));
- st.remove_maximal_simplex(st.find({1, 6, 7}));
- st.remove_maximal_simplex(st.find({1, 7}));
- st.remove_maximal_simplex(st.find({6, 7}));
- st.remove_maximal_simplex(st.find({7}));
-
- BOOST_CHECK(st == st_wo_seven);
-}
-
-BOOST_AUTO_TEST_CASE(prune_above_filtration) {
- std::cout << "********************************************************************" << std::endl;
- std::cout << "PRUNE ABOVE FILTRATION" << std::endl;
- typedef Simplex_tree<> typeST;
- typeST st;
-
- // FIXME
- st.set_dimension(3);
-
- st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0);
- st.insert_simplex_and_subfaces({3, 4, 5}, 2.0);
-
- // Constructs a copy at this state for further test purpose
- typeST st_pruned = st;
- st_pruned.initialize_filtration(); // reset
-
- st.insert_simplex_and_subfaces({3, 0}, 3.0);
- st.insert_simplex_and_subfaces({2, 1, 0}, 4.0);
-
- // Constructs a copy at this state for further test purpose
- typeST st_complete = st;
- // st_complete and st:
- // 1 6
- // o---o
- // /X\7/
- // o---o---o---o
- // 2 0 3\X/4
- // o
- // 5
- // st_pruned:
- // 1 6
- // o---o
- // \7/
- // o o---o
- // 0 3\X/4
- // o
- // 5
-
- bool simplex_is_changed = false;
- // Check the no action cases
- // greater than initial filtration value
- simplex_is_changed = st.prune_above_filtration(10.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- BOOST_CHECK(st == st_complete);
- BOOST_CHECK(!simplex_is_changed);
- // equal to initial filtration value
- simplex_is_changed = st.prune_above_filtration(6.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- BOOST_CHECK(st == st_complete);
- BOOST_CHECK(!simplex_is_changed);
- // lower than initial filtration value, but still greater than the maximum filtration value
- simplex_is_changed = st.prune_above_filtration(5.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- BOOST_CHECK(st == st_complete);
- BOOST_CHECK(!simplex_is_changed);
-
- // Display the Simplex_tree
- std::cout << "The complex contains " << st.num_simplices() << " simplices";
- std::cout << " - dimension " << st.dimension() << std::endl;
- std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl;
- for (auto f_simplex : st.filtration_simplex_range()) {
- std::cout << " " << "[" << st.filtration(f_simplex) << "] ";
- for (auto vertex : st.simplex_vertex_range(f_simplex)) {
- std::cout << (int) vertex << " ";
- }
- std::cout << std::endl;
- }
-
- // Check the pruned cases
- simplex_is_changed = st.prune_above_filtration(2.5);
- if (simplex_is_changed)
- st.initialize_filtration();
- BOOST_CHECK(st == st_pruned);
- BOOST_CHECK(simplex_is_changed);
-
- // Display the Simplex_tree
- std::cout << "The complex pruned at 2.5 contains " << st.num_simplices() << " simplices";
- std::cout << " - dimension " << st.dimension() << std::endl;
-
- simplex_is_changed = st.prune_above_filtration(2.0);
- if (simplex_is_changed)
- st.initialize_filtration();
-
- std::cout << "The complex pruned at 2.0 contains " << st.num_simplices() << " simplices";
- std::cout << " - dimension " << st.dimension() << std::endl;
-
- BOOST_CHECK(st == st_pruned);
- BOOST_CHECK(!simplex_is_changed);
-
- typeST st_empty;
- // FIXME
- st_empty.set_dimension(3);
- simplex_is_changed = st.prune_above_filtration(0.0);
- 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 == st_empty);
- BOOST_CHECK(simplex_is_changed);
-
- // Test case to the limit
- simplex_is_changed = st.prune_above_filtration(-1.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- BOOST_CHECK(st == st_empty);
- BOOST_CHECK(!simplex_is_changed);
-}
-
-BOOST_AUTO_TEST_CASE(mini_prune_above_filtration) {
- std::cout << "********************************************************************" << std::endl;
- std::cout << "MINI PRUNE ABOVE FILTRATION" << std::endl;
- typedef Simplex_tree<MyOptions> typeST;
- typeST st;
-
- // FIXME
- st.set_dimension(3);
-
- st.insert_simplex_and_subfaces({0, 1, 6, 7});
- st.insert_simplex_and_subfaces({3, 4, 5});
- st.insert_simplex_and_subfaces({3, 0});
- st.insert_simplex_and_subfaces({2, 1, 0});
-
- // st:
- // 1 6
- // o---o
- // /X\7/
- // o---o---o---o
- // 2 0 3\X/4
- // o
- // 5
-
- st.initialize_filtration();
-
- // Display the Simplex_tree
- std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
- BOOST_CHECK(st.num_simplices() == 27);
-
- // Test case to the limit - With these options, there is no filtration, which means filtration is 0
- bool simplex_is_changed = st.prune_above_filtration(1.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- // Display the Simplex_tree
- std::cout << "The complex pruned at 1.0 contains " << st.num_simplices() << " simplices" << std::endl;
- BOOST_CHECK(!simplex_is_changed);
- BOOST_CHECK(st.num_simplices() == 27);
-
- simplex_is_changed = st.prune_above_filtration(0.0);
- 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::endl;
- BOOST_CHECK(!simplex_is_changed);
- BOOST_CHECK(st.num_simplices() == 27);
-
- // Test case to the limit
- simplex_is_changed = st.prune_above_filtration(-1.0);
- if (simplex_is_changed)
- st.initialize_filtration();
- // Display the Simplex_tree
- std::cout << "The complex pruned at -1.0 contains " << st.num_simplices() << " simplices" << std::endl;
- BOOST_CHECK(simplex_is_changed);
- BOOST_CHECK(st.num_simplices() == 0);
-
- // Display the Simplex_tree
- std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl;
-
-} \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 21:36:43 +0000