summaryrefslogtreecommitdiff
path: root/src/Simplex_tree
diff options
context:
space:
mode:
Diffstat (limited to 'src/Simplex_tree')
-rw-r--r--src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp2
-rw-r--r--src/Simplex_tree/include/gudhi/Simplex_tree.h140
-rw-r--r--src/Simplex_tree/test/CMakeLists.txt8
-rw-r--r--src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp137
-rw-r--r--src/Simplex_tree/test/simplex_tree_unit_test.cpp56
5 files changed, 300 insertions, 43 deletions
diff --git a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp
index 34092ef6..6bab8adb 100644
--- a/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp
+++ b/src/Simplex_tree/example/cech_complex_cgal_mini_sphere_3d.cpp
@@ -50,7 +50,7 @@ using Vertex_handle = Simplex_tree::Vertex_handle;
using Simplex_handle = Simplex_tree::Simplex_handle;
using Filtration_value = Simplex_tree::Filtration_value;
using Siblings = Simplex_tree::Siblings;
-using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
+using Graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::property<Gudhi::vertex_filtration_t, Filtration_value>,
boost::property<Gudhi::edge_filtration_t, Filtration_value> >;
using Edge_t = std::pair<Vertex_handle, Vertex_handle>;
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index ee96d5a2..4b18651c 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -296,12 +296,79 @@ class Simplex_tree {
dimension_(-1) { }
/** \brief User-defined copy constructor reproduces the whole tree structure. */
- Simplex_tree(const Simplex_tree& simplex_source)
- : null_vertex_(simplex_source.null_vertex_),
- root_(nullptr, null_vertex_ , simplex_source.root_.members_),
- filtration_vect_(),
- dimension_(simplex_source.dimension_) {
- auto root_source = simplex_source.root_;
+ Simplex_tree(const Simplex_tree& complex_source) {
+#ifdef DEBUG_TRACES
+ std::cout << "Simplex_tree copy constructor" << std::endl;
+#endif // DEBUG_TRACES
+ copy_from(complex_source);
+ }
+
+ /** \brief User-defined move constructor relocates the whole tree structure.
+ * \exception std::invalid_argument In debug mode, if the complex_source is invalid.
+ */
+ Simplex_tree(Simplex_tree && complex_source) {
+#ifdef DEBUG_TRACES
+ std::cout << "Simplex_tree move constructor" << std::endl;
+#endif // DEBUG_TRACES
+ move_from(complex_source);
+
+ // just need to set dimension_ on source to make it available again
+ // (filtration_vect_ and members are already set from the move)
+ complex_source.dimension_ = -1;
+ }
+
+ /** \brief Destructor; deallocates the whole tree structure. */
+ ~Simplex_tree() {
+ root_members_recursive_deletion();
+ }
+
+ /** \brief User-defined copy assignment reproduces the whole tree structure. */
+ Simplex_tree& operator= (const Simplex_tree& complex_source) {
+#ifdef DEBUG_TRACES
+ std::cout << "Simplex_tree copy assignment" << std::endl;
+#endif // DEBUG_TRACES
+ // Self-assignment detection
+ if (&complex_source != this) {
+ // We start by deleting root_ if not empty
+ root_members_recursive_deletion();
+
+ copy_from(complex_source);
+ }
+ return *this;
+ }
+
+ /** \brief User-defined move assignment relocates the whole tree structure.
+ * \exception std::invalid_argument In debug mode, if the complex_source is invalid.
+ */
+ Simplex_tree& operator=(Simplex_tree&& complex_source) {
+#ifdef DEBUG_TRACES
+ std::cout << "Simplex_tree move assignment" << std::endl;
+#endif // DEBUG_TRACES
+ // Self-assignment detection
+ if (&complex_source != this) {
+ // root_ deletion in case it was not empty
+ root_members_recursive_deletion();
+
+ move_from(complex_source);
+ }
+ return *this;
+ }
+ /** @} */ // end constructor/destructor
+
+ private:
+ // Copy from complex_source to "this"
+ void copy_from(const Simplex_tree& complex_source) {
+ null_vertex_ = complex_source.null_vertex_;
+ filtration_vect_.clear();
+ dimension_ = complex_source.dimension_;
+ auto root_source = complex_source.root_;
+
+ // root members copy
+ root_.members() = Dictionary(boost::container::ordered_unique_range, root_source.members().begin(), root_source.members().end());
+ // Needs to reassign children
+ for (auto& map_el : root_.members()) {
+ map_el.second.assign_children(&root_);
+ }
rec_copy(&root_, &root_source);
}
@@ -320,26 +387,38 @@ 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_)),
- root_(std::move(old.root_)),
- filtration_vect_(std::move(old.filtration_vect_)),
- dimension_(std::move(old.dimension_)) {
- old.dimension_ = -1;
- old.root_ = Siblings(nullptr, null_vertex_);
+ // Move from complex_source to "this"
+ void move_from(Simplex_tree& complex_source) {
+ null_vertex_ = std::move(complex_source.null_vertex_);
+ root_ = std::move(complex_source.root_);
+ filtration_vect_ = std::move(complex_source.filtration_vect_);
+ dimension_ = std::move(complex_source.dimension_);
+
+ // Need to update root members (children->oncles and children need to point on the new root pointer)
+ for (auto& map_el : root_.members()) {
+ if (map_el.second.children() != &(complex_source.root_)) {
+ // reset children->oncles with the moved root_ pointer value
+ map_el.second.children()->oncles_ = &root_;
+ } else {
+ // if simplex is of dimension 0, oncles_ shall be nullptr
+ GUDHI_CHECK(map_el.second.children()->oncles_ == nullptr,
+ std::invalid_argument("Simplex_tree move constructor from an invalid Simplex_tree"));
+ // and children points on root_ - to be moved
+ map_el.second.assign_children(&root_);
+ }
+ }
}
- /** \brief Destructor; deallocates the whole tree structure. */
- ~Simplex_tree() {
+ // delete all root_.members() recursively
+ void root_members_recursive_deletion() {
for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) {
if (has_children(sh)) {
rec_delete(sh->second.children());
}
}
+ root_.members().clear();
}
- /** @} */ // end constructor/destructor
- private:
+
// Recursive deletion
void rec_delete(Siblings * sib) {
for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) {
@@ -970,7 +1049,8 @@ class Simplex_tree {
* boost::graph_traits<OneSkeletonGraph>::vertex_descriptor
* must be Vertex_handle.
* boost::graph_traits<OneSkeletonGraph>::directed_category
- * must be undirected_tag.
+ * can be directed_tag (the fastest, the least RAM use), undirected_tag or even
+ * bidirected_tag.
*
* If an edge appears with multiplicity, the function will arbitrarily pick
* one representative to read the filtration value. */
@@ -998,12 +1078,14 @@ class Simplex_tree {
root_.members_.end(), *v_it,
Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it)));
}
- typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it,
- e_it_end;
- for (std::tie(e_it, e_it_end) = boost::edges(skel_graph); e_it != e_it_end;
- ++e_it) {
- auto u = source(*e_it, skel_graph);
- auto v = target(*e_it, skel_graph);
+ std::pair<typename boost::graph_traits<OneSkeletonGraph>::edge_iterator,
+ typename boost::graph_traits<OneSkeletonGraph>::edge_iterator> boost_edges = boost::edges(skel_graph);
+ // boost_edges.first is the equivalent to boost_edges.begin()
+ // boost_edges.second is the equivalent to boost_edges.end()
+ for (; boost_edges.first != boost_edges.second; boost_edges.first++) {
+ auto edge = *(boost_edges.first);
+ auto u = source(edge, skel_graph);
+ auto v = target(edge, skel_graph);
if (u == v) throw "Self-loops are not simplicial";
// We cannot skip edges with the wrong orientation and expect them to
// come a second time with the right orientation, that does not always
@@ -1019,7 +1101,7 @@ class Simplex_tree {
}
sh->second.children()->members().emplace(v,
- Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, *e_it)));
+ Node(sh->second.children(), boost::get(edge_filtration_t(), skel_graph, edge)));
}
}
@@ -1035,6 +1117,7 @@ class Simplex_tree {
* The Simplex_tree must contain no simplex of dimension bigger than
* 1 when calling the method. */
void expansion(int max_dim) {
+ if (max_dim <= 1) return;
dimension_ = max_dim;
for (Dictionary_it root_it = root_.members_.begin();
root_it != root_.members_.end(); ++root_it) {
@@ -1057,7 +1140,10 @@ class Simplex_tree {
Dictionary_it next = siblings->members().begin();
++next;
- thread_local std::vector<std::pair<Vertex_handle, Node> > inter;
+#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL
+ thread_local
+#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL
+ std::vector<std::pair<Vertex_handle, Node> > inter;
for (Dictionary_it s_h = siblings->members().begin();
s_h != siblings->members().end(); ++s_h, ++next) {
Simplex_handle root_sh = find_vertex(s_h->first);
diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt
index c63d8532..5bea3938 100644
--- a/src/Simplex_tree/test/CMakeLists.txt
+++ b/src/Simplex_tree/test/CMakeLists.txt
@@ -28,3 +28,11 @@ if (TBB_FOUND)
endif()
gudhi_add_coverage_test(Simplex_tree_iostream_operator_test_unit)
+
+add_executable ( Simplex_tree_ctor_and_move_test_unit simplex_tree_ctor_and_move_unit_test.cpp )
+target_link_libraries(Simplex_tree_ctor_and_move_test_unit ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+if (TBB_FOUND)
+ target_link_libraries(Simplex_tree_ctor_and_move_test_unit ${TBB_LIBRARIES})
+endif()
+
+gudhi_add_coverage_test(Simplex_tree_ctor_and_move_test_unit)
diff --git a/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp
new file mode 100644
index 00000000..e729cf00
--- /dev/null
+++ b/src/Simplex_tree/test/simplex_tree_ctor_and_move_unit_test.cpp
@@ -0,0 +1,137 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "simplex_tree_constructor_and_move"
+#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;
+
+template<typename Simplex_tree>
+void print_simplex_filtration(Simplex_tree& st, const std::string& msg) {
+ // Required before browsing through filtration values
+ st.initialize_filtration();
+
+ std::cout << "********************************************************************\n";
+ std::cout << "* " << msg << "\n";
+ std::cout << "* The complex contains " << st.num_simplices() << " simplices";
+ std::cout << " - dimension " << st.dimension() << "\n";
+ std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n";
+ 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 << "(" << vertex << ")";
+ std::cout << std::endl;
+ }
+
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_copy_constructor, Simplex_tree, list_of_tested_variants) {
+ Simplex_tree st;
+
+ st.insert_simplex_and_subfaces({2, 1, 0}, 3.0);
+ st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.0);
+ st.insert_simplex_and_subfaces({3, 0}, 2.0);
+ st.insert_simplex_and_subfaces({3, 4, 5}, 3.0);
+ st.insert_simplex_and_subfaces({8}, 1.0);
+ /* Inserted simplex: */
+ /* 1 6 */
+ /* o---o */
+ /* /X\7/ */
+ /* o---o---o---o o */
+ /* 2 0 3\X/4 8 */
+ /* o */
+ /* 5 */
+ /* */
+ /* In other words: */
+ /* A facet [2,1,0] */
+ /* An edge [0,3] */
+ /* A facet [3,4,5] */
+ /* A cell [0,1,6,7] */
+ /* A vertex [8] */
+
+ print_simplex_filtration(st, "Default Simplex_tree is initialized");
+
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST OF COPY CONSTRUCTOR" << std::endl;
+
+ Simplex_tree st1(st);
+ Simplex_tree st2(st);
+ print_simplex_filtration(st1, "First copy constructor from the default Simplex_tree");
+ print_simplex_filtration(st2, "Second copy constructor from the default Simplex_tree");
+ // Cross check
+ BOOST_CHECK(st1 == st2);
+ BOOST_CHECK(st == st2);
+ BOOST_CHECK(st1 == st);
+
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST OF COPY ASSIGNMENT" << std::endl;
+ Simplex_tree st3;
+ // To check there is no memory leak
+ st3.insert_simplex_and_subfaces({9, 10, 11}, 200.0);
+ st3 = st;
+ print_simplex_filtration(st3, "First copy assignment from the default Simplex_tree");
+ Simplex_tree st4;
+ st4 = st;
+ print_simplex_filtration(st4, "Second copy assignment from the default Simplex_tree");
+
+ // Cross check
+ BOOST_CHECK(st3 == st4);
+ BOOST_CHECK(st == st4);
+ BOOST_CHECK(st3 == st);
+
+ st = st;
+ print_simplex_filtration(st4, "Third self copy assignment from the default Simplex_tree");
+
+ BOOST_CHECK(st3 == st);
+
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST OF MOVE CONSTRUCTOR" << std::endl;
+ Simplex_tree st5(std::move(st1));
+ print_simplex_filtration(st5, "First move constructor from the default Simplex_tree");
+ print_simplex_filtration(st1, "First moved Simplex_tree shall be empty");
+ Simplex_tree st6(std::move(st2));
+ print_simplex_filtration(st6, "Second move constructor from the default Simplex_tree");
+ print_simplex_filtration(st2, "Second moved Simplex_tree shall be empty");
+
+ // Cross check
+ BOOST_CHECK(st5 == st6);
+ BOOST_CHECK(st == st6);
+ BOOST_CHECK(st5 == st);
+
+ Simplex_tree empty_st;
+ BOOST_CHECK(st1 == st2);
+ BOOST_CHECK(empty_st == st2);
+ BOOST_CHECK(st1 == empty_st);
+
+ std::cout << "********************************************************************" << std::endl;
+ std::cout << "TEST OF MOVE ASSIGNMENT" << std::endl;
+
+ Simplex_tree st7;
+ // To check there is no memory leak
+ st7.insert_simplex_and_subfaces({9, 10, 11}, 200.0);
+ st7 = std::move(st3);
+ print_simplex_filtration(st7, "First move assignment from the default Simplex_tree");
+ Simplex_tree st8;
+ st8 = std::move(st4);
+ print_simplex_filtration(st8, "Second move assignment from the default Simplex_tree");
+
+ // Cross check
+ BOOST_CHECK(st7 == st8);
+ BOOST_CHECK(st == st8);
+ BOOST_CHECK(st7 == st);
+
+ st = std::move(st);
+ print_simplex_filtration(st, "Third self move assignment from the default Simplex_tree");
+
+ BOOST_CHECK(st7 == st);
+
+}
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index f63ea080..b27bbce8 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -864,34 +864,60 @@ BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) {
}
-BOOST_AUTO_TEST_CASE(insert_graph) {
+
+typedef boost::mpl::list<boost::adjacency_list<boost::setS, boost::vecS, boost::directedS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>,
+ boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>,
+ boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>,
+ boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>,
+ boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>,
+ boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
+ boost::property<vertex_filtration_t, double>,
+ boost::property<edge_filtration_t, double>>> list_of_graph_variants;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insert_graph, Graph, list_of_graph_variants) {
std::cout << "********************************************************************" << std::endl;
std::cout << "INSERT GRAPH" << std::endl;
- typedef typename boost::adjacency_list<boost::vecS, boost::vecS,
- boost::undirectedS,
- boost::property<vertex_filtration_t, double>,
- boost::property<edge_filtration_t, double>> Graph;
+
Graph g(3);
// filtration value 0 everywhere
put(Gudhi::vertex_filtration_t(), g, 0, 0);
put(Gudhi::vertex_filtration_t(), g, 1, 0);
put(Gudhi::vertex_filtration_t(), g, 2, 0);
// vertices don't always occur in sorted order
- add_edge(0, 1, 0, g);
- add_edge(2, 1, 0, g);
- add_edge(2, 0, 0, g);
+ add_edge(0, 1, 1.1, g);
+ add_edge(2, 0, 2.2, g);
+ add_edge(2, 1, 3.3, g);
- typedef Simplex_tree<> typeST;
- typeST st1;
+ Simplex_tree<> st1;
st1.insert_graph(g);
BOOST_CHECK(st1.num_simplices() == 6);
// edges can have multiplicity in the graph unless we replace the first vecS with (hash_)setS
- add_edge(1, 0, 0, g);
- add_edge(1, 2, 0, g);
- add_edge(0, 2, 0, g);
- add_edge(0, 2, 0, g);
- typeST st2;
+ add_edge(1, 0, 1.1, g);
+ add_edge(1, 2, 3.3, g);
+ add_edge(0, 2, 2.2, g);
+ add_edge(0, 1, 1.1, g);
+ add_edge(2, 1, 3.3, g);
+ add_edge(2, 0, 2.2, g);
+ Simplex_tree<> st2;
st2.insert_graph(g);
BOOST_CHECK(st2.num_simplices() == 6);
+
+ std::cout << "st1 is" << std::endl;
+ std::cout << st1 << std::endl;
+
+ std::cout << "st2 is" << std::endl;
+ std::cout << st2 << std::endl;
+
+ BOOST_CHECK(st1 == st2);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-01 14:11:42 +0000