summaryrefslogtreecommitdiff
path: root/src/Simplex_tree
diff options
context:
space:
mode:
Diffstat (limited to 'src/Simplex_tree')
-rw-r--r--src/Simplex_tree/concept/SimplexKey.h2
-rw-r--r--src/Simplex_tree/concept/SimplexTreeOptions.h10
-rw-r--r--src/Simplex_tree/doc/Intro_simplex_tree.h85
-rw-r--r--src/Simplex_tree/doc/Simplex_tree_representation.pngbin0 -> 39217 bytes
-rw-r--r--src/Simplex_tree/example/CMakeLists.txt29
-rw-r--r--src/Simplex_tree/example/README4
-rw-r--r--src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp (renamed from src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp)31
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree.h289
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h84
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h6
-rw-r--r--src/Simplex_tree/test/CMakeLists.txt9
-rw-r--r--src/Simplex_tree/test/simplex_tree_unit_test.cpp487
12 files changed, 854 insertions, 182 deletions
diff --git a/src/Simplex_tree/concept/SimplexKey.h b/src/Simplex_tree/concept/SimplexKey.h
index 7fdbdd84..9fbed401 100644
--- a/src/Simplex_tree/concept/SimplexKey.h
+++ b/src/Simplex_tree/concept/SimplexKey.h
@@ -22,7 +22,7 @@
/** \brief Key type used as simplex identifier.
*
- * Must be a signed integer type.
+ * Must be an integer type.
*/
struct SimplexKey {};
diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h
index a50a2bf1..89acdc18 100644
--- a/src/Simplex_tree/concept/SimplexTreeOptions.h
+++ b/src/Simplex_tree/concept/SimplexTreeOptions.h
@@ -31,11 +31,13 @@ struct SimplexTreeOptions {
typedef VertexHandle Vertex_handle;
/// Must be comparable with operator<.
typedef FiltrationValue Filtration_value;
- /// Must be a signed integer type.
+ /// Must be an integer type.
typedef SimplexKey Simplex_key;
/// If true, each simplex has extra storage for one `Simplex_key`. Necessary for `Persistent_cohomology`.
- static constexpr bool store_key;
- /// If true, each simplex has extra storage for one `Filtration_value`, and this value is propagated by operations like `Gudhi::Simplex_tree<SimplexTreeOptions>::expansion`. Without it, `Persistent_cohomology` degenerates to computing usual (non-persistent) cohomology.
- static constexpr bool store_filtration;
+ static const bool store_key;
+ /// If true, each simplex has extra storage for one `Filtration_value`, and this value is propagated by operations like `Gudhi::Simplex_tree::expansion`. Without it, `Persistent_cohomology` degenerates to computing usual (non-persistent) cohomology.
+ static const bool store_filtration;
+ /// If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1, without any hole.
+ static constexpr bool contiguous_vertices;
};
diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h
new file mode 100644
index 00000000..940dd694
--- /dev/null
+++ b/src/Simplex_tree/doc/Intro_simplex_tree.h
@@ -0,0 +1,85 @@
+/* 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): Clément Maria
+ *
+ * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France)
+ *
+ * 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/>.
+ */
+
+#ifndef DOC_SIMPLEX_TREE_INTRO_SIMPLEX_TREE_H_
+#define DOC_SIMPLEX_TREE_INTRO_SIMPLEX_TREE_H_
+
+// needs namespace for Doxygen to link on classes
+namespace Gudhi {
+
+
+/** \defgroup simplex_tree Filtered Complexes
+ * @{
+ * \author Cl&eacute;ment Maria
+ *
+ * A simplicial complex \f$\mathbf{K}\f$ on a set of vertices \f$V = \{1, \cdots ,|V|\}\f$ is a collection of
+ * implices \f$\{\sigma\}\f$, \f$\sigma \subseteq V\f$ such that
+ * \f$\tau \subseteq \sigma \in \mathbf{K} \rightarrow \tau \in \mathbf{K}\f$. The dimension \f$n=|\sigma|-1\f$ of
+ * \f$\sigma\f$ is its number of elements minus \f$1\f$.
+ *
+ * A filtration of a simplicial complex is a function \f$f:\mathbf{K} \rightarrow \mathbb{R}\f$ satisfying
+ * \f$f(\tau)\leq f(\sigma)\f$ whenever \f$\tau \subseteq \sigma\f$. Ordering the simplices by increasing filtration
+ * values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an
+ * indexing scheme.
+ *
+ * \section filteredcomplexesimplementation Implementations
+ * \subsection filteredcomplexessimplextree Simplex tree
+ * There are two implementation of complexes. The first on is the Simplex_tree data structure. The simplex tree is an
+ * efficient and flexible data structure for representing general (filtered) simplicial complexes. The data structure
+ * is described in \cite boissonnatmariasimplextreealgorithmica
+ * \image html "Simplex_tree_representation.png" "Simplex tree representation"
+ *
+ * \subsubsection filteredcomplexessimplextreeexamples Examples
+ *
+ * Here is a list of simplex tree examples :
+ * \li <a href="_simplex_tree_2simple_simplex_tree_8cpp-example.html">
+ * Simplex_tree/simple_simplex_tree.cpp</a> - Simple simplex tree construction and basic function use.
+ *
+ * \li <a href="_simplex_tree_2simplex_tree_from_cliques_of_graph_8cpp-example.html">
+ * Simplex_tree/simplex_tree_from_cliques_of_graph.cpp</a> - Simplex tree construction from cliques of graph read in
+ * a file.
+ *
+ * Simplex tree construction with \f$\mathbb{Z}/3\mathbb{Z}\f$ coefficients on weighted graph Klein bottle file:
+ * \code $> ./simplex_tree_from_cliques_of_graph ../../data/points/Klein_bottle_complex.txt 3 \endcode
+ * \code Insert the 1-skeleton in the simplex tree in 0.000404 s.
+max_dim = 3
+Expand the simplex tree in 3.8e-05 s.
+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)
+ *
+ *
+ * \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
+ * compact and harder to construct from scratch.
+ *
+ * \copyright GNU General Public License v3.
+ * @}
+ */
+
+} // namespace Gudhi
+
+#endif // DOC_SIMPLEX_TREE_INTRO_SIMPLEX_TREE_H_
diff --git a/src/Simplex_tree/doc/Simplex_tree_representation.png b/src/Simplex_tree/doc/Simplex_tree_representation.png
new file mode 100644
index 00000000..9d401520
--- /dev/null
+++ b/src/Simplex_tree/doc/Simplex_tree_representation.png
Binary files differ
diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt
index c70cfe35..e5285591 100644
--- a/src/Simplex_tree/example/CMakeLists.txt
+++ b/src/Simplex_tree/example/CMakeLists.txt
@@ -1,11 +1,19 @@
cmake_minimum_required(VERSION 2.6)
-project(GUDHISimplexTreeFromFile)
+project(Simplex_tree_examples)
add_executable ( simplex_tree_from_cliques_of_graph simplex_tree_from_cliques_of_graph.cpp )
-add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 2)
-add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 3)
+if (TBB_FOUND)
+ target_link_libraries(simplex_tree_from_cliques_of_graph ${TBB_LIBRARIES})
+endif()
+add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph
+ ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/Klein_bottle_complex.fsc 2)
+add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph
+ ${CMAKE_SOURCE_DIR}/data/filtered_simplicial_complex/Klein_bottle_complex.fsc 3)
add_executable ( simple_simplex_tree simple_simplex_tree.cpp )
+if (TBB_FOUND)
+ target_link_libraries(simple_simplex_tree ${TBB_LIBRARIES})
+endif()
add_test(simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/simple_simplex_tree)
add_executable ( mini_simplex_tree mini_simplex_tree.cpp )
@@ -14,11 +22,12 @@ add_test(mini_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/mini_simplex_tree)
# An example with Simplex-tree using CGAL alpha_shapes_3
if(GMP_FOUND AND CGAL_FOUND)
- message("CGAL_lib = ${CGAL_LIBRARIES_DIR}")
- message("GMP_LIBRARIES = ${GMP_LIBRARIES}")
- INCLUDE_DIRECTORIES(${GMP_INCLUDE_DIR})
- INCLUDE_DIRECTORIES(${CGAL_INCLUDE_DIRS})
- add_executable ( simplex_tree_from_alpha_shapes_3 simplex_tree_from_alpha_shapes_3.cpp )
- target_link_libraries(simplex_tree_from_alpha_shapes_3 ${GMP_LIBRARIES} ${CGAL_LIBRARY})
- add_test(simplex_tree_from_alpha_shapes_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_alpha_shapes_3 ${CMAKE_SOURCE_DIR}/data/points/bunny_5000)
+ add_executable ( alpha_shapes_3_simplex_tree_from_off_file example_alpha_shapes_3_simplex_tree_from_off_file.cpp )
+ target_link_libraries(alpha_shapes_3_simplex_tree_from_off_file ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY})
+ if (TBB_FOUND)
+ target_link_libraries(alpha_shapes_3_simplex_tree_from_off_file ${TBB_LIBRARIES})
+ endif()
+ add_test(alpha_shapes_3_simplex_tree_from_off_file
+ ${CMAKE_CURRENT_BINARY_DIR}/alpha_shapes_3_simplex_tree_from_off_file
+ ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off)
endif()
diff --git a/src/Simplex_tree/example/README b/src/Simplex_tree/example/README
index 03c759cb..e37af790 100644
--- a/src/Simplex_tree/example/README
+++ b/src/Simplex_tree/example/README
@@ -52,7 +52,7 @@ EXAMPLE OF SIMPLE INSERTION
*** Simplex tree construction with Z/2Z coefficients on weighted graph Klein bottle file:
-./simplex_tree_from_file ../../../data/points/Klein_bottle_complex.txt 2
+./simplex_tree_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 2
Insert the 1-skeleton in the simplex tree in 0 s.
Expand the simplex tree in 0 s.
Information of the Simplex Tree:
@@ -60,7 +60,7 @@ Information of the Simplex Tree:
with Z/3Z coefficients:
-./simplex_tree_from_file ../../../data/points/Klein_bottle_complex.txt 3
+./simplex_tree_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 3
Insert the 1-skeleton in the simplex tree in 0 s.
Expand the simplex tree in 0 s.
diff --git a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp
index 45efe3ed..ff2eebcb 100644
--- a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp
+++ b/src/Simplex_tree/example/example_alpha_shapes_3_simplex_tree_from_off_file.cpp
@@ -20,8 +20,9 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <gudhi/graph_simplicial_complex.h>
#include <gudhi/Simplex_tree.h>
+#include <gudhi/Points_3D_off_io.h>
+
#include <boost/variant.hpp>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
@@ -62,7 +63,8 @@ typedef Alpha_shape_3::Edge Edge;
typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list;
// gudhi type definition
-typedef Gudhi::Simplex_tree<>::Vertex_handle Simplex_tree_vertex;
+typedef Gudhi::Simplex_tree<> Simplex_tree;
+typedef Simplex_tree::Vertex_handle Simplex_tree_vertex;
typedef std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex > Alpha_shape_simplex_tree_map;
typedef std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex> Alpha_shape_simplex_tree_pair;
typedef std::vector< Simplex_tree_vertex > Simplex_tree_vector_vertex;
@@ -117,24 +119,21 @@ int main(int argc, char * const argv[]) {
// program args management
if (argc != 2) {
std::cerr << "Usage: " << argv[0]
- << " path_to_file_graph \n";
+ << " path_to_off_file \n";
return 0;
}
// Read points from file
- std::string filegraph = argv[1];
- std::list<Point> lp;
- std::ifstream is(filegraph.c_str());
- int n;
- is >> n;
-#ifdef DEBUG_TRACES
- std::cout << "Reading " << n << " points " << std::endl;
-#endif // DEBUG_TRACES
- Point p;
- for (; n > 0; n--) {
- is >> p;
- lp.push_back(p);
+ std::string offInputFile(argv[1]);
+ // Read the OFF file (input file name given as parameter) and triangulate points
+ Gudhi::Points_3D_off_reader<Point> off_reader(offInputFile);
+ // Check the read operation was correct
+ if (!off_reader.is_valid()) {
+ std::cerr << "Unable to read file " << argv[1] << std::endl;
+ return 0;
}
+ // Retrieve the triangulation
+ std::vector<Point> lp = off_reader.get_point_cloud();
// alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode.
Alpha_shape_3 as(lp.begin(), lp.end(), 0, Alpha_shape_3::GENERAL);
@@ -161,7 +160,7 @@ int main(int argc, char * const argv[]) {
// Loop on objects vector
Vertex_list vertex_list;
- Gudhi::Simplex_tree<> simplex_tree;
+ Simplex_tree simplex_tree;
Alpha_shape_simplex_tree_map map_cgal_simplex_tree;
std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin();
for (auto object_iterator : the_objects) {
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 4c6a95e8..63e3f0e5 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -30,64 +30,32 @@
#include <gudhi/reader_utils.h>
#include <gudhi/graph_simplicial_complex.h>
+#include <gudhi/Debug_utils.h>
#include <boost/container/flat_map.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/graph/adjacency_list.hpp>
+#include <boost/range/adaptor/reversed.hpp>
+
+#ifdef GUDHI_USE_TBB
+#include <tbb/parallel_sort.h>
+#endif
-#include <algorithm>
#include <utility>
#include <vector>
#include <functional> // for greater<>
+#include <stdexcept>
+#include <limits> // Inf
+#include <initializer_list>
+#include <algorithm> // for std::max
+#include <cstdint> // for std::uint32_t
namespace Gudhi {
-/** \defgroup simplex_tree Filtered Complexes
- *
- * A simplicial complex \f$\mathbf{K}\f$
- * on a set of vertices \f$V = \{1, \cdots ,|V|\}\f$ is a collection of simplices
- * \f$\{\sigma\}\f$,
- * \f$\sigma \subseteq V\f$ such that \f$\tau \subseteq \sigma \in \mathbf{K} \rightarrow \tau \in
- * \mathbf{K}\f$. The
- * dimension \f$n=|\sigma|-1\f$ of \f$\sigma\f$ is its number of elements minus \f$1\f$.
- *
- * A filtration of a simplicial complex is
- * a function \f$f:\mathbf{K} \rightarrow \mathbb{R}\f$ satisfying \f$f(\tau)\leq f(\sigma)\f$ whenever
- * \f$\tau \subseteq \sigma\f$. Ordering the simplices by increasing filtration values
- * (breaking ties so as a simplex appears after its subsimplices of same filtration value)
- * provides an indexing scheme.
- *
-
- <DT>Implementations:</DT>
- There are two implementation of complexes. The first on is the Simplex_tree data structure.
- The simplex tree is an efficient and flexible
- data structure for representing general (filtered) simplicial complexes. The data structure
- is described in \cite boissonnatmariasimplextreealgorithmica
-
- 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 compact and harder to construct from
- scratch.
-
-
- * \author Clément Maria
- * \version 1.0
- * \date 2014
- * \copyright GNU General Public License v3.
- * @{
- */
-
-/// Model of SimplexTreeOptions.
-struct Simplex_tree_options_full_featured {
- typedef linear_indexing_tag Indexing_tag;
- typedef int Vertex_handle;
- typedef double Filtration_value;
- typedef int Simplex_key;
- static const bool store_key = true;
- static const bool store_filtration = true;
-};
+struct Simplex_tree_options_full_featured;
/**
+ * \class Simplex_tree Simplex_tree.h gudhi/Simplex_tree.h
* \brief Simplex Tree data structure for representing simplicial complexes.
*
* \details Every simplex \f$[v_0, \cdots ,v_d]\f$ admits a canonical orientation
@@ -110,7 +78,7 @@ class Simplex_tree {
typedef typename Options::Filtration_value Filtration_value;
/** \brief Key associated to each simplex.
*
- * Must be a signed integer type. */
+ * Must be an integer type. */
typedef typename Options::Simplex_key Simplex_key;
/** \brief Type for the vertex handle.
*
@@ -141,7 +109,8 @@ class Simplex_tree {
void assign_key(Simplex_key) { }
Simplex_key key() const { assert(false); return -1; }
};
- typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base;
+ typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
+ Key_simplex_base;
struct Filtration_simplex_base_real {
Filtration_simplex_base_real() : filt_(0) {}
@@ -307,7 +276,8 @@ class Simplex_tree {
* of the simplex.
*
* @param[in] sh Simplex for which the boundary is computed. */
- Boundary_simplex_range boundary_simplex_range(Simplex_handle sh) {
+ template<class SimplexHandle>
+ Boundary_simplex_range boundary_simplex_range(SimplexHandle sh) {
return Boundary_simplex_range(Boundary_simplex_iterator(this, sh),
Boundary_simplex_iterator(this));
}
@@ -328,11 +298,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);
}
@@ -344,7 +313,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);
}
@@ -449,6 +418,15 @@ class Simplex_tree {
}
}
+ /** \brief Sets the filtration value of a simplex.
+ * \exception std::invalid_argument In debug mode, if sh is a null_simplex.
+ */
+ void assign_filtration(Simplex_handle sh, Filtration_value fv) {
+ GUDHI_CHECK(sh != null_simplex(),
+ std::invalid_argument("Simplex_tree::assign_filtration - cannot assign filtration on null_simplex"));
+ sh->second.assign_filtration(fv);
+ }
+
/** \brief Returns an upper bound of the filtration values of the simplices. */
Filtration_value filtration() const {
return threshold_;
@@ -518,9 +496,10 @@ class Simplex_tree {
return dimension_;
}
- /** \brief Returns true iff the node in the simplex tree pointed by
+ /** \brief Returns true if the node in the simplex tree pointed by
* sh has children.*/
- bool has_children(Simplex_handle sh) const {
+ template<class SimplexHandle>
+ bool has_children(SimplexHandle sh) const {
return (sh->second.children()->parent() == sh->first);
}
@@ -531,7 +510,7 @@ class Simplex_tree {
* The type InputVertexRange must be a range of <CODE>Vertex_handle</CODE>
* on which we can call std::begin() function
*/
- template<class InputVertexRange>
+ template<class InputVertexRange = std::initializer_list<Vertex_handle>>
Simplex_handle find(const InputVertexRange & s) {
auto first = std::begin(s);
auto last = std::end(s);
@@ -567,13 +546,38 @@ class Simplex_tree {
/** \brief Returns the Simplex_handle corresponding to the 0-simplex
* representing the vertex with Vertex_handle v. */
Simplex_handle find_vertex(Vertex_handle v) {
- return root_.members_.begin() + v;
+ if (Options::contiguous_vertices) {
+ assert(contiguous_vertices());
+ return root_.members_.begin() + v;
+ } else {
+ return root_.members_.find(v);
+ }
+ }
+
+ public:
+ /** \private \brief Test if the vertices have contiguous numbering: 0, 1, etc. */
+ bool contiguous_vertices() const {
+ if (root_.members_.empty()) return true;
+ if (root_.members_.begin()->first != 0) return false;
+ if (std::prev(root_.members_.end())->first != static_cast<Vertex_handle>(root_.members_.size() - 1)) return false;
+ return true;
}
- //{ return root_.members_.find(v); }
private:
/** \brief Inserts a simplex represented by a vector of vertex.
- \warning the vector must be sorted by increasing vertex handle order */
+ * @param[in] simplex vector of Vertex_handles, representing the vertices of the new simplex. The vector must be
+ * sorted by increasing vertex handle order.
+ * @param[in] filtration the filtration value assigned to the new simplex.
+ * @return If the new simplex is inserted successfully (i.e. it was not in the
+ * simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned
+ * to the new simplex.
+ * If the insertion fails (the simplex is already there), the bool is set to false. If the insertion
+ * fails and the simplex already in the complex has a filtration value strictly bigger than 'filtration',
+ * we assign this simplex with the new value 'filtration', and set the Simplex_handle field of the
+ * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to
+ * null_simplex.
+ *
+ */
std::pair<Simplex_handle, bool> insert_vertex_vector(const std::vector<Vertex_handle>& simplex,
Filtration_value filtration) {
Siblings * curr_sib = &root_;
@@ -606,7 +610,7 @@ class Simplex_tree {
*
* @param[in] simplex range of Vertex_handles, representing the vertices of the new simplex
* @param[in] filtration the filtration value assigned to the new simplex.
- * The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the
+ * @return If the new simplex is inserted successfully (i.e. it was not in the
* simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned
* to the new simplex.
* If the insertion fails (the simplex is already there), the bool is set to false. If the insertion
@@ -625,7 +629,7 @@ class Simplex_tree {
*
* The type InputVertexRange must be a range for which .begin() and
* .end() return input iterators, with 'value_type' Vertex_handle. */
- template<class InputVertexRange>
+ template<class InputVertexRange = std::initializer_list<Vertex_handle>>
std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex,
Filtration_value filtration = 0) {
auto first = std::begin(simplex);
@@ -645,7 +649,7 @@ class Simplex_tree {
*
* @param[in] Nsimplex range of Vertex_handles, representing the vertices of the new N-simplex
* @param[in] filtration the filtration value assigned to the new N-simplex.
- * The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the
+ * @return If the new simplex is inserted successfully (i.e. it was not in the
* simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned
* to the new simplex.
* If the insertion fails (the simplex is already there), the bool is set to false. If the insertion
@@ -654,7 +658,7 @@ class Simplex_tree {
* output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to
* null_simplex.
*/
- template<class InputVertexRange>
+ template<class InputVertexRange = std::initializer_list<Vertex_handle>>
std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex,
Filtration_value filtration = 0) {
auto first = std::begin(Nsimplex);
@@ -708,7 +712,7 @@ class Simplex_tree {
} else if (the_simplex.size() == 1) {
// When reaching the end of recursivity, vector of simplices shall be empty and filled on back recursive
if ((to_be_inserted.size() != 0) || (to_be_propagated.size() != 0)) {
- std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty" << std::endl;
+ std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Error vector not empty\n";
exit(-1);
}
std::vector<Vertex_handle> first_simplex(1, the_simplex.back());
@@ -717,7 +721,7 @@ class Simplex_tree {
insert_result = insert_vertex_vector(first_simplex, filtration);
} else {
- std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error" << std::endl;
+ std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error\n";
exit(-1);
}
return insert_result;
@@ -730,7 +734,6 @@ class Simplex_tree {
sh->second.assign_key(key);
}
- public:
/** Returns the two Simplex_handle corresponding to the endpoints of
* and edge. sh must point to a 1-dimensional simplex. This is an
* optimized version of the boundary computation. */
@@ -740,7 +743,8 @@ class Simplex_tree {
}
/** Returns the Siblings containing a simplex.*/
- Siblings * self_siblings(Simplex_handle sh) {
+ template<class SimplexHandle>
+ Siblings* self_siblings(SimplexHandle sh) {
if (sh->second.children()->parent() == sh->first)
return sh->second.children()->oncles();
else
@@ -788,8 +792,11 @@ class Simplex_tree {
* heuristic consists in inserting the cofaces of a simplex as soon as
* possible.
*/
- std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(),
- is_before_in_filtration(this));
+#ifdef GUDHI_USE_TBB
+ tbb::parallel_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
+#else
+ std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this));
+#endif
}
private:
@@ -915,7 +922,7 @@ class Simplex_tree {
bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const {
// Not using st_->filtration(sh1) because it uselessly tests for null_simplex.
if (sh1->second.filtration() != sh2->second.filtration()) {
- return sh1->second.filtration() < sh2->second.filtration();
+ return sh1->second.filtration() < sh2->second.filtration();
}
// is sh1 a proper subface of sh2
return st_->reverse_lexicographic_order(sh1, sh2);
@@ -1092,6 +1099,120 @@ class Simplex_tree {
}
}
+ public:
+ /** \brief Browse the simplex tree to ensure the filtration is not decreasing.
+ * The simplex tree is browsed starting from the root until the leaf, and the filtration values are set with their
+ * parent value (increased), in case the values are decreasing.
+ * @return The filtration modification information.
+ * \post Some simplex tree functions require the filtration to be valid. `make_filtration_non_decreasing()`
+ * function is not launching `initialize_filtration()` but returns the filtration modification information. If the
+ * complex has changed , please call `initialize_filtration()` to recompute it.
+ */
+ bool make_filtration_non_decreasing() {
+ bool modified = false;
+ // 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)) {
+ modified |= rec_make_filtration_non_decreasing(simplex.second.children());
+ }
+ }
+ return modified;
+ }
+
+ private:
+ /** \brief Recursively Browse the simplex tree to ensure the filtration is not decreasing.
+ * @param[in] sib Siblings to be parsed.
+ * @return The filtration modification information in order to trigger initialize_filtration.
+ */
+ bool rec_make_filtration_non_decreasing(Siblings * sib) {
+ bool modified = false;
+
+ // 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(sib->members())) {
+ // Find the maximum filtration value in the border
+ Boundary_simplex_range boundary = boundary_simplex_range(&simplex);
+ 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 (simplex.second.filtration() < max_filt_border_value) {
+ // Store the filtration modification information
+ modified = true;
+ simplex.second.assign_filtration(max_filt_border_value);
+ }
+ if (has_children(&simplex)) {
+ modified |= rec_make_filtration_non_decreasing(simplex.second.children());
+ }
+ }
+ // Make the modified information to be traced by upper call
+ return modified;
+ }
+
+ public:
+ /** \brief Prune above filtration value given as parameter.
+ * @param[in] filtration Maximum threshold value.
+ * @return The filtration modification information.
+ * \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.
+ */
+ bool prune_above_filtration(Filtration_value filtration) {
+ return rec_prune_above_filtration(root(), filtration);
+ }
+
+ private:
+ bool rec_prune_above_filtration(Siblings* sib, Filtration_value filt) {
+ auto&& list = sib->members();
+ 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());
+ return true;
+ });
+
+ bool modified = (last != list.end());
+ if (last == list.begin() && sib != root()) {
+ // Removing the whole siblings, parent becomes a leaf.
+ sib->oncles()->members()[sib->parent()].assign_children(sib->oncles());
+ delete sib;
+ return true;
+ } else {
+ // Keeping some elements of siblings. Remove the others, and recurse in the remaining ones.
+ list.erase(last, list.end());
+ for (auto&& simplex : list)
+ if (has_children(&simplex))
+ modified |= rec_prune_above_filtration(simplex.second.children(), filt);
+ }
+ return modified;
+ }
+
+ public:
+ /** \brief Remove a maximal simplex.
+ * @param[in] sh Simplex handle on the maximal simplex to remove.
+ * \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).
+ */
+ void 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"));
+
+ // Simplex is a leaf, it means the child is the Siblings owning the leaf
+ Siblings* child = sh->second.children();
+
+ if ((child->size() > 1) || (child == root())) {
+ // Not alone, just remove it from members
+ // Special case when child is the root of the simplex tree, just remove it from members
+ child->erase(sh);
+ } else {
+ // 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;
+ }
+ }
+
private:
Vertex_handle null_vertex_;
/** \brief Upper bound on the filtration values of the simplices.*/
@@ -1106,7 +1227,6 @@ class Simplex_tree {
};
// Print a Simplex_tree in os.
-
template<typename...T>
std::ostream& operator<<(std::ostream & os, Simplex_tree<T...> & st) {
for (auto sh : st.filtration_simplex_range()) {
@@ -1145,6 +1265,37 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
return is;
}
+
+/** Model of SimplexTreeOptions.
+ *
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint32_t>::max()</CODE>
+ * (about 4 billions of simplices). */
+struct Simplex_tree_options_full_featured {
+ typedef linear_indexing_tag Indexing_tag;
+ typedef int Vertex_handle;
+ typedef double Filtration_value;
+ typedef std::uint32_t Simplex_key;
+ static const bool store_key = true;
+ static const bool store_filtration = true;
+ static const bool contiguous_vertices = false;
+};
+
+/** Model of SimplexTreeOptions, faster than `Simplex_tree_options_full_featured` but note the unsafe
+ * `contiguous_vertices` option.
+ *
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint32_t>::max()</CODE>
+ * (about 4 billions of simplices). */
+
+struct Simplex_tree_options_fast_persistence {
+ typedef linear_indexing_tag Indexing_tag;
+ typedef int Vertex_handle;
+ typedef float Filtration_value;
+ typedef std::uint32_t Simplex_key;
+ static const bool store_key = true;
+ static const bool store_filtration = true;
+ static const bool contiguous_vertices = true;
+};
+
/** @} */ // end defgroup simplex_tree
} // namespace Gudhi
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
index 372ef329..7e0a454d 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h
@@ -54,7 +54,7 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st)
: // any end() iterator
- sib_(NULL),
+ sib_(nullptr),
v_(st->null_vertex()) {
}
@@ -99,21 +99,23 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
// any end() iterator
explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st)
- : last_(st->null_vertex()),
- sib_(NULL) {
+ : sib_(nullptr),
+ sh_(st->null_simplex()),
+ st_(st) {
}
- Simplex_tree_boundary_simplex_iterator(SimplexTree * st, Simplex_handle sh)
- : suffix_(),
+ template<class SimplexHandle>
+ Simplex_tree_boundary_simplex_iterator(SimplexTree * st, SimplexHandle sh)
+ : last_(sh->first),
+ sib_(nullptr),
st_(st) {
- last_ = sh->first;
Siblings * sib = st->self_siblings(sh);
next_ = sib->parent();
- sib_ = sib->oncles(); /* \todo check if NULL*/
- if (sib_ != NULL) {
+ sib_ = sib->oncles();
+ if (sib_ != nullptr) {
sh_ = sib_->find(next_);
} else {
- last_ = st->null_vertex();
+ sh_ = st->null_simplex();
} // vertex: == end()
}
@@ -121,28 +123,40 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
friend class boost::iterator_core_access;
// valid when iterating along the SAME boundary.
bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
- return (sib_ == other.sib_ && last_ == other.last_);
+ return sh_ == other.sh_;
}
Simplex_handle const& dereference() const {
+ assert(sh_ != st_->null_simplex());
return sh_;
}
void increment() {
- if (sib_ == NULL) {
- last_ = st_->null_vertex();
+ if (sib_ == nullptr) {
+ sh_ = st_->null_simplex();
return;
}
Siblings * for_sib = sib_;
- for (auto rit = suffix_.rbegin(); rit != suffix_.rend(); ++rit) {
+ Siblings * new_sib = sib_->oncles();
+ auto rit = suffix_.rbegin();
+ if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr && rit != suffix_.rend()) {
+ // We reached the root, use a short-cut to find a vertex. We could also
+ // optimize finding the second vertex of a segment, but people are
+ // expected to call endpoints().
+ assert(st_->contiguous_vertices());
+ sh_ = for_sib->members_.begin()+*rit;
+ for_sib = sh_->second.children();
+ ++rit;
+ }
+ for (; rit != suffix_.rend(); ++rit) {
sh_ = for_sib->find(*rit);
for_sib = sh_->second.children();
}
sh_ = for_sib->find(last_); // sh_ points to the right simplex now
suffix_.push_back(next_);
next_ = sib_->parent();
- sib_ = sib_->oncles();
+ sib_ = new_sib;
}
// Most of the storage should be moved to the range, iterators should be light.
@@ -176,13 +190,15 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
// any end() iterator
Simplex_tree_complex_simplex_iterator()
- : st_(NULL) {
+ : sib_(nullptr),
+ st_(nullptr) {
}
explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st)
- : st_(st) {
- if (st == NULL || st->root() == NULL || st->root()->members().empty()) {
- st_ = NULL;
+ : sib_(nullptr),
+ st_(st) {
+ if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
+ st_ = nullptr;
} else {
sh_ = st->root()->members().begin();
sib_ = st->root();
@@ -197,10 +213,10 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
// valid when iterating along the SAME boundary.
bool equal(Simplex_tree_complex_simplex_iterator const& other) const {
- if (other.st_ == NULL) {
- return (st_ == NULL);
+ if (other.st_ == nullptr) {
+ return (st_ == nullptr);
}
- if (st_ == NULL) {
+ if (st_ == nullptr) {
return false;
}
return (&(sh_->second) == &(other.sh_->second));
@@ -214,8 +230,8 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
void increment() {
++sh_;
if (sh_ == sib_->members().end()) {
- if (sib_->oncles() == NULL) {
- st_ = NULL;
+ if (sib_->oncles() == nullptr) {
+ st_ = nullptr;
return;
} // reach the end
sh_ = sib_->oncles()->members().find(sib_->parent());
@@ -248,15 +264,19 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
// any end() iterator
Simplex_tree_skeleton_simplex_iterator()
- : st_(NULL) {
+ : sib_(nullptr),
+ st_(nullptr),
+ dim_skel_(0),
+ curr_dim_(0) {
}
Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel)
- : st_(st),
+ : sib_(nullptr),
+ st_(st),
dim_skel_(dim_skel),
curr_dim_(0) {
- if (st == NULL || st->root() == NULL || st->root()->members().empty()) {
- st_ = NULL;
+ if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) {
+ st_ = nullptr;
} else {
sh_ = st->root()->members().begin();
sib_ = st->root();
@@ -272,10 +292,10 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
// valid when iterating along the SAME boundary.
bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const {
- if (other.st_ == NULL) {
- return (st_ == NULL);
+ if (other.st_ == nullptr) {
+ return (st_ == nullptr);
}
- if (st_ == NULL) {
+ if (st_ == nullptr) {
return false;
}
return (&(sh_->second) == &(other.sh_->second));
@@ -289,8 +309,8 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
void increment() {
++sh_;
if (sh_ == sib_->members().end()) {
- if (sib_->oncles() == NULL) {
- st_ = NULL;
+ if (sib_->oncles() == nullptr) {
+ st_ = nullptr;
return;
} // reach the end
sh_ = sib_->oncles()->members().find(sib_->parent());
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
index 158ee1f7..1eca7f6f 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
@@ -57,7 +57,7 @@ class Simplex_tree_siblings {
/* Default constructor.*/
Simplex_tree_siblings()
- : oncles_(NULL),
+ : oncles_(nullptr),
parent_(-1),
members_() {
}
@@ -116,6 +116,10 @@ class Simplex_tree_siblings {
return members_.size();
}
+ void erase(const Dictionary_it iterator) {
+ members_.erase(iterator);
+ }
+
Simplex_tree_siblings * oncles_;
Vertex_handle parent_;
Dictionary members_;
diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt
index c9eae163..e95d0782 100644
--- a/src/Simplex_tree/test/CMakeLists.txt
+++ b/src/Simplex_tree/test/CMakeLists.txt
@@ -1,21 +1,20 @@
cmake_minimum_required(VERSION 2.6)
-project(GUDHISimplexTreeUT)
+project(Simplex_tree_tests)
if (GCOVR_PATH)
# for gcovr to make coverage reports - Corbera Jenkins plugin
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage")
- set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fprofile-arcs -ftest-coverage")
- set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -fprofile-arcs -ftest-coverage")
endif()
if (GPROF_PATH)
# for gprof to make coverage reports - Jenkins
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg")
- set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg")
- set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg")
endif()
add_executable ( SimplexTreeUT simplex_tree_unit_test.cpp )
target_link_libraries(SimplexTreeUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+if (TBB_FOUND)
+ target_link_libraries(SimplexTreeUT ${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}/)
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index fff00d77..28bf202b 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -4,10 +4,12 @@
#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.
@@ -15,26 +17,25 @@
using namespace Gudhi;
-typedef Simplex_tree<> typeST;
-typedef std::pair<typeST::Simplex_handle, bool> typePairSimplexBool;
-typedef std::vector<Vertex_handle> typeVectorVertex;
-typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex;
+typedef boost::mpl::list<Simplex_tree<>, Simplex_tree<Simplex_tree_options_fast_persistence>> list_of_tested_variants;
const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) - 1;
const Filtration_value DEFAULT_FILTRATION_VALUE = (const Filtration_value) 0.0;
+template<class typeST>
void test_empty_simplex_tree(typeST& tst) {
BOOST_CHECK(tst.null_vertex() == DEFAULT_VERTEX_HANDLE);
BOOST_CHECK(tst.filtration() == DEFAULT_FILTRATION_VALUE);
BOOST_CHECK(tst.num_vertices() == (size_t) 0);
BOOST_CHECK(tst.num_simplices() == (size_t) 0);
- typeST::Siblings* STRoot = tst.root();
- BOOST_CHECK(STRoot != NULL);
- BOOST_CHECK(STRoot->oncles() == NULL);
+ typename typeST::Siblings* STRoot = tst.root();
+ BOOST_CHECK(STRoot != nullptr);
+ BOOST_CHECK(STRoot->oncles() == nullptr);
BOOST_CHECK(STRoot->parent() == DEFAULT_VERTEX_HANDLE);
BOOST_CHECK(tst.dimension() == -1);
}
+template<class typeST>
void test_iterators_on_empty_simplex_tree(typeST& tst) {
std::cout << "Iterator on vertices: " << std::endl;
for (auto vertex : tst.complex_vertex_range()) {
@@ -56,8 +57,9 @@ void test_iterators_on_empty_simplex_tree(typeST& tst) {
}
}
-BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) {
- const Filtration_value DEFAULT_FILTRATION_VALUE = 0;
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_when_empty, typeST, list_of_tested_variants) {
+ typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool;
+ typedef std::vector<Vertex_handle> typeVectorVertex;
std::cout << "********************************************************************" << std::endl;
std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl;
@@ -72,7 +74,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) {
BOOST_CHECK(simplexVectorEmpty.empty() == true);
typePairSimplexBool returnEmptyValue = st.insert_simplex(simplexVectorEmpty,
DEFAULT_FILTRATION_VALUE);
- BOOST_CHECK(returnEmptyValue.first == typeST::Simplex_handle(NULL));
+ BOOST_CHECK(returnEmptyValue.first == typename typeST::Simplex_handle(nullptr));
BOOST_CHECK(returnEmptyValue.second == true);
test_empty_simplex_tree(st);
@@ -84,7 +86,7 @@ bool AreAlmostTheSame(float a, float b) {
return std::fabs(a - b) < std::numeric_limits<float>::epsilon();
}
-BOOST_AUTO_TEST_CASE(simplex_tree_from_file) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_from_file, typeST, list_of_tested_variants) {
// TEST OF INSERTION
std::cout << "********************************************************************" << std::endl;
std::cout << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl;
@@ -101,7 +103,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_from_file) {
// Check
BOOST_CHECK(st.num_simplices() == 143353);
BOOST_CHECK(st.dimension() == 3);
- BOOST_CHECK(st.filtration() == 0.4);
+ BOOST_CHECK(AreAlmostTheSame(st.filtration(), 0.4));
int previous_size = 0;
for (auto f_simplex : st.filtration_simplex_range()) {
@@ -119,6 +121,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_from_file) {
simplex_tree_stream.close();
}
+template<class typeST, class typeSimplex>
void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int pos) {
auto f_simplex = simplexTree.filtration_simplex_range().begin() + pos;
@@ -135,16 +138,18 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p
}
}
+template<class typeST, class typePairSimplexBool>
void test_simplex_tree_insert_returns_true(const typePairSimplexBool& returnValue) {
BOOST_CHECK(returnValue.second == true);
- typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator
- BOOST_CHECK(shReturned != typeST::Simplex_handle(NULL));
+ typename typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator
+ BOOST_CHECK(shReturned != typename typeST::Simplex_handle(nullptr));
}
// Global variables
Filtration_value max_fil = DEFAULT_FILTRATION_VALUE;
int dim_max = -1;
+template<class typeST, class Filtration_value>
void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, const Filtration_value& fil) {
if (vectorSize > dim_max + 1) {
dim_max = vectorSize - 1;
@@ -173,11 +178,17 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons
BOOST_CHECK(simplexTree.num_simplices() == num_simp);
}
-BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_variants) {
+ typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool;
+ typedef std::vector<Vertex_handle> typeVectorVertex;
+ typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex;
const Filtration_value FIRST_FILTRATION_VALUE = 0.1;
const Filtration_value SECOND_FILTRATION_VALUE = 0.2;
const Filtration_value THIRD_FILTRATION_VALUE = 0.3;
const Filtration_value FOURTH_FILTRATION_VALUE = 0.4;
+ // reset since we run the test several times
+ dim_max = -1;
+ max_fil = DEFAULT_FILTRATION_VALUE;
// TEST OF INSERTION
std::cout << "********************************************************************" << std::endl;
@@ -191,7 +202,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex firstSimplex = std::make_pair(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE));
typePairSimplexBool returnValue = st.insert_simplex(firstSimplex.first, firstSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, firstSimplexVector.size(), firstSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 1);
@@ -202,7 +213,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex secondSimplex = std::make_pair(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE));
returnValue = st.insert_simplex(secondSimplex.first, secondSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, secondSimplexVector.size(), secondSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 2);
@@ -213,7 +224,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex thirdSimplex = std::make_pair(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE));
returnValue = st.insert_simplex(thirdSimplex.first, thirdSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, thirdSimplexVector.size(), thirdSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 2); // Not incremented !!
@@ -224,7 +235,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex fourthSimplex = std::make_pair(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE));
returnValue = st.insert_simplex(fourthSimplex.first, fourthSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, fourthSimplexVector.size(), fourthSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 3);
@@ -235,7 +246,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex fifthSimplex = std::make_pair(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE));
returnValue = st.insert_simplex(fifthSimplex.first, fifthSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, fifthSimplexVector.size(), fifthSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !!
@@ -246,7 +257,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex sixthSimplex = std::make_pair(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE));
returnValue = st.insert_simplex(sixthSimplex.first, sixthSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, sixthSimplexVector.size(), sixthSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !!
@@ -257,7 +268,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex seventhSimplex = std::make_pair(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE));
returnValue = st.insert_simplex(seventhSimplex.first, seventhSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, seventhSimplexVector.size(), seventhSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !!
@@ -268,7 +279,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex eighthSimplex = std::make_pair(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE));
returnValue = st.insert_simplex(eighthSimplex.first, eighthSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 4);
@@ -279,7 +290,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
typeSimplex ninethSimplex = std::make_pair(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE));
returnValue = st.insert_simplex(ninethSimplex.first, ninethSimplex.second);
- test_simplex_tree_insert_returns_true(returnValue);
+ test_simplex_tree_insert_returns_true<typeST>(returnValue);
set_and_test_simplex_tree_dim_fil(st, ninethSimplexVector.size(), ninethSimplex.second);
BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !!
@@ -292,8 +303,8 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
returnValue = st.insert_simplex(tenthSimplex.first, tenthSimplex.second);
BOOST_CHECK(returnValue.second == false);
- typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator
- BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL));
+ typename typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator
+ 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));
@@ -307,7 +318,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
BOOST_CHECK(returnValue.second == false);
shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator
- BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL));
+ 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));
@@ -362,9 +373,10 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) {
}
-bool sort_in_decr_order (Vertex_handle i,Vertex_handle j) { return (i>j); }
-
-BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_of_tested_variants) {
+ typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool;
+ typedef std::vector<Vertex_handle> typeVectorVertex;
+ typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex;
std::cout << "********************************************************************" << std::endl;
std::cout << "TEST OF RECURSIVE INSERTION" << std::endl;
typeST st;
@@ -382,7 +394,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Check it is well inserted
BOOST_CHECK(true == returnValue.second);
position = 0;
- std::sort(SimplexVector1.begin(), SimplexVector1.end(), sort_in_decr_order);
+ std::sort(SimplexVector1.begin(), SimplexVector1.end(), std::greater<Vertex_handle>());
for (auto vertex : st.simplex_vertex_range(returnValue.first)) {
// Check returned Simplex_handle
std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector1[position] << std::endl;
@@ -401,7 +413,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Check it is well inserted
BOOST_CHECK(true == returnValue.second);
position = 0;
- std::sort(SimplexVector2.begin(), SimplexVector2.end(), sort_in_decr_order);
+ std::sort(SimplexVector2.begin(), SimplexVector2.end(), std::greater<Vertex_handle>());
for (auto vertex : st.simplex_vertex_range(returnValue.first)) {
// Check returned Simplex_handle
std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector2[position] << std::endl;
@@ -420,7 +432,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Check it is well inserted
BOOST_CHECK(true == returnValue.second);
position = 0;
- std::sort(SimplexVector3.begin(), SimplexVector3.end(), sort_in_decr_order);
+ std::sort(SimplexVector3.begin(), SimplexVector3.end(), std::greater<Vertex_handle>());
for (auto vertex : st.simplex_vertex_range(returnValue.first)) {
// Check returned Simplex_handle
std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector3[position] << std::endl;
@@ -450,7 +462,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Check it is well inserted
BOOST_CHECK(true == returnValue.second);
position = 0;
- std::sort(SimplexVector5.begin(), SimplexVector5.end(), sort_in_decr_order);
+ std::sort(SimplexVector5.begin(), SimplexVector5.end(), std::greater<Vertex_handle>());
for (auto vertex : st.simplex_vertex_range(returnValue.first)) {
// Check returned Simplex_handle
std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector5[position] << std::endl;
@@ -469,7 +481,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Check it is well inserted
BOOST_CHECK(true == returnValue.second);
position = 0;
- std::sort(SimplexVector6.begin(), SimplexVector6.end(), sort_in_decr_order);
+ std::sort(SimplexVector6.begin(), SimplexVector6.end(), std::greater<Vertex_handle>());
for (auto vertex : st.simplex_vertex_range(returnValue.first)) {
// Check returned Simplex_handle
std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector6[position] << std::endl;
@@ -509,7 +521,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
// Find in the simplex_tree
// ------------------------------------------------------------------------------------------------------------------
typeVectorVertex simpleSimplexVector{1};
- Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector);
+ typename typeST::Simplex_handle simplexFound = st.find(simpleSimplexVector);
std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n";
if (simplexFound != st.null_simplex())
std::cout << "***+ YES IT IS!\n";
@@ -570,14 +582,15 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) {
}
}
-void test_cofaces(typeST& st, std::vector<Vertex_handle> expected, int dim, std::vector<typeST::Simplex_handle> res) {
- typeST::Cofaces_simplex_range cofaces;
+template<class typeST, class Vertex_handle>
+void test_cofaces(typeST& st, const std::vector<Vertex_handle>& expected, int dim, const std::vector<typename typeST::Simplex_handle>& res) {
+ typename typeST::Cofaces_simplex_range cofaces;
if (dim == 0)
cofaces = st.star_simplex_range(st.find(expected));
else
cofaces = st.cofaces_simplex_range(st.find(expected), dim);
for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) {
- typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex);
+ typename typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex);
for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) {
std::cout << "(" << *vertex << ")";
}
@@ -586,7 +599,8 @@ void test_cofaces(typeST& st, std::vector<Vertex_handle> expected, int dim, std:
}
}
-BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_variants) {
+ typedef std::vector<Vertex_handle> typeVectorVertex;
std::cout << "********************************************************************" << std::endl;
std::cout << "TEST COFACE ALGORITHM" << std::endl;
typeST st;
@@ -616,7 +630,7 @@ BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) {
st.set_dimension(3);
std::vector<Vertex_handle> simplex_result;
- std::vector<typeST::Simplex_handle> result;
+ std::vector<typename typeST::Simplex_handle> result;
std::cout << "First test - Star of (3):" << std::endl;
simplex_result = {3};
@@ -684,7 +698,8 @@ BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) {
}
-BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) {
+BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_variants) {
+ typedef std::vector<Vertex_handle> typeVectorVertex;
std::cout << "********************************************************************" << std::endl;
std::cout << "TEST COPY MOVE CONSTRUCTORS" << std::endl;
typeST st;
@@ -744,3 +759,391 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) {
std::cout << "Printing st once again- address = " << &st << std::endl;
}
+
+template<class typeST>
+void test_simplex_is_vertex(typeST& st, typename typeST::Simplex_handle sh, typename typeST::Vertex_handle v) {
+ BOOST_CHECK(st.dimension(sh) == 0);
+ auto&& r = st.simplex_vertex_range(sh);
+ auto i = std::begin(r);
+ BOOST_CHECK(*i == v);
+ BOOST_CHECK(++i == std::end(r));
+}
+
+BOOST_AUTO_TEST_CASE(non_contiguous) {
+ typedef Simplex_tree<> typeST;
+ typedef typeST::Vertex_handle Vertex_handle;
+ typedef typeST::Simplex_handle Simplex_handle;
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST NON-CONTIGUOUS VERTICES" << std::endl;
+ typeST st;
+ Vertex_handle e[] = {3,-7};
+ std::cout << "Insert" << std::endl;
+ st.insert_simplex_and_subfaces(e);
+ BOOST_CHECK(st.num_vertices() == 2);
+ BOOST_CHECK(st.num_simplices() == 3);
+ std::cout << "Find" << std::endl;
+ Simplex_handle sh = st.find(e);
+ BOOST_CHECK(sh != st.null_simplex());
+ std::cout << "Endpoints" << std::endl;
+ auto p = st.endpoints(sh);
+ test_simplex_is_vertex(st, p.first, 3);
+ test_simplex_is_vertex(st, p.second, -7);
+ std::cout << "Boundary" << std::endl;
+ auto&& b = st.boundary_simplex_range(sh);
+ auto i = std::begin(b);
+ test_simplex_is_vertex(st, *i, -7);
+ test_simplex_is_vertex(st, *++i, 3);
+ BOOST_CHECK(++i == std::end(b));
+}
+
+BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) {
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "MAKE FILTRATION NON DECREASING" << std::endl;
+ typedef Simplex_tree<> typeST;
+ typeST st;
+
+ 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);
+
+ /* 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
+
+ std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl;
+ BOOST_CHECK(!st.make_filtration_non_decreasing());
+
+ // Copy original simplex tree
+ typeST st_copy = st;
+
+ // 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_copy);
+
+ // 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 {
+ // 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-02 02:03:25 +0000