From f7090b7ea2f54eb69f31b0199cf4d2dcf5382668 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 24 Jun 2015 09:56:01 +0000 Subject: Copy - Move - print_tree - main.cpp (building a simple Simplex_tree now works) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@639 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 24b8cdf7b1787ceeb415bbb978d69fdb2a1fe407 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 78 ++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b79e3c8f..7307085e 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -26,11 +26,13 @@ #include #include #include +#include #include #include #include #include +#include #include #include @@ -289,6 +291,55 @@ class Simplex_tree { dimension_(-1) { } + /** \brief Copy; copy the whole tree structure. */ + Simplex_tree(Simplex_tree& copy) : root_(NULL, -1) + { + null_vertex_ = copy.null_vertex_; + threshold_ = copy.threshold_; + num_simplices_ = copy.num_simplices_; + filtration_vect_ = copy.filtration_vect_; + dimension_ = copy.dimension_; + std::vector v; + for (auto sh = copy.root_.members().begin(); sh != copy.root_.members().end(); ++sh) + { + v.push_back(sh->first); + if (has_children(sh)) { + rec_copy(sh->second.children(), v); + } + else { + insert_simplex(v, sh->second.filtration()); + } + v.pop_back(); + } + } + + /** rec_copy: DFS, inserts simplices when reaching a leaf.*/ + void rec_copy(Siblings * sib, std::vector v) + { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + { + v.push_back(sh->first); + if (has_children(sh)) { + rec_copy(sh->second.children(), v); + } + else { + insert_simplex(v, sh->second.filtration()); + } + v.pop_back(); + } + } + + + /** \brief Move; moves the whole tree structure. */ + Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), filtration_vect_(std::move(old.filtration_vect_)) + { + dimension_ = std::move(old.dimension_); + num_simplices_ = std::move(old.num_simplices_); + old.dimension_ = -1; + old.num_simplices_ = 0; + root_ = std::move(old.root_); + } + /** \brief Destructor; deallocates the whole tree structure. */ ~Simplex_tree() { for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) { @@ -309,12 +360,37 @@ class Simplex_tree { delete sib; } + public: + /** \brief print_tree: prints the tree in a hierarchical manner. */ + void print_tree() + { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) + { + std::cout << sh->first << " "; + if (has_children(sh)) + rec_print(sh->second.children()); + std::cout << std::endl; + } + } + + private: + /** rec_print: prints the tree recursively, using DFS. */ + void rec_print(Siblings * sib) + { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + { + std::cout << sh->first << " "; + if (has_children(sh)) + rec_print(sh->second.children()); + } + } + public: /** \brief Returns the key associated to a simplex. * * The filtration must be initialized. */ Simplex_key key(Simplex_handle sh) { - return sh->second.key(); + return sh->second.key(); } /** \brief Returns the simplex associated to a key. * -- cgit v1.2.3 From f480e331debb810dcc843d865b8f3e07a6b10d0a Mon Sep 17 00:00:00 2001 From: anmoreau Date: Thu, 25 Jun 2015 09:50:25 +0000 Subject: Fix find and insert functions : they now sort a copy of the given range before the recursive calls. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@646 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d45b7e23500076d44c88a44671bd0dd47ebdbbc2 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 99 +++++++++++++++--------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 1 + 2 files changed, 64 insertions(+), 36 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7307085e..714c6dfc 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -473,15 +473,22 @@ class Simplex_tree { */ template Simplex_handle find(RandomAccessVertexRange & s) { - if (s.begin() == s.end()) - std::cerr << "Empty simplex \n"; + std::vector copy = s; + sort(s.begin(), s.end()); + return find_rec(s); + } - sort(s.begin(), s.end()); + private: + /** recursive function of find */ + template + Simplex_handle find_rec(RandomAccessVertexRange & simplex) { + if (simplex.begin() == simplex.end()) + return null_simplex(); Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; - Vertex_handle last = s[s.size() - 1]; - for (auto v : s) { + Vertex_handle last = simplex[simplex.size() - 1]; + for (auto v : simplex) { tmp_dit = tmp_sib->members_.find(v); if (tmp_dit == tmp_sib->members_.end()) { return null_simplex(); @@ -501,38 +508,14 @@ class Simplex_tree { } //{ return root_.members_.find(v); } - /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. - * - * @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 - * 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 filed of the - * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to - * null_simplex. - * - * All subsimplices do not necessary need to be already in the simplex tree to proceed to an - * insertion. However, the property of being a simplicial complex will be violated. This allows - * us to insert a stream of simplices contained in a simplicial complex without considering any - * order on them. - * - * The filtration value - * assigned to the new simplex must preserve the monotonicity of the filtration. - * - * The type RandomAccessVertexRange must be a range for which .begin() and - * .end() return random access iterators, with 'value_type' Vertex_handle. */ + private: + /** Recursively insert a simplex */ template - std::pair insert_simplex(RandomAccessVertexRange & simplex, + std::pair insert_simplex_rec(RandomAccessVertexRange & simplex, Filtration_value filtration) { if (simplex.empty()) { return std::pair(null_simplex(), true); } - - sort(simplex.begin(), simplex.end()); // must be sorted in increasing order - Siblings * curr_sib = &root_; std::pair res_insert; typename RandomAccessVertexRange::iterator vi; @@ -541,7 +524,7 @@ class Simplex_tree { if (!(has_children(res_insert.first))) { res_insert.first->second.assign_children(new Siblings(curr_sib, *vi)); } - curr_sib = res_insert.first->second.children(); + curr_sib = res_insert.first->second.children(); } res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!res_insert.second) { // if already in the complex @@ -554,7 +537,37 @@ class Simplex_tree { // otherwise the insertion has succeeded return res_insert; } - +public: + /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. + * + * @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 + * 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 filed of the + * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to + * null_simplex. + * + * All subsimplices do not necessary need to be already in the simplex tree to proceed to an + * insertion. However, the property of being a simplicial complex will be violated. This allows + * us to insert a stream of simplices contained in a simplicial complex without considering any + * order on them. + * + * The filtration value + * assigned to the new simplex must preserve the monotonicity of the filtration. + * + * The type RandomAccessVertexRange must be a range for which .begin() and + * .end() return random access iterators, with 'value_type' Vertex_handle. */ +template +std::pair insert_simplex(RandomAccessVertexRange & simplex, + Filtration_value filtration) { + std::vector copy = simplex; + sort(copy.begin(), copy.end()); + return insert_simplex_rec(copy, filtration); +} /** \brief Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of * Vertex_handles, in the simplicial complex. @@ -565,6 +578,18 @@ class Simplex_tree { template void insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, Filtration_value filtration = 0.0) { + RandomAccessVertexRange copy(Nsimplex); + sort(copy.begin(), copy.end()); // must be sorted in increasing order + insert_simplex_and_subfaces_rec(copy, filtration); + } + + private: + + /** Recursively insert simplex and all of its subfaces */ + template + void insert_simplex_and_subfaces_rec(RandomAccessVertexRange & Nsimplex, + Filtration_value filtration = 0.0) { + if (Nsimplex.size() > 1) { for (unsigned int NIndex = 0; NIndex < Nsimplex.size(); NIndex++) { // insert N (N-1)-Simplex @@ -577,13 +602,13 @@ class Simplex_tree { insert_simplex_and_subfaces(NsimplexMinusOne, filtration); } // N-Simplex insert - std::pair returned = insert_simplex(Nsimplex, filtration); + std::pair returned = insert_simplex_rec(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } } else if (Nsimplex.size() == 1) { // 1-Simplex insert - End of recursivity - std::pair returned = insert_simplex(Nsimplex, filtration); + std::pair returned = insert_simplex_rec(Nsimplex, filtration); if (returned.second == true) { num_simplices_++; } @@ -592,6 +617,8 @@ class Simplex_tree { } } + public: + /** \brief Assign a value 'key' to the key of the simplex * represented by the Simplex_handle 'sh'. */ void assign_key(Simplex_handle sh, Simplex_key key) { diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index fdd1a5be..b5c201d9 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -130,6 +130,7 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p BOOST_CHECK( AreAlmostTheSame(simplexTree.filtration(*f_simplex),simplex.second) ); int simplexIndex=simplex.first.size()-1; + std::sort(simplex.first.begin(), simplex.first.end()); // if the simplex wasn't sorted, the next test could fail for( auto vertex : simplexTree.simplex_vertex_range(*f_simplex) ) { std::cout << "test_simplex_tree_contains - vertex=" << vertex << "||" << simplex.first.at(simplexIndex) << std::endl; -- cgit v1.2.3 From e50c1af62d8ede46e151c898beec37c2dda4b142 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Thu, 25 Jun 2015 12:06:37 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@651 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 15429d17efd5a58985e03f00b585f6cbc864227a --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 714c6dfc..81867a25 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -368,20 +368,28 @@ class Simplex_tree { { std::cout << sh->first << " "; if (has_children(sh)) + { + std::cout << "("; rec_print(sh->second.children()); + std::cout << ")"; + } std::cout << std::endl; } } - private: /** rec_print: prints the tree recursively, using DFS. */ + private: void rec_print(Siblings * sib) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { std::cout << sh->first << " "; if (has_children(sh)) + { + std::cout << "("; rec_print(sh->second.children()); + std::cout << ")"; + } } } -- cgit v1.2.3 From 227cadacd804fead2222cf2897a04262fd430dcf Mon Sep 17 00:00:00 2001 From: anmoreau Date: Thu, 25 Jun 2015 14:00:07 +0000 Subject: operator == instead of print_tree git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@652 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: f3848ccb53d732eb6a0059ca7f7c453b30391c1c --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 187 ++++++++++++----------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 12 +- 2 files changed, 105 insertions(+), 94 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 81867a25..79c7cd2e 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -361,36 +361,45 @@ class Simplex_tree { } public: - /** \brief print_tree: prints the tree in a hierarchical manner. */ - void print_tree() + + + /** \brief Checks whether or not two simplex trees are equal. */ + bool operator ==(Simplex_tree st2) { - for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) + if (root_.members().size() != st2.root()->members().size()) + return false; + for (auto sh1 = root_.members().begin(), sh2 = st2.root()->members().begin(); sh1 != root_.members().end(); ++sh1, ++sh2) { - std::cout << sh->first << " "; - if (has_children(sh)) - { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } - std::cout << std::endl; + if (sh1->first != sh2->first) + return false; + if (has_children(sh1)) + return rec_equal(sh1->second.children(), sh2->second.children()); + else if (has_children(sh2)) + return false; + else + return true; } + return true; } - /** rec_print: prints the tree recursively, using DFS. */ + /** rec_equal: Checks recursively whether or not two simplex trees are equal, using DFS. */ private: - void rec_print(Siblings * sib) + bool rec_equal(Siblings * s1, Siblings * s2) { - for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + if (s1->members().size() != s2->members().size()) + return false; + for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); sh1 != s1->members().end(); ++sh1, ++sh2) { - std::cout << sh->first << " "; - if (has_children(sh)) - { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } + if (sh1->first != sh2->first) + return false; + if (has_children(sh1)) + return rec_equal(sh1->second.children(), sh2->second.children()); + else if (has_children(sh2)) + return false; + else + return true; } + return true; } public: @@ -404,82 +413,82 @@ class Simplex_tree { * * The filtration must be initialized. */ Simplex_handle simplex(Simplex_key key) { - return filtration_vect_[key]; + return filtration_vect_[key]; } /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ Filtration_value filtration(Simplex_handle sh) { - if (sh != null_simplex()) { - return sh->second.filtration(); - } else { - return INFINITY; - } // filtration(); } - } - /** \brief Returns an upper bound of the filtration values of the simplices. */ - Filtration_value filtration() { - return threshold_; - } - /** \brief Returns a Simplex_handle different from all Simplex_handles - * associated to the simplices in the simplicial complex. - * - * One can call filtration(null_simplex()). */ - Simplex_handle null_simplex() { - return Dictionary_it(NULL); - } - /** \brief Returns a key different for all keys associated to the - * simplices of the simplicial complex. */ - Simplex_key null_key() { - return -1; - } - /** \brief Returns a Vertex_handle different from all Vertex_handles associated - * to the vertices of the simplicial complex. */ - Vertex_handle null_vertex() { - return null_vertex_; - } - /** \brief Returns the number of vertices in the complex. */ - size_t num_vertices() { - return root_.members_.size(); - } - /** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ - const unsigned int& num_simplices() const { - return num_simplices_; - } + if (sh != null_simplex()) { + return sh->second.filtration(); + } else { + return INFINITY; + } // filtration(); } +} +/** \brief Returns an upper bound of the filtration values of the simplices. */ +Filtration_value filtration() { + return threshold_; +} +/** \brief Returns a Simplex_handle different from all Simplex_handles + * associated to the simplices in the simplicial complex. + * + * One can call filtration(null_simplex()). */ +Simplex_handle null_simplex() { + return Dictionary_it(NULL); +} +/** \brief Returns a key different for all keys associated to the + * simplices of the simplicial complex. */ +Simplex_key null_key() { + return -1; +} +/** \brief Returns a Vertex_handle different from all Vertex_handles associated + * to the vertices of the simplicial complex. */ +Vertex_handle null_vertex() { + return null_vertex_; +} +/** \brief Returns the number of vertices in the complex. */ +size_t num_vertices() { + return root_.members_.size(); +} +/** \brief Returns the number of simplices in the complex. + * + * Does not count the empty simplex. */ +const unsigned int& num_simplices() const { + return num_simplices_; +} - /** \brief Returns the dimension of a simplex. - * - * Must be different from null_simplex().*/ - int dimension(Simplex_handle sh) { - Siblings * curr_sib = self_siblings(sh); - int dim = 0; - while (curr_sib != NULL) { - ++dim; - curr_sib = curr_sib->oncles(); - } - return dim - 1; - } - /** \brief Returns an upper bound on the dimension of the simplicial complex. */ - int dimension() { - return dimension_; - } +/** \brief Returns the dimension of a simplex. + * + * Must be different from null_simplex().*/ +int dimension(Simplex_handle sh) { + Siblings * curr_sib = self_siblings(sh); + int dim = 0; + while (curr_sib != NULL) { + ++dim; + curr_sib = curr_sib->oncles(); + } + return dim - 1; +} +/** \brief Returns an upper bound on the dimension of the simplicial complex. */ +int dimension() { + return dimension_; +} - /** \brief Returns true iff the node in the simplex tree pointed by - * sh has children.*/ - bool has_children(Simplex_handle sh) { - return (sh->second.children()->parent() == sh->first); - } +/** \brief Returns true iff the node in the simplex tree pointed by + * sh has children.*/ +bool has_children(Simplex_handle sh) { + return (sh->second.children()->parent() == sh->first); +} - /** \brief Given a range of Vertex_handles, returns the Simplex_handle - * of the simplex in the simplicial complex containing the corresponding - * vertices. Return null_simplex() if the simplex is not in the complex. - * - * The type RandomAccessVertexRange must be a range for which .begin() and - * .end() return random access iterators, with value_type - * Vertex_handle. - */ - template +/** \brief Given a range of Vertex_handles, returns the Simplex_handle + * of the simplex in the simplicial complex containing the corresponding + * vertices. Return null_simplex() if the simplex is not in the complex. + * + * The type RandomAccessVertexRange must be a range for which .begin() and + * .end() return random access iterators, with value_type + * Vertex_handle. + */ +template Simplex_handle find(RandomAccessVertexRange & s) { std::vector copy = s; sort(s.begin(), s.end()); diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index b5c201d9..1e05f8e8 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -592,18 +592,20 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << "Printing st" << std::endl; std::cout << &st << std::endl; std::cout << st; // Vertices test - st.print_tree(); // Hierarchy test - typeST st3 = st, st_move = std::move(st); +// st.print_tree(); // Hierarchy test + typeST st3 = st; + BOOST_CHECK(st == st3); + typeST st_move = std::move(st); std::cout << "Printing a copy of st" << std::endl; std::cout << &st3 << std::endl; std::cout << st3; - st3.print_tree(); +// st3.print_tree(); std::cout << "Printing a move of st" << std::endl; std::cout << &st_move << std::endl; std::cout << st_move; - st_move.print_tree(); +// st_move.print_tree(); std::cout << "Printing st again" << std::endl; std::cout << &st << std::endl; std::cout << st; - st.print_tree(); +// st.print_tree(); } -- cgit v1.2.3 From 67b00eb17785cf8abb08055a83b631904b9c5746 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Fri, 26 Jun 2015 15:05:38 +0000 Subject: fix + edge_contraction + print_tree git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@657 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 2c63af50eec59e37e933e6bd7e1810de943e9b48 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 69 ++++++++++++++++++++++- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 71 +++++++++++++++++------- 2 files changed, 118 insertions(+), 22 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 79c7cd2e..63671d63 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -314,7 +314,8 @@ class Simplex_tree { } /** rec_copy: DFS, inserts simplices when reaching a leaf.*/ - void rec_copy(Siblings * sib, std::vector v) + template + void rec_copy(Siblings * sib, RandomAccessVertexRange v) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { @@ -361,7 +362,40 @@ class Simplex_tree { } public: + /** \brief Prints the simplex_tree hierarchically. */ + void print_tree() + { + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) + { + std::cout << sh->first << " "; + if (has_children(sh)) + { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + std::cout << std::endl; + } + } + + + /** \brief Recursively prints the simplex_tree, using DFS. */ + private: + void rec_print(Siblings * sib) + { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + { + std::cout << " " << sh->first << " "; + if (has_children(sh)) + { + std::cout << "("; + rec_print(sh->second.children()); + std::cout << ")"; + } + } + } + public: /** \brief Checks whether or not two simplex trees are equal. */ bool operator ==(Simplex_tree st2) @@ -490,7 +524,7 @@ bool has_children(Simplex_handle sh) { */ template Simplex_handle find(RandomAccessVertexRange & s) { - std::vector copy = s; + RandomAccessVertexRange copy = s; sort(s.begin(), s.end()); return find_rec(s); } @@ -581,7 +615,7 @@ public: template std::pair insert_simplex(RandomAccessVertexRange & simplex, Filtration_value filtration) { - std::vector copy = simplex; + RandomAccessVertexRange copy = simplex; sort(copy.begin(), copy.end()); return insert_simplex_rec(copy, filtration); } @@ -720,6 +754,35 @@ std::pair insert_simplex(RandomAccessVertexRange & simplex is_before_in_filtration(this)); } +/** \brief Contracts two edges + \param deleted The base of the edge to be contracted + \param remaining The new vertex with children and variables of the former +*/ + void edge_contraction(Simplex_handle & deleted, Simplex_handle & remaining) + { + Siblings * sibDeleted, * sibRemaining; // We need the siblings + sibDeleted = (has_children(deleted) ? deleted->second.children()->oncles() : deleted->second.children()); + sibRemaining = (has_children(remaining) ? remaining->second.children()->oncles() : remaining->second.children()); + // Add all edges to vertex + if (has_children(deleted)) + { + std::deque v; + Vertex_handle vertex = sibRemaining->parent_; + Siblings * sib_tmp = sibRemaining->oncles(); + while (vertex != -1) + { + v.push_front(vertex); + vertex = sib_tmp->parent_; + sib_tmp = sib_tmp->oncles(); + } + v.push_back(remaining->first); + v.push_back(deleted->first); + rec_copy(deleted->second.children(), v); + } + // Delete the contracted edge + sibDeleted->members().erase(deleted->first); + } + private: /** \brief Returns true iff the list of vertices of sh1 * is smaller than the list of vertices of sh2 w.r.t. diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 1f99cfe7..7ab5c24e 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -588,23 +588,56 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << std::endl; } - // TEST Copy constructor / Move - std::cout << "Printing st" << std::endl; - std::cout << &st << std::endl; - std::cout << st; - typeST st3 = st; - BOOST_CHECK(st == st3); - typeST st_move = std::move(st); - std::cout << "Printing a copy of st" << std::endl; - std::cout << &st3 << std::endl; - std::cout << st3; - BOOST_CHECK(st_move == st3); - std::cout << "Printing a move of st" << std::endl; - std::cout << &st_move << std::endl; - std::cout << st_move; - typeST st_empty; - BOOST_CHECK(st == st_empty); - std::cout << "Printing st again" << std::endl; - std::cout << &st << std::endl; - std::cout << st; + std::cout << "********************************************************************" << std::endl; + // TEST Copy constructor / Move + std::cout << "Printing st" << std::endl; + std::cout << &st << std::endl; + st.print_tree(); + typeST st_copy_1 = st; + BOOST_CHECK(st == st_copy_1); + typeST st_move = std::move(st); + std::cout << "Printing a copy of st" << std::endl; + std::cout << &st_copy_1 << std::endl; + st_copy_1.print_tree(); + BOOST_CHECK(st_move == st_copy_1); + std::cout << "Printing a move of st" << std::endl; + std::cout << &st_move << std::endl; + st_move.print_tree(); + typeST st_empty; + BOOST_CHECK(st == st_empty); + std::cout << "Printing st again" << std::endl; + std::cout << &st << std::endl; + st.print_tree(); + + std::cout << "********************************************************************" << std::endl; + // TEST Edge_contraction + typeST st_copy_2 = st_copy_1, st_copy_3 = st_copy_1; + std::vector v1, v2; + v1.push_back(3); + v2.push_back(0); + typeST::Simplex_handle s1; + typeST::Simplex_handle s2; + s1 = st_copy_1.find(v1); + s2 = st_copy_1.find(v2); + st_copy_1.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (3, 0) contracted, 3 being contracted in 0" << std::endl; + st_copy_1.print_tree(); + v1.clear(); + v2.clear(); + v1.push_back(3); + v2.push_back(1); + s1 = st_copy_2.find(v1); + s2 = st_copy_2.find(v2); + st_copy_2.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (3, 1) contracted, 3 being contracted in 1" << std::endl; + st_copy_2.print_tree(); + v1.clear(); + v2.clear(); + v1.push_back(4); + v2.push_back(3); + s1 = st_copy_3.find(v1); + s2 = st_copy_3.find(v2); + st_copy_3.edge_contraction(s1, s2); + std::cout << "Printing a copy of st, with the edge (4, 3) contracted, 4 being contracted in 3" << std::endl; + st_copy_3.print_tree(); } -- cgit v1.2.3 From 46eb14219834599b247ffe8053931262927a3014 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Sun, 28 Jun 2015 21:00:20 +0000 Subject: Multiple fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@658 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 85d3c8664e3191911e02189cdd33bf4c022638cd --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 37 +++++++++++++++------------ 1 file changed, 21 insertions(+), 16 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 63671d63..e4de5571 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -522,17 +522,18 @@ bool has_children(Simplex_handle sh) { * .end() return random access iterators, with value_type * Vertex_handle. */ -template - Simplex_handle find(RandomAccessVertexRange & s) { - RandomAccessVertexRange copy = s; - sort(s.begin(), s.end()); - return find_rec(s); +template + Simplex_handle find(const InputVertexRange & s) { + std::vector copy; + for (auto v = std::begin(s); v != std::end(s); ++v ) + copy.push_back(*v); + sort(std::begin(copy), std::end(copy)); + return find_rec(copy); } private: /** recursive function of find */ - template - Simplex_handle find_rec(RandomAccessVertexRange & simplex) { + Simplex_handle find_rec(std::vector & simplex) { if (simplex.begin() == simplex.end()) return null_simplex(); @@ -561,7 +562,7 @@ template private: /** Recursively insert a simplex */ - template + template std::pair insert_simplex_rec(RandomAccessVertexRange & simplex, Filtration_value filtration) { if (simplex.empty()) { @@ -613,10 +614,12 @@ public: * The type RandomAccessVertexRange must be a range for which .begin() and * .end() return random access iterators, with 'value_type' Vertex_handle. */ template -std::pair insert_simplex(RandomAccessVertexRange & simplex, +std::pair insert_simplex(const RandomAccessVertexRange & simplex, Filtration_value filtration) { - RandomAccessVertexRange copy = simplex; - sort(copy.begin(), copy.end()); + std::vector copy; + for (auto v = std::begin(simplex); v != std::end(simplex); ++v) + copy.push_back(*v); + sort(std::begin(copy), std::end(copy)); return insert_simplex_rec(copy, filtration); } @@ -626,18 +629,20 @@ std::pair insert_simplex(RandomAccessVertexRange & simplex * @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. */ - template - void insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, + template + void insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, Filtration_value filtration = 0.0) { - RandomAccessVertexRange copy(Nsimplex); - sort(copy.begin(), copy.end()); // must be sorted in increasing order + std::vector copy; + for (auto v = std::begin(Nsimplex); v != std::end(Nsimplex); ++v) + copy.push_back(*v); + sort(std::begin(copy), std::end(copy)); insert_simplex_and_subfaces_rec(copy, filtration); } private: /** Recursively insert simplex and all of its subfaces */ - template + template void insert_simplex_and_subfaces_rec(RandomAccessVertexRange & Nsimplex, Filtration_value filtration = 0.0) { -- cgit v1.2.3 From e290cf6b6872e6a2eac136feb87fddc77d24c9d2 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 6 Jul 2015 11:28:28 +0000 Subject: Fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@681 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 4024156075d59cc47d12531162626a9cc68a0d2e --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 47 +++++++-------------------- 1 file changed, 11 insertions(+), 36 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index e4de5571..0ed554d3 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -292,25 +292,10 @@ class Simplex_tree { } /** \brief Copy; copy the whole tree structure. */ - Simplex_tree(Simplex_tree& copy) : root_(NULL, -1) + Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), num_simplices_(copy.num_simplices_), root_(NULL, -1), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) { - null_vertex_ = copy.null_vertex_; - threshold_ = copy.threshold_; - num_simplices_ = copy.num_simplices_; - filtration_vect_ = copy.filtration_vect_; - dimension_ = copy.dimension_; std::vector v; - for (auto sh = copy.root_.members().begin(); sh != copy.root_.members().end(); ++sh) - { - v.push_back(sh->first); - if (has_children(sh)) { - rec_copy(sh->second.children(), v); - } - else { - insert_simplex(v, sh->second.filtration()); - } - v.pop_back(); - } + rec_copy(©.root_, v); } /** rec_copy: DFS, inserts simplices when reaching a leaf.*/ @@ -332,13 +317,10 @@ class Simplex_tree { /** \brief Move; moves the whole tree structure. */ - Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), filtration_vect_(std::move(old.filtration_vect_)) + Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), num_simplices_(std::move(old.num_simplices_)), root_(std::move(old.root_)), filtration_vect_(std::move(old.filtration_vect_)), dimension_(std::move(old.dimension_)) { - dimension_ = std::move(old.dimension_); - num_simplices_ = std::move(old.num_simplices_); old.dimension_ = -1; old.num_simplices_ = 0; - root_ = std::move(old.root_); } /** \brief Destructor; deallocates the whole tree structure. */ @@ -518,16 +500,13 @@ bool has_children(Simplex_handle sh) { * of the simplex in the simplicial complex containing the corresponding * vertices. Return null_simplex() if the simplex is not in the complex. * - * The type RandomAccessVertexRange must be a range for which .begin() and - * .end() return random access iterators, with value_type - * Vertex_handle. + * The type InputVertexRange must be a range of Vertex_handle + * on which we can call std::begin() function */ template Simplex_handle find(const InputVertexRange & s) { - std::vector copy; - for (auto v = std::begin(s); v != std::end(s); ++v ) - copy.push_back(*v); - sort(std::begin(copy), std::end(copy)); + std::vector copy(std::begin(s), std::end(s)); + std::sort(std::begin(copy), std::end(copy)); return find_rec(copy); } @@ -616,10 +595,8 @@ public: template std::pair insert_simplex(const RandomAccessVertexRange & simplex, Filtration_value filtration) { - std::vector copy; - for (auto v = std::begin(simplex); v != std::end(simplex); ++v) - copy.push_back(*v); - sort(std::begin(copy), std::end(copy)); + std::vector copy(std::begin(simplex), std::end(simplex));; + std::sort(std::begin(copy), std::end(copy)); return insert_simplex_rec(copy, filtration); } @@ -632,10 +609,8 @@ std::pair insert_simplex(const RandomAccessVertexRange & s template void insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, Filtration_value filtration = 0.0) { - std::vector copy; - for (auto v = std::begin(Nsimplex); v != std::end(Nsimplex); ++v) - copy.push_back(*v); - sort(std::begin(copy), std::end(copy)); + std::vector copy(std::begin(Nsimplex), std::end(Nsimplex));; + std::sort(std::begin(copy), std::end(copy)); insert_simplex_and_subfaces_rec(copy, filtration); } -- cgit v1.2.3 From f06671819213604e26778bf40113e22b8996c3ee Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 5 Aug 2015 13:36:42 +0000 Subject: several fixes git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@724 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 8eb82645458ae536d1cba8682a50880ba377cb7f --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 142 +++++++++++++++-------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 36 ++---- 2 files changed, 103 insertions(+), 75 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 0ed554d3..5eef283e 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -239,8 +239,7 @@ class Simplex_tree { Filtration_simplex_range filtration_simplex_range(Indexing_tag) { if (filtration_vect_.empty()) { initialize_filtration(); - } - return Filtration_simplex_range(filtration_vect_.begin(), + } return Filtration_simplex_range(filtration_vect_.begin(), filtration_vect_.end()); } @@ -292,35 +291,33 @@ class Simplex_tree { } /** \brief Copy; copy the whole tree structure. */ - Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), num_simplices_(copy.num_simplices_), root_(NULL, -1), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) - { - std::vector v; - rec_copy(©.root_, v); + Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), num_simplices_(copy.num_simplices_), root_(NULL, -1, std::vector> (copy.root_.members().begin(), copy.root_.members().end())), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) { + rec_copy(&root_, ©.root_); } - /** rec_copy: DFS, inserts simplices when reaching a leaf.*/ - template - void rec_copy(Siblings * sib, RandomAccessVertexRange v) + /** rec_copy: depth first search, inserts simplices when reaching a leaf.*/ + void rec_copy(Siblings *sib, Siblings *sib_copy) { - for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) - { - v.push_back(sh->first); - if (has_children(sh)) { - rec_copy(sh->second.children(), v); - } - else { - insert_simplex(v, sh->second.filtration()); - } - v.pop_back(); - } + for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); sh != sib->members().end(); ++sh, ++sh_copy) { + if (has_children(sh_copy)) { + std::vector> v(sh_copy->second.children()->members().begin(), sh_copy->second.children()->members().end()); + Siblings * newsib = new Siblings (sib, sh_copy->first); + for (auto it = v.begin(); it != v.end(); ++it) + newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); + rec_copy(newsib, sh_copy->second.children()); + sh->second.assign_children(newsib); + } + } } + + /** \brief Move; moves the whole tree structure. */ - Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), num_simplices_(std::move(old.num_simplices_)), root_(std::move(old.root_)), filtration_vect_(std::move(old.filtration_vect_)), dimension_(std::move(old.dimension_)) - { + Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), num_simplices_(std::move(old.num_simplices_)), root_(std::move(old.root_)), filtration_vect_(std::move(old.filtration_vect_)), dimension_(std::move(old.dimension_)) { old.dimension_ = -1; old.num_simplices_ = 0; + old.threshold_ = 0; } /** \brief Destructor; deallocates the whole tree structure. */ @@ -361,7 +358,7 @@ class Simplex_tree { } - /** \brief Recursively prints the simplex_tree, using DFS. */ + /** \brief Recursively prints the simplex_tree, using depth first search. */ private: void rec_print(Siblings * sib) { @@ -382,11 +379,11 @@ class Simplex_tree { /** \brief Checks whether or not two simplex trees are equal. */ bool operator ==(Simplex_tree st2) { - if (root_.members().size() != st2.root()->members().size()) + if (root_.members().size() != st2.root()->members().size() || this->null_vertex_ != st2.null_vertex_ || this->threshold_ != st2.threshold_ || this->num_simplices_ != st2.num_simplices_ || this->dimension_ != st2.dimension_) return false; for (auto sh1 = root_.members().begin(), sh2 = st2.root()->members().begin(); sh1 != root_.members().end(); ++sh1, ++sh2) { - if (sh1->first != sh2->first) + if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) return false; if (has_children(sh1)) return rec_equal(sh1->second.children(), sh2->second.children()); @@ -398,7 +395,7 @@ class Simplex_tree { return true; } - /** rec_equal: Checks recursively whether or not two simplex trees are equal, using DFS. */ + /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ private: bool rec_equal(Siblings * s1, Siblings * s2) { @@ -406,7 +403,7 @@ class Simplex_tree { return false; for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); sh1 != s1->members().end(); ++sh1, ++sh2) { - if (sh1->first != sh2->first) + if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) return false; if (has_children(sh1)) return rec_equal(sh1->second.children(), sh2->second.children()); @@ -734,33 +731,80 @@ std::pair insert_simplex(const RandomAccessVertexRange & s is_before_in_filtration(this)); } -/** \brief Contracts two edges - \param deleted The base of the edge to be contracted - \param remaining The new vertex with children and variables of the former +/** \brief Contracts two edges : the contracted edge is erased from the three, and the remaining edge receives all the links of the contracted one. + \param remaining The value of the vertex within the other is contracted + \param deleted The value of the vertex to be contracted */ - void edge_contraction(Simplex_handle & deleted, Simplex_handle & remaining) + void edge_contraction(Vertex_handle remaining, Vertex_handle deleted) { - Siblings * sibDeleted, * sibRemaining; // We need the siblings - sibDeleted = (has_children(deleted) ? deleted->second.children()->oncles() : deleted->second.children()); - sibRemaining = (has_children(remaining) ? remaining->second.children()->oncles() : remaining->second.children()); - // Add all edges to vertex - if (has_children(deleted)) - { - std::deque v; - Vertex_handle vertex = sibRemaining->parent_; - Siblings * sib_tmp = sibRemaining->oncles(); - while (vertex != -1) + std::vector accessRemaining, accessDeleted; + accessRemaining.push_back(remaining); + accessDeleted.push_back(deleted); + Simplex_handle shr = find(accessRemaining), shd = find(accessDeleted); + if (has_children(shd)) + { + Siblings * sibDeleted, * sibRemaining; // We need the siblings + sibDeleted = shd->second.children(); + sibRemaining = shr->second.children(); + rec_insert(sibDeleted, sibRemaining, shd->first); + } + rec_delete(&root_, shd->first); + } + + +/** \brief recursively insert the members of a Sibling into another, any time the key exists into the target Sibling + \param sibInserted The sibling to be inserted + \param sibTarget The target sibling on which the other sibling is copied + \param key The key (Vertex_handle) needed to insert the sibling +*/ + void rec_insert(Siblings * sibInserted, Siblings * sibTarget, Vertex_handle key) + { + for (auto sh = sibTarget->members().begin(); sh != sibTarget->members().end(); ++sh) + { + if (has_children(sh)) + rec_insert(sibInserted, sh->second.children(), key); + if (sh->first == key) + insert_members(sibTarget, sibInserted); + } + } + +/** \brief Copy a Sibling into another, which is possibly not empty + \param sibInserted The sibling to be copied + \param sibTarget The sibling on which we wan't to copy the other sibling +*/ + void insert_members(Siblings * sibTarget, Siblings * sibInserted) + { + for (auto sh = sibInserted->members().begin(); sh != sibInserted->members().end(); ++sh) + { + std::pair member(sh->first, Node(sibTarget, sh->second.filtration())); + if (has_children(sh)) { - v.push_front(vertex); - vertex = sib_tmp->parent_; - sib_tmp = sib_tmp->oncles(); + std::cout << "children" << std::endl; + std::vector> v(sh->second.children()->members().begin(), sh->second.children()->members().end()); + Siblings * newsib = new Siblings (sibTarget, sh->first); + for (auto it = v.begin(); it != v.end(); ++it) + newsib->members_.emplace(it->first, Node(sibTarget, it->second.filtration())); + insert_members(newsib, sh->second.children()); + member.second.assign_children(newsib); + } - v.push_back(remaining->first); - v.push_back(deleted->first); - rec_copy(deleted->second.children(), v); + sibTarget->members_.emplace(member); + } + } + +/** \brief Erase every occurencies of a key in a Sibling + \param sib The sibling on which we wan't to erase the elements + \param key The key of the members we wan't to erase +*/ + void rec_delete(Siblings * sib, Vertex_handle key) + { + for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) + { + if (has_children(sh)) + rec_delete(sh->second.children(), key); + if (sh->first == key) + sib->members_.erase(sh); } - // Delete the contracted edge - sibDeleted->members().erase(deleted->first); } private: diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 7ab5c24e..cd690b19 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -611,33 +611,17 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << "********************************************************************" << std::endl; // TEST Edge_contraction - typeST st_copy_2 = st_copy_1, st_copy_3 = st_copy_1; - std::vector v1, v2; - v1.push_back(3); - v2.push_back(0); - typeST::Simplex_handle s1; - typeST::Simplex_handle s2; - s1 = st_copy_1.find(v1); - s2 = st_copy_1.find(v2); - st_copy_1.edge_contraction(s1, s2); - std::cout << "Printing a copy of st, with the edge (3, 0) contracted, 3 being contracted in 0" << std::endl; + typeST st_copy_2 = st_copy_1, st_copy_3 = st_copy_1, st_copy_4 = st_copy_1; + st_copy_1.edge_contraction(0, 3); + std::cout << "Printing a copy of st, with the edge (0, 3) contracted, 3 being contracted in 0" << std::endl; st_copy_1.print_tree(); - v1.clear(); - v2.clear(); - v1.push_back(3); - v2.push_back(1); - s1 = st_copy_2.find(v1); - s2 = st_copy_2.find(v2); - st_copy_2.edge_contraction(s1, s2); - std::cout << "Printing a copy of st, with the edge (3, 1) contracted, 3 being contracted in 1" << std::endl; + st_copy_2.edge_contraction(1, 3); + std::cout << "Printing a copy of st, with the edge (1, 3) contracted, 3 being contracted in 1" << std::endl; st_copy_2.print_tree(); - v1.clear(); - v2.clear(); - v1.push_back(4); - v2.push_back(3); - s1 = st_copy_3.find(v1); - s2 = st_copy_3.find(v2); - st_copy_3.edge_contraction(s1, s2); - std::cout << "Printing a copy of st, with the edge (4, 3) contracted, 4 being contracted in 3" << std::endl; + st_copy_3.edge_contraction(3, 4); + std::cout << "Printing a copy of st, with the edge (3, 4) contracted, 4 being contracted in 3" << std::endl; st_copy_3.print_tree(); + st_copy_4.edge_contraction(1, 6); + std::cout << "Printing a copy of st, with the edge (1, 6) contracted, 6 being contracted in 1" << std::endl; + st_copy_4.print_tree(); } -- cgit v1.2.3 From f98b5a5f13d9657eb6ca924ca9909d4d29c9641a Mon Sep 17 00:00:00 2001 From: glisse Date: Sat, 15 Aug 2015 09:03:52 +0000 Subject: Optionally provide a dummy key/filtration interface instead of storing them for real. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-options@734 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: ea7237a7b5c3d8e2dde49ea8356b142f3efa8089 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 54 ++++++++++++++++++---- .../Simplex_tree_node_explicit_storage.h | 42 +++-------------- 2 files changed, 51 insertions(+), 45 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 153401d6..11c41d1b 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -85,35 +85,71 @@ namespace Gudhi { * \implements FilteredComplex * */ -template + +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 constexpr bool store_key = true; + static constexpr bool store_filtration = true; +}; + +template class Simplex_tree { public: - typedef IndexingTag Indexing_tag; + typedef typename Options::Indexing_tag Indexing_tag; /** \brief Type for the value of the filtration function. * * Must be comparable with <. */ - typedef FiltrationValue Filtration_value; + typedef typename Options::Filtration_value Filtration_value; /** \brief Key associated to each simplex. * * Must be a signed integer type. */ - typedef SimplexKey Simplex_key; + typedef typename Options::Simplex_key Simplex_key; /** \brief Type for the vertex handle. * * Must be a signed integer type. It admits a total order <. */ - typedef VertexHandle Vertex_handle; + typedef typename Options::Vertex_handle Vertex_handle; /* Type of node in the simplex tree. */ typedef Simplex_tree_node_explicit_storage Node; /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */ + // FIXME: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and Simplex_key next to each other). typedef typename boost::container::flat_map Dictionary; /* \brief Set of nodes sharing a same parent in the simplex tree. */ /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings Siblings; + struct Key_simplex_base_real { + Key_simplex_base_real() : key_(-1) {} + void assign_key(Simplex_key k) { key_ = k; } + Simplex_key key() const { return key_; } + private: + Simplex_key key_; + }; + struct Key_simplex_base_dummy { + Key_simplex_base_dummy() {} + void assign_key(Simplex_key) { } + Simplex_key key() const { assert(false); return -1; } + }; + typedef typename std::conditional::type Key_simplex_base; + + struct Filtration_simplex_base_real { + Filtration_simplex_base_real() : filt_(0) {} + void assign_filtration(Filtration_value f) { filt_ = f; } + Filtration_value filtration() const { return filt_; } + private: + Filtration_value filt_; + }; + struct Filtration_simplex_base_dummy { + Filtration_simplex_base_dummy() {} + void assign_filtration(Filtration_value f) { assert(f == 0); } + Filtration_value filtration() const { return 0; } + }; + typedef typename std::conditional::type Filtration_simplex_base; + public: /** \brief Handle type to a simplex contained in the simplicial complex represented * by the simplex tree. */ @@ -456,7 +492,7 @@ class Simplex_tree { * .end() return random access iterators, with 'value_type' Vertex_handle. */ template std::pair insert_simplex(RandomAccessVertexRange & simplex, - Filtration_value filtration) { + Filtration_value filtration = 0) { if (simplex.empty()) { return std::pair(null_simplex(), true); } diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index 1f1a34cc..26d18098 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -39,62 +39,32 @@ namespace Gudhi { * It stores explicitely its own filtration value and its own Simplex_key. */ template -class Simplex_tree_node_explicit_storage { +struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base { public: typedef typename SimplexTree::Siblings Siblings; typedef typename SimplexTree::Filtration_value Filtration_value; typedef typename SimplexTree::Simplex_key Simplex_key; - // Default constructor. - Simplex_tree_node_explicit_storage() - : children_(NULL), - simplex_key_(-1), - filtration_(0) { - } - - Simplex_tree_node_explicit_storage(Siblings * sib, - Filtration_value filtration) - : children_(sib), - simplex_key_(-1), - filtration_(filtration) { - } - - void assign_key(Simplex_key key) { - simplex_key_ = key; + Simplex_tree_node_explicit_storage(Siblings * sib = nullptr, + Filtration_value filtration = 0) + : children_(sib) { + this->assign_filtration(filtration); } /* - * Assign a children to the node + * Assign children to the node */ void assign_children(Siblings * children) { children_ = children; } - /* - * - */ - void assign_filtration(double filtration_value) { - filtration_ = filtration_value; - } - - Filtration_value filtration() { - return filtration_; - } /* Careful -> children_ can be NULL*/ Siblings * children() { return children_; } - Simplex_key key() { - return simplex_key_; - } - private: Siblings * children_; - - // Data attached to simplex, explicit storage - Simplex_key simplex_key_; - Filtration_value filtration_; // value in the filtration }; /* @} */ // end addtogroup simplex_tree -- cgit v1.2.3 From 57fecbe5a89aa4db82ae9cd071966a4201e03463 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 18 Aug 2015 14:47:50 +0000 Subject: Multiple fixes git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@742 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 89e8ccf59283c5775db2f058bf5439bd487d79aa --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 479 ++++++++++++--------- .../gudhi/Simplex_tree/Simplex_tree_siblings.h | 23 +- 2 files changed, 287 insertions(+), 215 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 5eef283e..57e9b987 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -20,8 +20,8 @@ * along with this program. If not, see . */ -#ifndef SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ -#define SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ +#ifndef SIMPLEX_TREE_H_ +#define SIMPLEX_TREE_H_ #include #include @@ -37,9 +37,10 @@ #include #include #include +#include // for greater<> namespace Gudhi { - + /** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ @@ -74,6 +75,7 @@ namespace Gudhi { * \copyright GNU General Public License v3. * @{ */ + /** * \brief Simplex Tree data structure for representing simplicial complexes. * @@ -86,9 +88,8 @@ namespace Gudhi { * */ template class Simplex_tree { public: @@ -111,20 +112,13 @@ class Simplex_tree { /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */ typedef typename boost::container::flat_map Dictionary; - friend class Simplex_tree_node_explicit_storage< Simplex_tree >; - friend class Simplex_tree_siblings< Simplex_tree, Dictionary>; - friend class Simplex_tree_simplex_vertex_iterator< Simplex_tree >; - friend class Simplex_tree_boundary_simplex_iterator< Simplex_tree >; - friend class Simplex_tree_complex_simplex_iterator< Simplex_tree >; - friend class Simplex_tree_skeleton_simplex_iterator< Simplex_tree >; - /* \brief Set of nodes sharing a same parent in the simplex tree. */ /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings Siblings; public: /** \brief Handle type to a simplex contained in the simplicial complex represented - * byt he simplex tree. */ + * by the simplex tree. */ typedef typename Dictionary::iterator Simplex_handle; private: @@ -158,6 +152,8 @@ class Simplex_tree { typedef Simplex_tree_simplex_vertex_iterator Simplex_vertex_iterator; /** \brief Range over the vertices of a simplex. */ typedef boost::iterator_range Simplex_vertex_range; + /** \brief Range over the cofaces of a simplex. */ + typedef std::vector Cofaces_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -189,13 +185,12 @@ class Simplex_tree { /** \name Range and iterator methods * @{ */ - /** \brief Returns a range over the vertices of the simplicial complex. - * + /** \brief Returns a range over the vertices of the simplicial complex. * The order is increasing according to < on Vertex_handles.*/ Complex_vertex_range complex_vertex_range() { return Complex_vertex_range( - boost::make_transform_iterator(root_.members_.begin(), return_first()), - boost::make_transform_iterator(root_.members_.end(), return_first())); + boost::make_transform_iterator(root_.members_.begin(), return_first()), + boost::make_transform_iterator(root_.members_.end(), return_first())); } /** \brief Returns a range over the simplices of the simplicial complex. @@ -246,6 +241,7 @@ class Simplex_tree { Filtration_simplex_range filtration_simplex_range() { return filtration_simplex_range(Indexing_tag()); } + /** \brief Returns a range over the vertices of a simplex. * * The order in which the vertices are visited is the decreasing order for < on Vertex_handles, @@ -253,6 +249,7 @@ class Simplex_tree { * equal to \f$(-1)^{\text{dim} \sigma}\f$ the canonical orientation on the simplex. */ Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) { + assert(sh != null_simplex()); // Empty simplex return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -283,12 +280,11 @@ class Simplex_tree { /** \brief Constructs an empty simplex tree. */ Simplex_tree() : null_vertex_(-1), - threshold_(0), - num_simplices_(0), - root_(NULL, null_vertex_), - filtration_vect_(), - dimension_(-1) { - } + threshold_(0), + num_simplices_(0), + root_(NULL, null_vertex_), + filtration_vect_(), + dimension_(-1) { } /** \brief Copy; copy the whole tree structure. */ Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), num_simplices_(copy.num_simplices_), root_(NULL, -1, std::vector> (copy.root_.members().begin(), copy.root_.members().end())), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) { @@ -330,7 +326,7 @@ class Simplex_tree { } /** @} */ // end constructor/destructor private: - /** Recursive deletion. */ + // Recursive deletion void rec_delete(Siblings * sib) { for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) { if (has_children(sh)) { @@ -379,20 +375,11 @@ class Simplex_tree { /** \brief Checks whether or not two simplex trees are equal. */ bool operator ==(Simplex_tree st2) { - if (root_.members().size() != st2.root()->members().size() || this->null_vertex_ != st2.null_vertex_ || this->threshold_ != st2.threshold_ || this->num_simplices_ != st2.num_simplices_ || this->dimension_ != st2.dimension_) - return false; - for (auto sh1 = root_.members().begin(), sh2 = st2.root()->members().begin(); sh1 != root_.members().end(); ++sh1, ++sh2) - { - if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) - return false; - if (has_children(sh1)) - return rec_equal(sh1->second.children(), sh2->second.children()); - else if (has_children(sh2)) - return false; - else - return true; - } - return true; + return (this->null_vertex_ == st2.null_vertex_ + && this->threshold_ == st2.threshold_ + && this->num_simplices_ == st2.num_simplices_ + && this->dimension_ == st2.dimension_ + && rec_equal(&root_, &st2.root_)); } /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ @@ -419,100 +406,109 @@ class Simplex_tree { /** \brief Returns the key associated to a simplex. * * The filtration must be initialized. */ - Simplex_key key(Simplex_handle sh) { + static Simplex_key key(Simplex_handle sh) { return sh->second.key(); } + /** \brief Returns the simplex associated to a key. * * The filtration must be initialized. */ - Simplex_handle simplex(Simplex_key key) { + Simplex_handle simplex(Simplex_key key) const { return filtration_vect_[key]; } + /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ - Filtration_value filtration(Simplex_handle sh) { - if (sh != null_simplex()) { - return sh->second.filtration(); - } else { - return INFINITY; - } // filtration(); } -} -/** \brief Returns an upper bound of the filtration values of the simplices. */ -Filtration_value filtration() { - return threshold_; -} -/** \brief Returns a Simplex_handle different from all Simplex_handles - * associated to the simplices in the simplicial complex. - * - * One can call filtration(null_simplex()). */ -Simplex_handle null_simplex() { - return Dictionary_it(NULL); -} -/** \brief Returns a key different for all keys associated to the - * simplices of the simplicial complex. */ -Simplex_key null_key() { - return -1; -} -/** \brief Returns a Vertex_handle different from all Vertex_handles associated - * to the vertices of the simplicial complex. */ -Vertex_handle null_vertex() { - return null_vertex_; -} -/** \brief Returns the number of vertices in the complex. */ -size_t num_vertices() { - return root_.members_.size(); -} -/** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ -const unsigned int& num_simplices() const { - return num_simplices_; -} + static Filtration_value filtration(Simplex_handle sh) { + if (sh != null_simplex()) { + return sh->second.filtration(); + } else { + return INFINITY; + } + } -/** \brief Returns the dimension of a simplex. - * - * Must be different from null_simplex().*/ -int dimension(Simplex_handle sh) { - Siblings * curr_sib = self_siblings(sh); - int dim = 0; - while (curr_sib != NULL) { - ++dim; - curr_sib = curr_sib->oncles(); - } - return dim - 1; -} -/** \brief Returns an upper bound on the dimension of the simplicial complex. */ -int dimension() { - return dimension_; -} + /** \brief Returns an upper bound of the filtration values of the simplices. */ + Filtration_value filtration() const { + return threshold_; + } -/** \brief Returns true iff the node in the simplex tree pointed by - * sh has children.*/ -bool has_children(Simplex_handle sh) { - return (sh->second.children()->parent() == sh->first); -} + /** \brief Returns a Simplex_handle different from all Simplex_handles + * associated to the simplices in the simplicial complex. + * + * One can call filtration(null_simplex()). */ + static Simplex_handle null_simplex() { + return Dictionary_it(NULL); + } -/** \brief Given a range of Vertex_handles, returns the Simplex_handle - * of the simplex in the simplicial complex containing the corresponding - * vertices. Return null_simplex() if the simplex is not in the complex. - * - * The type InputVertexRange must be a range of Vertex_handle - * on which we can call std::begin() function - */ + /** \brief Returns a key different for all keys associated to the + * simplices of the simplicial complex. */ + static Simplex_key null_key() { + return -1; + } + + /** \brief Returns a Vertex_handle different from all Vertex_handles associated + * to the vertices of the simplicial complex. */ + Vertex_handle null_vertex() const { + return null_vertex_; + } + + /** \brief Returns the number of vertices in the complex. */ + size_t num_vertices() const { + return root_.members_.size(); + } + + /** \brief Returns the number of simplices in the complex. + * + * Does not count the empty simplex. */ + unsigned int num_simplices() const { + return num_simplices_; + } + + /** \brief Returns the dimension of a simplex. + * + * Must be different from null_simplex().*/ + int dimension(Simplex_handle sh) { + Siblings * curr_sib = self_siblings(sh); + int dim = 0; + while (curr_sib != NULL) { + ++dim; + curr_sib = curr_sib->oncles(); + } + return dim - 1; + } + + /** \brief Returns an upper bound on the dimension of the simplicial complex. */ + int dimension() const { + return dimension_; + } + + + /** \brief Returns true iff the node in the simplex tree pointed by + * sh has children.*/ + bool has_children(Simplex_handle sh) const { + return (sh->second.children()->parent() == sh->first); + } + + /** \brief Given a range of Vertex_handles, returns the Simplex_handle + * of the simplex in the simplicial complex containing the corresponding + * vertices. Return null_simplex() if the simplex is not in the complex. + * + * The type InputVertexRange must be a range of Vertex_handle + * on which we can call std::begin() function + */ template Simplex_handle find(const InputVertexRange & s) { std::vector copy(std::begin(s), std::end(s)); std::sort(std::begin(copy), std::end(copy)); - return find_rec(copy); + return find_simplex(copy); } private: - /** recursive function of find */ - Simplex_handle find_rec(std::vector & simplex) { + /** Find function, with a sorted range of vertices. */ + Simplex_handle find_simplex(std::vector & simplex) { if (simplex.begin() == simplex.end()) return null_simplex(); - Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; Vertex_handle last = simplex[simplex.size() - 1]; @@ -534,13 +530,13 @@ template Simplex_handle find_vertex(Vertex_handle v) { return root_.members_.begin() + v; } -//{ return root_.members_.find(v); } + //{ return root_.members_.find(v); } private: /** Recursively insert a simplex */ template std::pair insert_simplex_rec(RandomAccessVertexRange & simplex, - Filtration_value filtration) { + Filtration_value filtration) { if (simplex.empty()) { return std::pair(null_simplex(), true); } @@ -555,12 +551,15 @@ template curr_sib = res_insert.first->second.children(); } res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); - if (!res_insert.second) { // if already in the complex - if (res_insert.first->second.filtration() > filtration) { // if filtration value modified + if (!res_insert.second) { + // if already in the complex + if (res_insert.first->second.filtration() > filtration) { + // if filtration value modified res_insert.first->second.assign_filtration(filtration); return res_insert; } - return std::pair(null_simplex(), false); // if filtration value unchanged + // if filtration value unchanged + return std::pair(null_simplex(), false); } // otherwise the insertion has succeeded return res_insert; @@ -602,10 +601,10 @@ std::pair insert_simplex(const RandomAccessVertexRange & s * * @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. - */ + */ template void insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, - Filtration_value filtration = 0.0) { + Filtration_value filtration = 0.0) { std::vector copy(std::begin(Nsimplex), std::end(Nsimplex));; std::sort(std::begin(copy), std::end(copy)); insert_simplex_and_subfaces_rec(copy, filtration); @@ -624,7 +623,7 @@ std::pair insert_simplex(const RandomAccessVertexRange & s RandomAccessVertexRange NsimplexMinusOne; for (unsigned int NListIter = 0; NListIter < Nsimplex.size() - 1; NListIter++) { // (N-1)-Simplex creation - NsimplexMinusOne.push_back( Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); + NsimplexMinusOne.push_back(Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); } // (N-1)-Simplex recursive call insert_simplex_and_subfaces(NsimplexMinusOne, filtration); @@ -658,9 +657,8 @@ std::pair insert_simplex(const RandomAccessVertexRange & s * and edge. sh must point to a 1-dimensional simplex. This is an * optimized version of the boundary computation. */ std::pair endpoints(Simplex_handle sh) { - return std::pair( - root_.members_.find(sh->first), - root_.members_.find(self_siblings(sh)->parent())); + assert(dimension(sh) == 1); + return { find_vertex(sh->first), find_vertex(self_siblings(sh)->parent()) }; } /** Returns the Siblings containing a simplex.*/ @@ -671,12 +669,12 @@ std::pair insert_simplex(const RandomAccessVertexRange & s return sh->second.children(); } -// void display_simplex(Simplex_handle sh) -// { -// std::cout << " " << "[" << filtration(sh) << "] "; -// for( auto vertex : simplex_vertex_range(sh) ) -// { std::cout << vertex << " "; } -// } + // void display_simplex(Simplex_handle sh) + // { + // std::cout << " " << "[" << filtration(sh) << "] "; + // for( auto vertex : simplex_vertex_range(sh) ) + // { std::cout << vertex << " "; } + // } // void print(Simplex_handle sh, std::ostream& os = std::cout) // { for(auto v : simplex_vertex_range(sh)) {os << v << " ";} @@ -688,15 +686,16 @@ std::pair insert_simplex(const RandomAccessVertexRange & s return &root_; } - public: /** Set an upper bound for the filtration values. */ void set_filtration(Filtration_value fil) { threshold_ = fil; } + /** Set a number of simplices for the simplicial complex. */ - void set_num_simplices(const unsigned int& num_simplices) { + void set_num_simplices(unsigned int num_simplices) { num_simplices_ = num_simplices; } + /** Set a dimension for the simplicial complex. */ void set_dimension(int dimension) { dimension_ = dimension; @@ -721,17 +720,15 @@ std::pair insert_simplex(const RandomAccessVertexRange & s void initialize_filtration() { filtration_vect_.clear(); filtration_vect_.reserve(num_simplices()); - for (auto cpx_it = complex_simplex_range().begin(); - cpx_it != complex_simplex_range().end(); ++cpx_it) { - filtration_vect_.push_back(*cpx_it); - } + for (Simplex_handle sh : complex_simplex_range()) + filtration_vect_.push_back(sh); // the stable sort ensures the ordering heuristic std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); } -/** \brief Contracts two edges : the contracted edge is erased from the three, and the remaining edge receives all the links of the contracted one. +/** \brief Contracts two vertices : the contracted vertex is erased from the three, and the remaining vertex receives all the links of the contracted one. \param remaining The value of the vertex within the other is contracted \param deleted The value of the vertex to be contracted */ @@ -779,7 +776,6 @@ std::pair insert_simplex(const RandomAccessVertexRange & s std::pair member(sh->first, Node(sibTarget, sh->second.filtration())); if (has_children(sh)) { - std::cout << "children" << std::endl; std::vector> v(sh->second.children()->members().begin(), sh->second.children()->members().end()); Siblings * newsib = new Siblings (sibTarget, sh->first); for (auto it = v.begin(); it != v.end(); ++it) @@ -807,6 +803,92 @@ std::pair insert_simplex(const RandomAccessVertexRange & s } } + private: + /** Recursive search of cofaces + * This function uses DFS + *\param vertices contains a list of vertices, which represent the vertices of the simplex not found yet. + *\param curr_nbVertices represents the number of vertices of the simplex we reached by going through the tree. + *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. + *\param star true if we need the star of the simplex + *\param nbVertices number of vertices of the cofaces we search + * Prefix actions : When the bottom vertex matches with the current vertex in the tree, we remove the bottom vertex from vertices. + * Infix actions : Then we call or not the recursion. + * Postfix actions : Finally, we add back the removed vertex into vertices, and remove this vertex from curr_nbVertices so that we didn't change the parameters. + * If the vertices list is empty, we need to check if curr_nbVertices matches with the dimension of the cofaces asked. + */ + void rec_coface(std::vector &vertices, Siblings *curr_sib, int curr_nbVertices, + std::vector& cofaces, bool star, int nbVertices) { + if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices + return; + for (Simplex_handle simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) { + if (vertices.empty()) { + // If we reached the end of the vertices, and the simplex has more vertices than the given simplex + // => we found a coface + + // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices + bool addCoface = (star || curr_nbVertices == nbVertices); + if (addCoface) + cofaces.push_back(simplex); + if ((!addCoface || star) && has_children(simplex)) // Rec call + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + } else { + if (simplex->first == vertices.back()) { + // If curr_sib matches with the top vertex + bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = vertices.size() == 1 && equalDim; + if (addCoface) + cofaces.push_back(simplex); + if ((!addCoface || star) && has_children(simplex)) { + // Rec call + Vertex_handle tmp = vertices.back(); + vertices.pop_back(); + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + vertices.push_back(tmp); + } + } else if (simplex->first > vertices.back()) { + return; + } else { + // (simplex->first < vertices.back() + if (has_children(simplex)) + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + } + } + } + } + + public: + /** \brief Compute the star of a n simplex + * \param simplex represent the simplex of which we search the star + * \return Vector of Simplex_handle, empty vector if no cofaces found. + */ + + Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) { + return cofaces_simplex_range(simplex, 0); + } + + /** \brief Compute the cofaces of a n simplex + * \param simplex represent the n-simplex of which we search the n+codimension cofaces + * \param codimension The function returns the n+codimension-cofaces of the n-simplex. If codimension = 0, + * return all cofaces (equivalent of star function) + * \return Vector of Simplex_handle, empty vector if no cofaces found. + */ + + Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) { + Cofaces_simplex_range cofaces; + // codimension must be positive or null integer + assert(codimension >= 0); + Simplex_vertex_range rg = simplex_vertex_range(simplex); + std::vector copy(rg.begin(), rg.end()); + if (codimension + static_cast(copy.size()) > dimension_ + 1 || + (codimension == 0 && static_cast(copy.size()) > dimension_)) // n+codimension greater than dimension_ + return cofaces; + // must be sorted in decreasing order + assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); + bool star = codimension == 0; + rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast(copy.size())); + return cofaces; + } + private: /** \brief Returns true iff the list of vertices of sh1 * is smaller than the list of vertices of sh2 w.r.t. @@ -830,6 +912,7 @@ std::pair insert_simplex(const RandomAccessVertexRange & s } return ((it1 == rg1.end()) && (it2 != rg2.end())); } + /** \brief StrictWeakOrdering, for the simplices, defined by the filtration. * * It corresponds to the partial order @@ -838,15 +921,14 @@ std::pair insert_simplex(const RandomAccessVertexRange & s * to be smaller. The filtration function must be monotonic. */ struct is_before_in_filtration { explicit is_before_in_filtration(Simplex_tree * st) - : st_(st) { - } + : st_(st) { } bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const { if (st_->filtration(sh1) != st_->filtration(sh2)) { return st_->filtration(sh1) < st_->filtration(sh2); } - - return st_->reverse_lexicographic_order(sh1, sh2); // is sh1 a proper subface of sh2 + // is sh1 a proper subface of sh2 + return st_->reverse_lexicographic_order(sh1, sh2); } Simplex_tree * st_; @@ -873,7 +955,8 @@ std::pair insert_simplex(const RandomAccessVertexRange & s * must be undirected_tag. */ template void insert_graph(const OneSkeletonGraph& skel_graph) { - assert(num_simplices() == 0); // the simplex tree must be empty + // the simplex tree must be empty + assert(num_simplices() == 0); if (boost::num_vertices(skel_graph) == 0) { return; @@ -891,30 +974,32 @@ std::pair insert_simplex(const RandomAccessVertexRange & s typename boost::graph_traits::vertex_iterator v_it, v_it_end; for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end; - ++v_it) { + ++v_it) { root_.members_.emplace_hint( - root_.members_.end(), *v_it, - Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); + root_.members_.end(), *v_it, + Node(&root_, boost::get(vertex_filtration_t(), skel_graph, *v_it))); } typename boost::graph_traits::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) { + ++e_it) { auto u = source(*e_it, skel_graph); auto v = target(*e_it, skel_graph); - if (u < v) { // count edges only once { std::swap(u,v); } // u < v + if (u < v) { + // count edges only once { std::swap(u,v); } // u < v auto sh = find_vertex(u); if (!has_children(sh)) { sh->second.assign_children(new Siblings(&root_, sh->first)); } sh->second.children()->members().emplace( - v, - Node(sh->second.children(), - boost::get(edge_filtration_t(), skel_graph, *e_it))); + v, + Node(sh->second.children(), + boost::get(edge_filtration_t(), skel_graph, *e_it))); } } } + /** \brief Expands the Simplex_tree containing only its one skeleton * until dimension max_dim. * @@ -929,7 +1014,7 @@ std::pair insert_simplex(const RandomAccessVertexRange & s void expansion(int max_dim) { dimension_ = max_dim; for (Dictionary_it root_it = root_.members_.begin(); - root_it != root_.members_.end(); ++root_it) { + root_it != root_.members_.end(); ++root_it) { if (has_children(root_it)) { siblings_expansion(root_it->second.children(), max_dim - 1); } @@ -940,7 +1025,7 @@ std::pair insert_simplex(const RandomAccessVertexRange & s private: /** \brief Recursive expansion of the simplex tree.*/ void siblings_expansion(Siblings * siblings, // must contain elements - int k) { + int k) { if (dimension_ > k) { dimension_ = k; } @@ -951,68 +1036,56 @@ std::pair insert_simplex(const RandomAccessVertexRange & s static std::vector > inter; // static, not thread-safe. for (Dictionary_it s_h = siblings->members().begin(); - s_h != siblings->members().end(); ++s_h, ++next) { + s_h != siblings->members().end(); ++s_h, ++next) { Simplex_handle root_sh = find_vertex(s_h->first); if (has_children(root_sh)) { intersection( - inter, // output intersection - next, // begin - siblings->members().end(), // end - root_sh->second.children()->members().begin(), - root_sh->second.children()->members().end(), - s_h->second.filtration()); + inter, // output intersection + next, // begin + siblings->members().end(), // end + root_sh->second.children()->members().begin(), + root_sh->second.children()->members().end(), + s_h->second.filtration()); if (inter.size() != 0) { this->num_simplices_ += inter.size(); Siblings * new_sib = new Siblings(siblings, // oncles - s_h->first, // parent - inter); // boost::container::ordered_unique_range_t + s_h->first, // parent + inter); // boost::container::ordered_unique_range_t inter.clear(); s_h->second.assign_children(new_sib); siblings_expansion(new_sib, k - 1); } else { - s_h->second.assign_children(siblings); // ensure the children property + // ensure the children property + s_h->second.assign_children(siblings); inter.clear(); } } } } + /** \brief Intersects Dictionary 1 [begin1;end1) with Dictionary 2 [begin2,end2) * and assigns the maximal possible Filtration_value to the Nodes. */ - void intersection(std::vector >& intersection, - Dictionary_it begin1, Dictionary_it end1, - Dictionary_it begin2, Dictionary_it end2, - Filtration_value filtration) { + static void intersection(std::vector >& intersection, + Dictionary_it begin1, Dictionary_it end1, + Dictionary_it begin2, Dictionary_it end2, + Filtration_value filtration_) { if (begin1 == end1 || begin2 == end2) return; // ----->> while (true) { if (begin1->first == begin2->first) { - intersection.push_back( - std::pair( - begin1->first, - Node(NULL, maximum(begin1->second.filtration(), begin2->second.filtration(), filtration)))); - ++begin1; - ++begin2; - if (begin1 == end1 || begin2 == end2) + Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_}); + intersection.emplace_back(begin1->first, Node(NULL, filt)); + if (++begin1 == end1 || ++begin2 == end2) + return; // ----->> + } else if (begin1->first < begin2->first) { + if (++begin1 == end1) + return; + } else /* begin1->first > begin2->first */ { + if (++begin2 == end2) return; // ----->> - } else { - if (begin1->first < begin2->first) { - ++begin1; - if (begin1 == end1) - return; - } else { - ++begin2; - if (begin2 == end2) - return; // ----->> - } } } } - /** Maximum over 3 values.*/ - Filtration_value maximum(Filtration_value a, Filtration_value b, - Filtration_value c) { - Filtration_value max = (a < b) ? b : a; - return ((max < c) ? c : max); - } public: /** \brief Write the hasse diagram of the simplicial complex in os. @@ -1047,8 +1120,9 @@ std::pair insert_simplex(const RandomAccessVertexRange & s }; // Print a Simplex_tree in os. -template -std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { + +template +std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { for (auto sh : st.filtration_simplex_range()) { os << st.dimension(sh) << " "; for (auto v : st.simplex_vertex_range(sh)) { @@ -1058,25 +1132,30 @@ std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { } return os; } -template -std::istream& operator>>(std::istream & is, Simplex_tree & st) { + +template +std::istream& operator>>(std::istream & is, Simplex_tree & st) { // assert(st.num_simplices() == 0); - std::vector::Vertex_handle> simplex; - typename Simplex_tree::Filtration_value fil; - typename Simplex_tree::Filtration_value max_fil = 0; + typedef Simplex_tree ST; + std::vector simplex; + typename ST::Filtration_value fil; + typename ST::Filtration_value max_fil = 0; int max_dim = -1; size_t num_simplices = 0; - while (read_simplex(is, simplex, fil)) { // read all simplices in the file as a list of vertices + while (read_simplex(is, simplex, fil)) { + // read all simplices in the file as a list of vertices ++num_simplices; - int dim = static_cast(simplex.size() - 1); // Warning : simplex_size needs to be casted in int - Can be 0 + // Warning : simplex_size needs to be casted in int - Can be 0 + int dim = static_cast (simplex.size() - 1); if (max_dim < dim) { max_dim = dim; } if (max_fil < fil) { max_fil = fil; } - st.insert_simplex(simplex, fil); // insert every simplex in the simplex tree + // insert every simplex in the simplex tree + st.insert_simplex(simplex, fil); simplex.clear(); } st.set_num_simplices(num_simplices); @@ -1085,8 +1164,8 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { return is; } - /** @} */ // end defgroup simplex_tree + } // namespace Gudhi -#endif // SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ +#endif // SIMPLEX_TREE_H_ 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 977fafa1..de350f2d 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 @@ -77,8 +77,8 @@ class Simplex_tree_siblings { parent_(parent), members_(boost::container::ordered_unique_range, members.begin(), members.end()) { - for (auto map_it = members_.begin(); map_it != members_.end(); map_it++) { - map_it->second.assign_children(this); + for (auto& map_el : members_) { + map_el.second.assign_children(this); } } @@ -90,19 +90,12 @@ class Simplex_tree_siblings { * present in the node. */ void insert(Vertex_handle v, Filtration_value filtration_value) { - typename Dictionary::iterator sh = members_.find(v); - if (sh != members_.end() && sh->second.filtration() > filtration_value) { - sh->second.assign_filtration(filtration_value); - return; - } - if (sh == members_.end()) { - members_.insert( - std::pair(v, Node(this, filtration_value))); - return; - } + auto ins = members_.emplace(v, Node(this, filtration_value)); + if (!ins.second && filtration(ins.first) > filtration_value) + ins.first->second.assign_filtration(filtration_value); } - typename Dictionary::iterator find(Vertex_handle v) { + Dictionary_it find(Vertex_handle v) { return members_.find(v); } @@ -110,7 +103,7 @@ class Simplex_tree_siblings { return oncles_; } - Vertex_handle parent() { + Vertex_handle parent() const { return parent_; } @@ -118,7 +111,7 @@ class Simplex_tree_siblings { return members_; } - size_t size() { + size_t size() const { return members_.size(); } -- cgit v1.2.3 From 683fbc62a3640361b1e204ac52ed61059df1d52f Mon Sep 17 00:00:00 2001 From: glisse Date: Thu, 20 Aug 2015 12:10:59 +0000 Subject: Some doc for SimplexTreeOptions. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-options@745 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 2560e01a832071e13486bfaabfdf166b705d5a70 --- src/Simplex_tree/concept/IndexingTag.h | 2 +- src/Simplex_tree/concept/SimplexKey.h | 4 +-- src/Simplex_tree/concept/SimplexTreeOptions.h | 41 +++++++++++++++++++++++++++ src/Simplex_tree/concept/VertexHandle.h | 3 +- src/Simplex_tree/include/gudhi/Simplex_tree.h | 22 +++++++------- 5 files changed, 58 insertions(+), 14 deletions(-) create mode 100644 src/Simplex_tree/concept/SimplexTreeOptions.h (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/concept/IndexingTag.h b/src/Simplex_tree/concept/IndexingTag.h index d690da11..1dcdd756 100644 --- a/src/Simplex_tree/concept/IndexingTag.h +++ b/src/Simplex_tree/concept/IndexingTag.h @@ -25,6 +25,6 @@ * continuous maps to a cell complex, and compute its persistent * homology. * - * Must be linear_indexing_tag. + * Must be `Gudhi::linear_indexing_tag`. */ struct IndexingTag {}; diff --git a/src/Simplex_tree/concept/SimplexKey.h b/src/Simplex_tree/concept/SimplexKey.h index ce5b2382..7fdbdd84 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 int + * Must be a signed integer type. */ struct SimplexKey {}; - \ No newline at end of file + diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h new file mode 100644 index 00000000..9415a471 --- /dev/null +++ b/src/Simplex_tree/concept/SimplexTreeOptions.h @@ -0,0 +1,41 @@ + /* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (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 . + */ + +/** \brief Concept of the template parameter for the class `Gudhi::Simplex_tree`. + * + * One model for this is `Gudhi::Simplex_tree_options_full_featured`. If you want to provide your own, it is recommended that you derive from it and override some parts instead of writing a class from scratch. + */ +struct SimplexTreeOptions { + /// Forced for now. + typedef IndexingTag Indexing_tag; + /// Must be a signed integer type. It admits a total order <. + typedef VertexHandle Vertex_handle; + /// Must be comparable with operator<. + typedef FiltrationValue Filtration_value; + /// Must be a signed 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::expansion`. Necessary for `Persistent_cohomology`. + static constexpr bool store_filtration; +}; + diff --git a/src/Simplex_tree/concept/VertexHandle.h b/src/Simplex_tree/concept/VertexHandle.h index 491f0f56..3efbba61 100644 --- a/src/Simplex_tree/concept/VertexHandle.h +++ b/src/Simplex_tree/concept/VertexHandle.h @@ -22,5 +22,6 @@ /** \brief Handle type for the vertices of a cell complex. * - * Must be int.*/ + * Must be a signed integer type. operator< defines a total order on it. + */ struct VertexHandle {}; diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 11c41d1b..44ee7693 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -74,6 +74,16 @@ namespace Gudhi { * @{ */ +/// 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 constexpr bool store_key = true; + static constexpr bool store_filtration = true; +}; + /** * \brief Simplex Tree data structure for representing simplicial complexes. * @@ -86,18 +96,10 @@ namespace Gudhi { * */ -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 constexpr bool store_key = true; - static constexpr bool store_filtration = true; -}; - -template +template class Simplex_tree { public: + typedef SimplexTreeOptions Options; typedef typename Options::Indexing_tag Indexing_tag; /** \brief Type for the value of the filtration function. * -- cgit v1.2.3 From 05a215d2d8fed0961daf0b48e9e63973a12b9315 Mon Sep 17 00:00:00 2001 From: glisse Date: Thu, 20 Aug 2015 14:07:31 +0000 Subject: A bit more doc for SimplexTreeOptions. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-options@747 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 1631ac5e9c4eb9f074fe7468f14cda1f122b63ad --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 44ee7693..c3f913fa 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -266,7 +266,7 @@ class Simplex_tree { * order is used. * * The filtration must be valid. If the filtration has not been initialized yet, the - * method initializes it (i.e. order the simplices). */ + * method initializes it (i.e. order the simplices). If the complex has changed since the last time the filtration was initialized, please call `initialize_filtration()` to recompute it. */ Filtration_simplex_range filtration_simplex_range(Indexing_tag) { if (filtration_vect_.empty()) { initialize_filtration(); @@ -346,21 +346,27 @@ class Simplex_tree { public: /** \brief Returns the key associated to a simplex. * - * The filtration must be initialized. */ + * The filtration must be initialized. + * \pre SimplexTreeOptions::store_key + */ static Simplex_key key(Simplex_handle sh) { return sh->second.key(); } /** \brief Returns the simplex associated to a key. * - * The filtration must be initialized. */ + * The filtration must be initialized. + * \pre SimplexTreeOptions::store_key + */ Simplex_handle simplex(Simplex_key key) const { return filtration_vect_[key]; } /** \brief Returns the filtration value of a simplex. * - * Called on the null_simplex, returns INFINITY. */ + * Called on the null_simplex, 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(); -- cgit v1.2.3 From 84ab537dccbec5eefa28f47f9a40f1ec1a83bf25 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 24 Aug 2015 12:59:52 +0000 Subject: Fixes git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@756 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 9d9cfa9fdcf90b1a02f42e8f3a5ab6812629b4a1 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 6b016fc3..b32b525b 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -288,7 +288,6 @@ class Simplex_tree { /** \brief Copy; copy the whole tree structure. */ Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), - num_simplices_(copy.num_simplices_), root_(NULL, -1, std::vector> (copy.root_.members().begin(), copy.root_.members().end())), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) { @@ -300,9 +299,8 @@ class Simplex_tree { { for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); sh != sib->members().end(); ++sh, ++sh_copy) { if (has_children(sh_copy)) { - std::vector> v(sh_copy->second.children()->members().begin(), sh_copy->second.children()->members().end()); Siblings * newsib = new Siblings (sib, sh_copy->first); - for (auto it = v.begin(); it != v.end(); ++it) + for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); rec_copy(newsib, sh_copy->second.children()); sh->second.assign_children(newsib); @@ -314,9 +312,11 @@ class Simplex_tree { /** \brief Move; moves the whole tree structure. */ - Simplex_tree(Simplex_tree&& old) : null_vertex_(std::move(old.null_vertex_)), threshold_(std::move(old.threshold_)), num_simplices_(std::move(old.num_simplices_)), root_(std::move(old.root_)), filtration_vect_(std::move(old.filtration_vect_)), dimension_(std::move(old.dimension_)) { + 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.num_simplices_ = 0; old.threshold_ = 0; } @@ -341,7 +341,9 @@ class Simplex_tree { } public: - /** \brief Prints the simplex_tree hierarchically. */ + /** \brief Prints the simplex_tree hierarchically. + * Since it prints the vertices recursively, one can watch its tree shape. + */ void print_tree() { for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) @@ -381,7 +383,6 @@ class Simplex_tree { { return (this->null_vertex_ == st2.null_vertex_ && this->threshold_ == st2.threshold_ - && this->num_simplices_ == st2.num_simplices_ && this->dimension_ == st2.dimension_ && rec_equal(&root_, &st2.root_)); } -- cgit v1.2.3 From fa7f116a662bf8cff80402ad0011bcb83296c182 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 24 Aug 2015 14:56:23 +0000 Subject: Fixes git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@757 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 88bfc9b672be26ed97bea4aecdcfbafb24259553 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h | 5 +++-- 2 files changed, 4 insertions(+), 3 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b32b525b..51c39801 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -288,7 +288,7 @@ class Simplex_tree { /** \brief Copy; copy the whole tree structure. */ Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), threshold_(copy.threshold_), - root_(NULL, -1, std::vector> (copy.root_.members().begin(), copy.root_.members().end())), + root_(NULL, -1, copy.root_.members()), filtration_vect_(copy.filtration_vect_), dimension_(copy.dimension_) { rec_copy(&root_, ©.root_); 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 de350f2d..b9f8dcc1 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 @@ -71,15 +71,16 @@ class Simplex_tree_siblings { /* \brief Constructor with initialized set of members. * * 'members' must be sorted and unique.*/ + template Simplex_tree_siblings(Simplex_tree_siblings * oncles, Vertex_handle parent, - const std::vector > & members) + RandomAccessVertexRange members) : oncles_(oncles), parent_(parent), members_(boost::container::ordered_unique_range, members.begin(), members.end()) { for (auto& map_el : members_) { map_el.second.assign_children(this); - } + } } /* -- cgit v1.2.3 From 5cee68f83f5eb9b78bc699bf6ef9c8911e4ab2d0 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 24 Aug 2015 15:45:54 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@761 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 616315097f92608d92c264a3015fd5b8d634e37b --- src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/Simplex_tree/include') 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 b9f8dcc1..adb3f49b 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 @@ -72,8 +72,7 @@ class Simplex_tree_siblings { * * 'members' must be sorted and unique.*/ template - Simplex_tree_siblings(Simplex_tree_siblings * oncles, Vertex_handle parent, - RandomAccessVertexRange members) + Simplex_tree_siblings(Simplex_tree_siblings * oncles, Vertex_handle parent, const& RandomAccessVertexRange members) : oncles_(oncles), parent_(parent), members_(boost::container::ordered_unique_range, members.begin(), -- cgit v1.2.3 From 67e3921f57dde28a557dc132da3ac96b9c5284f0 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 26 Aug 2015 14:51:34 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@762 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: a64cb1cb3661a065035c5facd23c9f9855a927c6 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 7 ++++--- .../include/gudhi/Simplex_tree/Simplex_tree_siblings.h | 2 +- 2 files changed, 5 insertions(+), 4 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 51c39801..62d6f8fb 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -299,9 +299,10 @@ class Simplex_tree { { for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); sh != sib->members().end(); ++sh, ++sh_copy) { if (has_children(sh_copy)) { - Siblings * newsib = new Siblings (sib, sh_copy->first); - for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) - newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); + boost::container::flat_map copy(sh_copy->second.children()->members()); + Siblings * newsib = new Siblings (sib, sh_copy->first, copy); +// for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) +// newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); rec_copy(newsib, sh_copy->second.children()); sh->second.assign_children(newsib); } 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 adb3f49b..d20a91d7 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 @@ -72,7 +72,7 @@ class Simplex_tree_siblings { * * 'members' must be sorted and unique.*/ template - Simplex_tree_siblings(Simplex_tree_siblings * oncles, Vertex_handle parent, const& RandomAccessVertexRange members) + Simplex_tree_siblings(Simplex_tree_siblings * oncles, Vertex_handle parent, const RandomAccessVertexRange & members) : oncles_(oncles), parent_(parent), members_(boost::container::ordered_unique_range, members.begin(), -- cgit v1.2.3 From cd78252ec7e022dfebfa563531890971c978339a Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 26 Aug 2015 14:52:18 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@763 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5cbe199ded1ba7da400cfa5a96f53c71f19ca2a8 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 62d6f8fb..b9b8f0ea 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -299,10 +299,10 @@ class Simplex_tree { { for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); sh != sib->members().end(); ++sh, ++sh_copy) { if (has_children(sh_copy)) { - boost::container::flat_map copy(sh_copy->second.children()->members()); - Siblings * newsib = new Siblings (sib, sh_copy->first, copy); -// for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) -// newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); +// boost::container::flat_map copy(sh_copy->second.children()->members()); + Siblings * newsib = new Siblings (sib, sh_copy->first); + for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) + newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); rec_copy(newsib, sh_copy->second.children()); sh->second.assign_children(newsib); } -- cgit v1.2.3 From 79425a986879662b217672cf693e3ca570e501ee Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 2 Sep 2015 09:07:41 +0000 Subject: constexpr is only supported in extremely recent VS. Unnecessary "public:". git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-options@769 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 62c7733f0d3236a0d919be049dc09b824435a198 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 4 ++-- .../include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h | 1 - 2 files changed, 2 insertions(+), 3 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index bf9b3e13..aeb0364f 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -80,8 +80,8 @@ struct Simplex_tree_options_full_featured { typedef int Vertex_handle; typedef double Filtration_value; typedef int Simplex_key; - static constexpr bool store_key = true; - static constexpr bool store_filtration = true; + static const bool store_key = true; + static const bool store_filtration = true; }; /** diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index 26d18098..c49e30b9 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -40,7 +40,6 @@ namespace Gudhi { */ template struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base { - public: typedef typename SimplexTree::Siblings Siblings; typedef typename SimplexTree::Filtration_value Filtration_value; typedef typename SimplexTree::Simplex_key Simplex_key; -- cgit v1.2.3 From 0af6f948dc2efcf046176e8fcb407e36ac91e7a7 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 4 Sep 2015 11:41:22 +0000 Subject: Peer review fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@772 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e2896c0a1dc03cb8f87771910b6c756a755f258c --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 420 ++++++++++------------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 361 ++++++++++--------- 2 files changed, 367 insertions(+), 414 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b9b8f0ea..b38e5813 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -26,13 +26,14 @@ #include #include #include -#include #include +#include +#include + #include #include #include -#include #include #include @@ -234,8 +235,8 @@ class Simplex_tree { Filtration_simplex_range filtration_simplex_range(Indexing_tag) { if (filtration_vect_.empty()) { initialize_filtration(); - } return Filtration_simplex_range(filtration_vect_.begin(), - filtration_vect_.end()); + } + return Filtration_simplex_range(filtration_vect_.begin(), filtration_vect_.end()); } Filtration_simplex_range filtration_simplex_range() { @@ -281,45 +282,48 @@ class Simplex_tree { Simplex_tree() : null_vertex_(-1), threshold_(0), - root_(NULL, null_vertex_), + root_(nullptr, null_vertex_), filtration_vect_(), dimension_(-1) { } - /** \brief Copy; copy the whole tree structure. */ - Simplex_tree(Simplex_tree& copy) : null_vertex_(copy.null_vertex_), - threshold_(copy.threshold_), - root_(NULL, -1, copy.root_.members()), - filtration_vect_(copy.filtration_vect_), - dimension_(copy.dimension_) { - rec_copy(&root_, ©.root_); - } - - /** rec_copy: depth first search, inserts simplices when reaching a leaf.*/ - void rec_copy(Siblings *sib, Siblings *sib_copy) - { - for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); sh != sib->members().end(); ++sh, ++sh_copy) { - if (has_children(sh_copy)) { -// boost::container::flat_map copy(sh_copy->second.children()->members()); - Siblings * newsib = new Siblings (sib, sh_copy->first); - for (auto it = sh_copy->second.children()->members().begin(); it != sh_copy->second.children()->members().end(); ++it) - newsib->members_.emplace(it->first, Node(sib, it->second.filtration())); - rec_copy(newsib, sh_copy->second.children()); - sh->second.assign_children(newsib); - } - } + /** \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_), + filtration_vect_(simplex_source.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); } + /** \brief depth first search, inserts simplices when reaching a leaf. */ + void rec_copy(Siblings *sib, Siblings *sib_copy) { + for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); + sh != sib->members().end(); ++sh, ++sh_copy) { + if (has_children(sh_copy)) { + Siblings * newsib = new Siblings(sib, sh_copy->first); + newsib->members_.reserve(sh_copy->second.children()->members().size()); + for (auto it = sh_copy->second.children()->members().begin(); + it != sh_copy->second.children()->members().end(); ++it) + newsib->members_.emplace_hint(newsib->members_.end(), it->first, Node(sib, it->second.filtration())); + rec_copy(newsib, sh_copy->second.children()); + sh->second.assign_children(newsib); + } + } + } - - - /** \brief Move; 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; - } + /** \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_); + } /** \brief Destructor; deallocates the whole tree structure. */ ~Simplex_tree() { @@ -341,71 +345,36 @@ class Simplex_tree { delete sib; } - public: - /** \brief Prints the simplex_tree hierarchically. - * Since it prints the vertices recursively, one can watch its tree shape. - */ - void print_tree() - { - for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh) - { - std::cout << sh->first << " "; - if (has_children(sh)) - { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } - std::cout << std::endl; - } - } - - - /** \brief Recursively prints the simplex_tree, using depth first search. */ - private: - void rec_print(Siblings * sib) - { - for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) - { - std::cout << " " << sh->first << " "; - if (has_children(sh)) - { - std::cout << "("; - rec_print(sh->second.children()); - std::cout << ")"; - } - } - } - public: + /** \brief Checks if two simplex trees are equal. */ + bool operator==(Simplex_tree st2) { + return (this->null_vertex_ == st2.null_vertex_ + && this->threshold_ == st2.threshold_ + && this->dimension_ == st2.dimension_ + && rec_equal(&root_, &st2.root_)); + } - /** \brief Checks whether or not two simplex trees are equal. */ - bool operator ==(Simplex_tree st2) - { - return (this->null_vertex_ == st2.null_vertex_ - && this->threshold_ == st2.threshold_ - && this->dimension_ == st2.dimension_ - && rec_equal(&root_, &st2.root_)); + /** \brief Checks if two simplex trees are different. */ + bool operator!=(Simplex_tree st2) { + return (!(*this == st2)); } /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ private: - bool rec_equal(Siblings * s1, Siblings * s2) - { - if (s1->members().size() != s2->members().size()) - return false; - for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); sh1 != s1->members().end(); ++sh1, ++sh2) - { - if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) - return false; - if (has_children(sh1)) - return rec_equal(sh1->second.children(), sh2->second.children()); - else if (has_children(sh2)) - return false; - else - return true; - } - return true; + bool rec_equal(Siblings * s1, Siblings * s2) { + if (s1->members().size() != s2->members().size()) + return false; + for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); sh1 != s1->members().end(); ++sh1, ++sh2) { + if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) + return false; + if (has_children(sh1)) + return rec_equal(sh1->second.children(), sh2->second.children()); + else if (has_children(sh2)) + return false; + else + return true; + } + return true; } public: @@ -444,7 +413,7 @@ class Simplex_tree { * * One can call filtration(null_simplex()). */ static Simplex_handle null_simplex() { - return Dictionary_it(NULL); + return Dictionary_it(nullptr); } /** \brief Returns a key different for all keys associated to the @@ -491,7 +460,7 @@ class Simplex_tree { int dimension(Simplex_handle sh) { Siblings * curr_sib = self_siblings(sh); int dim = 0; - while (curr_sib != NULL) { + while (curr_sib != nullptr) { ++dim; curr_sib = curr_sib->oncles(); } @@ -503,32 +472,36 @@ class Simplex_tree { return dimension_; } - /** \brief Returns true iff the node in the simplex tree pointed by * sh has children.*/ bool has_children(Simplex_handle sh) const { return (sh->second.children()->parent() == sh->first); } - /** \brief Given a range of Vertex_handles, returns the Simplex_handle + /** \brief Given a range of Vertex_handles, returns the Simplex_handle * of the simplex in the simplicial complex containing the corresponding * vertices. Return null_simplex() if the simplex is not in the complex. * * The type InputVertexRange must be a range of Vertex_handle * on which we can call std::begin() function */ -template + template Simplex_handle find(const InputVertexRange & s) { - std::vector copy(std::begin(s), std::end(s)); - std::sort(std::begin(copy), std::end(copy)); - return find_simplex(copy); + auto first = std::begin(s); + auto last = std::end(s); + + if (first == last) + return null_simplex(); // ----->> + + // Copy before sorting + std::vector copy(first, last); + std::sort(std::begin(copy), std::end(copy)); + return find_simplex(copy); } private: /** Find function, with a sorted range of vertices. */ Simplex_handle find_simplex(std::vector & simplex) { - if (simplex.begin() == simplex.end()) - return null_simplex(); Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; Vertex_handle last = simplex[simplex.size() - 1]; @@ -553,22 +526,19 @@ template //{ return root_.members_.find(v); } private: - /** Recursively insert a simplex */ - template - std::pair insert_simplex_rec(RandomAccessVertexRange & simplex, - Filtration_value filtration) { - if (simplex.empty()) { - return std::pair(null_simplex(), true); - } + /** \brief Recursively insert a simplex represented by a vector of vertex. + \warning the vector must be sorted by increasing vertex handle order */ + std::pair insert_vertex_vector(const std::vector& simplex, + Filtration_value filtration) { Siblings * curr_sib = &root_; std::pair res_insert; - typename RandomAccessVertexRange::iterator vi; - for (vi = simplex.begin(); vi != simplex.end() - 1; ++vi) { + auto vi = simplex.begin(); + for (; vi != simplex.end() - 1; ++vi) { res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!(has_children(res_insert.first))) { res_insert.first->second.assign_children(new Siblings(curr_sib, *vi)); } - curr_sib = res_insert.first->second.children(); + curr_sib = res_insert.first->second.children(); } res_insert = curr_sib->members_.emplace(*vi, Node(curr_sib, filtration)); if (!res_insert.second) { @@ -584,7 +554,8 @@ template // otherwise the insertion has succeeded return res_insert; } -public: + + public: /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. * * @param[in] simplex range of Vertex_handles, representing the vertices of the new simplex @@ -594,7 +565,7 @@ public: * 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 filed of the + * 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. * @@ -608,58 +579,105 @@ public: * * The type RandomAccessVertexRange must be a range for which .begin() and * .end() return random access iterators, with 'value_type' Vertex_handle. */ -template -std::pair insert_simplex(const RandomAccessVertexRange & simplex, - Filtration_value filtration) { - std::vector copy(std::begin(simplex), std::end(simplex));; - std::sort(std::begin(copy), std::end(copy)); - return insert_simplex_rec(copy, filtration); -} + template + std::pair insert_simplex(const RandomAccessVertexRange & simplex, + Filtration_value filtration) { + auto first = std::begin(simplex); + auto last = std::end(simplex); + + if (first == last) + return std::pair(null_simplex(), true); // ----->> + + // Copy before sorting + std::vector copy(first, last); + std::sort(std::begin(copy), std::end(copy)); + return insert_vertex_vector(copy, filtration); + } - /** \brief Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of + /** \brief Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of * Vertex_handles, in the simplicial complex. * * @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 + * 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. */ template - void insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, + std::pair insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, Filtration_value filtration = 0.0) { - std::vector copy(std::begin(Nsimplex), std::end(Nsimplex));; - std::sort(std::begin(copy), std::end(copy)); - insert_simplex_and_subfaces_rec(copy, filtration); - } + auto first = std::begin(Nsimplex); + auto last = std::end(Nsimplex); - private: + if (first == last) + return std::pair(null_simplex(), true); // ----->> - /** Recursively insert simplex and all of its subfaces */ - template - void insert_simplex_and_subfaces_rec(RandomAccessVertexRange & Nsimplex, - Filtration_value filtration = 0.0) { - - if (Nsimplex.size() > 1) { - for (unsigned int NIndex = 0; NIndex < Nsimplex.size(); NIndex++) { - // insert N (N-1)-Simplex - RandomAccessVertexRange NsimplexMinusOne; - for (unsigned int NListIter = 0; NListIter < Nsimplex.size() - 1; NListIter++) { - // (N-1)-Simplex creation - NsimplexMinusOne.push_back(Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); - } - // (N-1)-Simplex recursive call - insert_simplex_and_subfaces(NsimplexMinusOne, filtration); + // Copy before sorting + std::vector copy(first, last); + std::sort(std::begin(copy), std::end(copy)); + + std::vector> to_be_inserted; + std::vector> to_be_propagated; + return rec_insert_simplex_and_subfaces(copy, to_be_inserted, to_be_propagated, filtration); + } + + private: + std::pair rec_insert_simplex_and_subfaces(std::vector& the_simplex, + std::vector>& to_be_inserted, + std::vector>& to_be_propagated, + Filtration_value filtration = 0.0) { + std::pair insert_result; + if (the_simplex.size() > 1) { + // Get and remove last vertex + Vertex_handle last_vertex = the_simplex.back(); + the_simplex.pop_back(); + // Recursive call after last vertex removal + insert_result = rec_insert_simplex_and_subfaces(the_simplex, to_be_inserted, to_be_propagated, filtration); + + // Concatenation of to_be_inserted and to_be_propagated + to_be_inserted.insert(to_be_inserted.begin(), to_be_propagated.begin(), to_be_propagated.end()); + to_be_propagated = to_be_inserted; + + // to_be_inserted treatment + for (auto& simplex_tbi : to_be_inserted) { + simplex_tbi.push_back(last_vertex); + } + std::vector last_simplex(1, last_vertex); + to_be_inserted.insert(to_be_inserted.begin(), last_simplex); + // i.e. (0,1,2) => + // [to_be_inserted | to_be_propagated] = [(1) (0,1) | (0)] + // [to_be_inserted | to_be_propagated] = [(2) (0,2) (1,2) (0,1,2) | (0) (1) (0,1)] + // N.B. : it is important the last inserted to be the highest in dimension + // in order to return the "last" insert_simplex result + + // insert all to_be_inserted + for (auto& simplex_tbi : to_be_inserted) { + insert_result = insert_vertex_vector(simplex_tbi, filtration); } - // N-Simplex insert - std::pair returned = insert_simplex_rec(Nsimplex, filtration); - } else if (Nsimplex.size() == 1) { - // 1-Simplex insert - End of recursivity - std::pair returned = insert_simplex_rec(Nsimplex, filtration); + } 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; + exit(-1); + } + std::vector first_simplex(1, the_simplex.back()); + // i.e. (0,1,2) => [to_be_inserted | to_be_propagated] = [(0) | ] + to_be_inserted.push_back(first_simplex); + + insert_result = insert_vertex_vector(first_simplex, filtration); } else { - // Nothing to insert - empty vector + std::cerr << "Simplex_tree::rec_insert_simplex_and_subfaces - Recursivity error" << std::endl; + exit(-1); } + return insert_result; } public: - /** \brief Assign a value 'key' to the key of the simplex * represented by the Simplex_handle 'sh'. */ void assign_key(Simplex_handle sh, Simplex_key key) { @@ -683,17 +701,6 @@ std::pair insert_simplex(const RandomAccessVertexRange & s return sh->second.children(); } - // void display_simplex(Simplex_handle sh) - // { - // std::cout << " " << "[" << filtration(sh) << "] "; - // for( auto vertex : simplex_vertex_range(sh) ) - // { std::cout << vertex << " "; } - // } - - // void print(Simplex_handle sh, std::ostream& os = std::cout) - // { for(auto v : simplex_vertex_range(sh)) {os << v << " ";} - // os << std::endl; } - public: /** Returns a pointer to the root nodes of the simplex tree. */ Siblings * root() { @@ -737,81 +744,6 @@ std::pair insert_simplex(const RandomAccessVertexRange & s is_before_in_filtration(this)); } -/** \brief Contracts two vertices : the contracted vertex is erased from the three, and the remaining vertex receives all the links of the contracted one. - \param remaining The value of the vertex within the other is contracted - \param deleted The value of the vertex to be contracted -*/ - void edge_contraction(Vertex_handle remaining, Vertex_handle deleted) - { - std::vector accessRemaining, accessDeleted; - accessRemaining.push_back(remaining); - accessDeleted.push_back(deleted); - Simplex_handle shr = find(accessRemaining), shd = find(accessDeleted); - if (has_children(shd)) - { - Siblings * sibDeleted, * sibRemaining; // We need the siblings - sibDeleted = shd->second.children(); - sibRemaining = shr->second.children(); - rec_insert(sibDeleted, sibRemaining, shd->first); - } - rec_delete(&root_, shd->first); - } - - -/** \brief recursively insert the members of a Sibling into another, any time the replacedVertex appears into the target Sibling - \param sibInserted The sibling to be inserted - \param sibTarget The target sibling on which the other sibling is copied - \param replacedVertex The replacedVertex (Vertex_handle) needed to insert the sibling -*/ - void rec_insert(Siblings * sibInserted, Siblings * sibTarget, Vertex_handle replacedVertex) - { - for (auto sh = sibTarget->members().begin(); sh != sibTarget->members().end(); ++sh) - { - if (has_children(sh)) - rec_insert(sibInserted, sh->second.children(), replacedVertex); - if (sh->first == replacedVertex) - insert_members(sibTarget, sibInserted); - } - } - -/** \brief Copy a Sibling into another, which is possibly not empty - \param sibInserted The sibling to be copied - \param sibTarget The sibling on which we wan't to copy the other sibling -*/ - void insert_members(Siblings * sibTarget, Siblings * sibInserted) - { - for (auto sh = sibInserted->members().begin(); sh != sibInserted->members().end(); ++sh) - { - std::pair member(sh->first, Node(sibTarget, sh->second.filtration())); - if (has_children(sh)) - { - std::vector> v(sh->second.children()->members().begin(), sh->second.children()->members().end()); - Siblings * newsib = new Siblings (sibTarget, sh->first); - for (auto it = v.begin(); it != v.end(); ++it) - newsib->members_.emplace(it->first, Node(sibTarget, it->second.filtration())); - insert_members(newsib, sh->second.children()); - member.second.assign_children(newsib); - - } - sibTarget->members_.emplace(member); - } - } - -/** \brief Erase every occurencies of a vertex in a Sibling - \param sib The sibling on which we wan't to erase the elements - \param deletedVertex The value of the members we wan't to erase -*/ - void rec_delete(Siblings * sib, Vertex_handle deletedVertex) - { - for (auto sh = sib->members().begin(); sh != sib->members().end(); ++sh) - { - if (has_children(sh)) - rec_delete(sh->second.children(), deletedVertex); - if (sh->first == deletedVertex) - sib->members_.erase(sh); - } - } - private: /** Recursive search of cofaces * This function uses DFS @@ -888,13 +820,13 @@ std::pair insert_simplex(const RandomAccessVertexRange & s assert(codimension >= 0); Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector copy(rg.begin(), rg.end()); - if (codimension + static_cast(copy.size()) > dimension_ + 1 || - (codimension == 0 && static_cast(copy.size()) > dimension_)) // n+codimension greater than dimension_ + if (codimension + static_cast (copy.size()) > dimension_ + 1 || + (codimension == 0 && static_cast (copy.size()) > dimension_)) // n+codimension greater than dimension_ return cofaces; // must be sorted in decreasing order assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); bool star = codimension == 0; - rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast(copy.size())); + rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast (copy.size())); return cofaces; } @@ -1080,7 +1012,7 @@ std::pair insert_simplex(const RandomAccessVertexRange & s while (true) { if (begin1->first == begin2->first) { Filtration_value filt = (std::max)({begin1->second.filtration(), begin2->second.filtration(), filtration_}); - intersection.emplace_back(begin1->first, Node(NULL, filt)); + intersection.emplace_back(begin1->first, Node(nullptr, filt)); if (++begin1 == end1 || ++begin2 == end2) return; // ----->> } else if (begin1->first < begin2->first) { diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index f09a11ea..d9666c52 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -9,8 +9,8 @@ #define BOOST_TEST_MODULE "simplex_tree" #include -#include "gudhi/graph_simplicial_complex.h" -#include "gudhi/reader_utils.h" +// ^ +// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. #include "gudhi/Simplex_tree.h" using namespace Gudhi; @@ -59,7 +59,6 @@ void test_iterators_on_empty_simplex_tree(typeST& tst) { BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) { const Filtration_value DEFAULT_FILTRATION_VALUE = 0; - // TEST OF DEFAULT CONSTRUCTOR std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; typeST st; @@ -125,10 +124,9 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p std::cout << "test_simplex_tree_contains - filtration=" << simplexTree.filtration(*f_simplex) << "||" << simplex.second << std::endl; BOOST_CHECK(AreAlmostTheSame(simplexTree.filtration(*f_simplex), simplex.second)); - int simplexIndex=simplex.first.size()-1; + int simplexIndex = simplex.first.size() - 1; std::sort(simplex.first.begin(), simplex.first.end()); // if the simplex wasn't sorted, the next test could fail - for( auto vertex : simplexTree.simplex_vertex_range(*f_simplex) ) - { + for (auto vertex : simplexTree.simplex_vertex_range(*f_simplex)) { std::cout << "test_simplex_tree_contains - vertex=" << vertex << "||" << simplex.first.at(simplexIndex) << std::endl; BOOST_CHECK(vertex == simplex.first.at(simplexIndex)); BOOST_CHECK(simplexIndex >= 0); @@ -159,33 +157,17 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons 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: - long long int num_simp = 0; + size_t num_simp = 0; for (auto f_simplex : simplexTree.complex_simplex_range()) { num_simp++; } - - BOOST_CHECK(simplexTree.num_simplices() == num_simp); -} -void test_cofaces(typeST& st, std::vector v, int dim, std::vector res) { - typeST::Cofaces_simplex_range cofaces; - if (dim == 0) - cofaces = st.star_simplex_range(st.find(v)); - else - cofaces = st.cofaces_simplex_range(st.find(v), dim); - for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) { - typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); - for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { - std::cout << "(" << *vertex << ")"; - } - std::cout << std::endl; - BOOST_CHECK(std::find(res.begin(), res.end(), *simplex) != res.end()); - } + BOOST_CHECK(simplexTree.num_simplices() == num_simp); } BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { @@ -201,7 +183,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ FIRST std::cout << " - INSERT 0" << std::endl; - typeVectorVertex firstSimplexVector { 0 }; + typeVectorVertex firstSimplexVector{0}; BOOST_CHECK(firstSimplexVector.size() == 1); typeSimplex firstSimplex = std::make_pair(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); typePairSimplexBool returnValue = st.insert_simplex(firstSimplex.first, firstSimplex.second); @@ -212,7 +194,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ SECOND std::cout << " - INSERT 1" << std::endl; - typeVectorVertex secondSimplexVector { 1 }; + typeVectorVertex secondSimplexVector{1}; BOOST_CHECK(secondSimplexVector.size() == 1); typeSimplex secondSimplex = std::make_pair(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(secondSimplex.first, secondSimplex.second); @@ -223,7 +205,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ THIRD std::cout << " - INSERT (0,1)" << std::endl; - typeVectorVertex thirdSimplexVector { 0, 1 }; + typeVectorVertex thirdSimplexVector{0, 1}; BOOST_CHECK(thirdSimplexVector.size() == 2); typeSimplex thirdSimplex = std::make_pair(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(thirdSimplex.first, thirdSimplex.second); @@ -234,7 +216,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ FOURTH std::cout << " - INSERT 2" << std::endl; - typeVectorVertex fourthSimplexVector { 2 }; + typeVectorVertex fourthSimplexVector{2}; BOOST_CHECK(fourthSimplexVector.size() == 1); typeSimplex fourthSimplex = std::make_pair(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(fourthSimplex.first, fourthSimplex.second); @@ -245,7 +227,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ FIFTH std::cout << " - INSERT (2,0)" << std::endl; - typeVectorVertex fifthSimplexVector { 2, 0 }; + typeVectorVertex fifthSimplexVector{2, 0}; BOOST_CHECK(fifthSimplexVector.size() == 2); typeSimplex fifthSimplex = std::make_pair(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(fifthSimplex.first, fifthSimplex.second); @@ -256,7 +238,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ SIXTH std::cout << " - INSERT (2,1)" << std::endl; - typeVectorVertex sixthSimplexVector { 2, 1 }; + typeVectorVertex sixthSimplexVector{2, 1}; BOOST_CHECK(sixthSimplexVector.size() == 2); typeSimplex sixthSimplex = std::make_pair(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(sixthSimplex.first, sixthSimplex.second); @@ -267,7 +249,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ SEVENTH std::cout << " - INSERT (2,1,0)" << std::endl; - typeVectorVertex seventhSimplexVector { 2, 1, 0 }; + typeVectorVertex seventhSimplexVector{2, 1, 0}; BOOST_CHECK(seventhSimplexVector.size() == 3); typeSimplex seventhSimplex = std::make_pair(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); returnValue = st.insert_simplex(seventhSimplex.first, seventhSimplex.second); @@ -278,7 +260,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ EIGHTH std::cout << " - INSERT 3" << std::endl; - typeVectorVertex eighthSimplexVector { 3 }; + typeVectorVertex eighthSimplexVector{3}; BOOST_CHECK(eighthSimplexVector.size() == 1); typeSimplex eighthSimplex = std::make_pair(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(eighthSimplex.first, eighthSimplex.second); @@ -289,7 +271,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ NINETH std::cout << " - INSERT (3,0)" << std::endl; - typeVectorVertex ninethSimplexVector { 3, 0 }; + typeVectorVertex ninethSimplexVector{3, 0}; BOOST_CHECK(ninethSimplexVector.size() == 2); typeSimplex ninethSimplex = std::make_pair(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(ninethSimplex.first, ninethSimplex.second); @@ -300,7 +282,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ TENTH std::cout << " - INSERT 0 (already inserted)" << std::endl; - typeVectorVertex tenthSimplexVector { 0 }; + typeVectorVertex tenthSimplexVector{0}; BOOST_CHECK(tenthSimplexVector.size() == 1); // With a different filtration value typeSimplex tenthSimplex = std::make_pair(tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); @@ -315,7 +297,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // ++ ELEVENTH std::cout << " - INSERT (2,1,0) (already inserted)" << std::endl; - typeVectorVertex eleventhSimplexVector { 2, 1, 0 }; + typeVectorVertex eleventhSimplexVector{2, 1, 0}; BOOST_CHECK(eleventhSimplexVector.size() == 3); typeSimplex eleventhSimplex = std::make_pair(eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); returnValue = st.insert_simplex(eleventhSimplex.first, eleventhSimplex.second); @@ -378,14 +360,13 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { } BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { - // TEST OF INSERTION std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF INSERTION" << std::endl; + std::cout << "TEST OF RECURSIVE INSERTION" << std::endl; typeST st; // ++ FIRST std::cout << " - INSERT (2,1,0)" << std::endl; - typeVectorVertex SimplexVector1 { 2, 1, 0 }; + typeVectorVertex SimplexVector1{2, 1, 0}; BOOST_CHECK(SimplexVector1.size() == 3); st.insert_simplex_and_subfaces(SimplexVector1); @@ -393,7 +374,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ++ SECOND std::cout << " - INSERT 3" << std::endl; - typeVectorVertex SimplexVector2 { 3 }; + typeVectorVertex SimplexVector2{3}; BOOST_CHECK(SimplexVector2.size() == 1); st.insert_simplex_and_subfaces(SimplexVector2); @@ -401,7 +382,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ++ THIRD std::cout << " - INSERT (0,3)" << std::endl; - typeVectorVertex SimplexVector3 { 3, 0 }; + typeVectorVertex SimplexVector3{3, 0}; BOOST_CHECK(SimplexVector3.size() == 2); st.insert_simplex_and_subfaces(SimplexVector3); @@ -409,7 +390,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ++ FOURTH std::cout << " - INSERT (1,0) (already inserted)" << std::endl; - typeVectorVertex SimplexVector4 { 1, 0 }; + typeVectorVertex SimplexVector4{1, 0}; BOOST_CHECK(SimplexVector4.size() == 2); st.insert_simplex_and_subfaces(SimplexVector4); @@ -417,7 +398,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ++ FIFTH std::cout << " - INSERT (3,4,5)" << std::endl; - typeVectorVertex SimplexVector5 { 3, 4, 5 }; + typeVectorVertex SimplexVector5{3, 4, 5}; BOOST_CHECK(SimplexVector5.size() == 3); st.insert_simplex_and_subfaces(SimplexVector5); @@ -425,7 +406,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ++ SIXTH std::cout << " - INSERT (0,1,6,7)" << std::endl; - typeVectorVertex SimplexVector6 { 0, 1, 6, 7 }; + typeVectorVertex SimplexVector6{0, 1, 6, 7}; BOOST_CHECK(SimplexVector6.size() == 4); st.insert_simplex_and_subfaces(SimplexVector6); @@ -462,7 +443,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // ------------------------------------------------------------------------------------------------------------------ // Find in the simplex_tree // ------------------------------------------------------------------------------------------------------------------ - typeVectorVertex simpleSimplexVector { 1 }; + typeVectorVertex simpleSimplexVector{1}; Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) @@ -472,7 +453,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); - typeVectorVertex unknownSimplexVector { 15 }; + typeVectorVertex unknownSimplexVector{15}; simplexFound = st.find(unknownSimplexVector); std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) @@ -491,7 +472,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is found BOOST_CHECK(simplexFound != st.null_simplex()); - typeVectorVertex otherSimplexVector { 1, 15 }; + typeVectorVertex otherSimplexVector{1, 15}; simplexFound = st.find(otherSimplexVector); std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) @@ -501,7 +482,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is NOT found BOOST_CHECK(simplexFound == st.null_simplex()); - typeVectorVertex invSimplexVector { 1, 2, 0 }; + typeVectorVertex invSimplexVector{1, 2, 0}; simplexFound = st.find(invSimplexVector); std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) @@ -522,143 +503,183 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { } std::cout << std::endl; } +} + +void test_cofaces(typeST& st, std::vector expected, int dim, std::vector res) { + 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); + for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { + std::cout << "(" << *vertex << ")"; + } + std::cout << std::endl; + BOOST_CHECK(std::find(res.begin(), res.end(), *simplex) != res.end()); + } +} +BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) { std::cout << "********************************************************************" << std::endl; - // TEST COFACE ALGORITHM + std::cout << "TEST COFACE ALGORITHM" << std::endl; + typeST st; + + typeVectorVertex SimplexVector{2, 1, 0}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {3, 0}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {3, 4, 5}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {0, 1, 6, 7}; + st.insert_simplex_and_subfaces(SimplexVector); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + // FIXME st.set_dimension(3); - std::cout << "COFACE ALGORITHM" << std::endl; - std::vector v; - std::vector simplex; + + std::vector simplex_result; std::vector result; - v.push_back(3); - std::cout << "First test : " << std::endl; - std::cout << "Star of (3):" << std::endl; - - simplex.push_back(3); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(3); - simplex.push_back(0); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(4); - simplex.push_back(3); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(5); - simplex.push_back(4); - simplex.push_back(3); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(5); - simplex.push_back(3); - result.push_back(st.find(simplex)); - simplex.clear(); - - test_cofaces(st, v, 0, result); - v.clear(); + std::cout << "First test - Star of (3):" << std::endl; + + simplex_result = {3}; + result.push_back(st.find(simplex_result)); + + simplex_result = {3, 0}; + result.push_back(st.find(simplex_result)); + + simplex_result = {4, 3}; + result.push_back(st.find(simplex_result)); + + simplex_result = {5, 4, 3}; + result.push_back(st.find(simplex_result)); + + simplex_result = {5, 3}; + result.push_back(st.find(simplex_result)); + simplex_result.clear(); + + std::vector vertex = {3}; + test_cofaces(st, vertex, 0, result); + vertex.clear(); result.clear(); - v.push_back(1); - v.push_back(7); - std::cout << "Second test : " << std::endl; - std::cout << "Star of (1,7): " << std::endl; - - simplex.push_back(7); - simplex.push_back(1); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(7); - simplex.push_back(6); - simplex.push_back(1); - simplex.push_back(0); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(7); - simplex.push_back(1); - simplex.push_back(0); - result.push_back(st.find(simplex)); - simplex.clear(); - - simplex.push_back(7); - simplex.push_back(6); - simplex.push_back(1); - result.push_back(st.find(simplex)); - simplex.clear(); - - test_cofaces(st, v, 0, result); + vertex.push_back(1); + vertex.push_back(7); + std::cout << "Second test - Star of (1,7): " << std::endl; + + simplex_result = {7, 1}; + result.push_back(st.find(simplex_result)); + + simplex_result = {7, 6, 1, 0}; + result.push_back(st.find(simplex_result)); + + simplex_result = {7, 1, 0}; + result.push_back(st.find(simplex_result)); + + simplex_result = {7, 6, 1}; + result.push_back(st.find(simplex_result)); + + test_cofaces(st, vertex, 0, result); result.clear(); - std::cout << "Third test : " << std::endl; - std::cout << "2-dimension Cofaces of simplex(1,7) : " << std::endl; + std::cout << "Third test - 2-dimension Cofaces of simplex(1,7) : " << std::endl; - simplex.push_back(7); - simplex.push_back(1); - simplex.push_back(0); - result.push_back(st.find(simplex)); - simplex.clear(); + simplex_result = {7, 1, 0}; + result.push_back(st.find(simplex_result)); - simplex.push_back(7); - simplex.push_back(6); - simplex.push_back(1); - result.push_back(st.find(simplex)); - simplex.clear(); + simplex_result = {7, 6, 1}; + result.push_back(st.find(simplex_result)); - test_cofaces(st, v, 1, result); + test_cofaces(st, vertex, 1, result); result.clear(); std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension) :" << std::endl; - test_cofaces(st, v, 5, result); - // std::cout << "Cofaces with an empty codimension" << std::endl; - // test_cofaces(st, v, -1, result); + test_cofaces(st, vertex, 5, result); + + //std::cout << "Cofaces with an empty codimension" << std::endl; + //test_cofaces(st, vertex, -1, result); // std::cout << "Cofaces in an empty simplex tree" << std::endl; // typeST empty_tree; - // test_cofaces(empty_tree, v, 1, result); - // std::cout << "Cofaces of an empty simplex" << std::endl; - // v.clear(); - // test_cofaces(st, v, 1, result); - - std::cout << "********************************************************************" << std::endl; - // TEST Copy constructor / Move - std::cout << "Printing st" << std::endl; - std::cout << &st << std::endl; - st.print_tree(); - typeST st_copy_1 = st; - BOOST_CHECK(st == st_copy_1); - typeST st_move = std::move(st); - std::cout << "Printing a copy of st" << std::endl; - std::cout << &st_copy_1 << std::endl; - st_copy_1.print_tree(); - BOOST_CHECK(st_move == st_copy_1); - std::cout << "Printing a move of st" << std::endl; - std::cout << &st_move << std::endl; - st_move.print_tree(); - typeST st_empty; - BOOST_CHECK(st == st_empty); - std::cout << "Printing st again" << std::endl; - std::cout << &st << std::endl; - st.print_tree(); - - std::cout << "********************************************************************" << std::endl; - // TEST Edge_contraction - typeST st_copy_2 = st_copy_1, st_copy_3 = st_copy_1, st_copy_4 = st_copy_1; - st_copy_1.edge_contraction(0, 3); - std::cout << "Printing a copy of st, with the edge (0, 3) contracted, 3 being contracted in 0" << std::endl; - st_copy_1.print_tree(); - st_copy_2.edge_contraction(1, 3); - std::cout << "Printing a copy of st, with the edge (1, 3) contracted, 3 being contracted in 1" << std::endl; - st_copy_2.print_tree(); - st_copy_3.edge_contraction(3, 4); - std::cout << "Printing a copy of st, with the edge (3, 4) contracted, 4 being contracted in 3" << std::endl; - st_copy_3.print_tree(); - st_copy_4.edge_contraction(1, 6); - std::cout << "Printing a copy of st, with the edge (1, 6) contracted, 6 being contracted in 1" << std::endl; - st_copy_4.print_tree(); + // test_cofaces(empty_tree, vertex, 1, result); + //std::cout << "Cofaces of an empty simplex" << std::endl; + //vertex.clear(); + // test_cofaces(st, vertex, 1, result); + +} +BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST COPY MOVE CONSTRUCTORS" << std::endl; + typeST st; + + typeVectorVertex SimplexVector{2, 1, 0}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {3, 0}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {3, 4, 5}; + st.insert_simplex_and_subfaces(SimplexVector); + + SimplexVector = {0, 1, 6, 7}; + st.insert_simplex_and_subfaces(SimplexVector); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + // FIXME + st.set_dimension(3); + + std::cout << "Printing st - address = " << &st << std::endl; + //std::cout << st << std::endl; + + // Copy constructor + typeST st_copy = st; + std::cout << "Printing a copy of st - address = " << &st_copy << std::endl; + //std::cout << st_copy << std::endl; + + // Check the data are the same + BOOST_CHECK(st == st_copy); + // Check there is a new simplex tree reference + BOOST_CHECK(&st != &st_copy); + + // Move constructor + typeST st_move = std::move(st); + std::cout << "Printing a move of st - address = " << &st_move << std::endl; + //std::cout << st_move << std::endl; + + // Check the data are the same + BOOST_CHECK(st_move == st_copy); + // Check there is a new simplex tree reference + BOOST_CHECK(&st_move != &st_copy); + BOOST_CHECK(&st_move != &st); + + 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); + + std::cout << "Printing st once again- address = " << &st << std::endl; + //std::cout << st << std::endl; } -- cgit v1.2.3 From c71a91c4192c82c464c8300a1b7b2e9de8fb2ca9 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 4 Sep 2015 11:50:20 +0000 Subject: constify ref git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@773 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 952881703aa1868554a21caed9302df5b98fea31 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b38e5813..5588cafd 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -501,7 +501,7 @@ class Simplex_tree { private: /** Find function, with a sorted range of vertices. */ - Simplex_handle find_simplex(std::vector & simplex) { + Simplex_handle find_simplex(const std::vector & simplex) { Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; Vertex_handle last = simplex[simplex.size() - 1]; -- cgit v1.2.3 From bc9c3de6cf45a44666ca3ac0a5a2c2151a4996d9 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Wed, 9 Sep 2015 08:47:19 +0000 Subject: Issue fix for operator==. Replaced by is_equal function (constify is required first for operator==) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@775 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 90d5e30caafb0679117be1ea40a12753847e9ab7 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 35 ++++++++++++------------ src/Simplex_tree/test/simplex_tree_unit_test.cpp | 6 ++-- 2 files changed, 20 insertions(+), 21 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 5588cafd..e9b12fd7 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -347,32 +347,31 @@ class Simplex_tree { public: /** \brief Checks if two simplex trees are equal. */ - bool operator==(Simplex_tree st2) { - return (this->null_vertex_ == st2.null_vertex_ - && this->threshold_ == st2.threshold_ - && this->dimension_ == st2.dimension_ - && rec_equal(&root_, &st2.root_)); - } - - /** \brief Checks if two simplex trees are different. */ - bool operator!=(Simplex_tree st2) { - return (!(*this == st2)); + // TODO: constify is required to make an operator== + bool is_equal(Simplex_tree& st2) + { + if ((null_vertex_ != st2.null_vertex_) || + (threshold_ != st2.threshold_) || + (dimension_ != st2.dimension_)) + return false; + return rec_equal(&root_, &st2.root_); } - + /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ private: - bool rec_equal(Siblings * s1, Siblings * s2) { + bool rec_equal(Siblings* s1, Siblings* s2) { if (s1->members().size() != s2->members().size()) return false; - for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); sh1 != s1->members().end(); ++sh1, ++sh2) { + for (auto sh1 = s1->members().begin(), sh2 = s2->members().begin(); + (sh1 != s1->members().end() && sh2 != s2->members().end()); ++sh1, ++sh2) { if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) return false; - if (has_children(sh1)) - return rec_equal(sh1->second.children(), sh2->second.children()); - else if (has_children(sh2)) + if (((!has_children(sh1)) && (has_children(sh2))) || ((has_children(sh1)) && (!has_children(sh2)))) return false; - else - return true; + // Recursivity on children only if both have children + else if (has_children(sh1) && has_children(sh2)) + if (!rec_equal(sh1->second.children(), sh2->second.children())) + return false; } return true; } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index d9666c52..6be6d4f3 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -657,7 +657,7 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { //std::cout << st_copy << std::endl; // Check the data are the same - BOOST_CHECK(st == st_copy); + BOOST_CHECK(st.is_equal(st_copy)); // Check there is a new simplex tree reference BOOST_CHECK(&st != &st_copy); @@ -667,14 +667,14 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { //std::cout << st_move << std::endl; // Check the data are the same - BOOST_CHECK(st_move == st_copy); + BOOST_CHECK(st_move.is_equal(st_copy)); // Check there is a new simplex tree reference BOOST_CHECK(&st_move != &st_copy); BOOST_CHECK(&st_move != &st); typeST st_empty; // Check st has been emptied by the move - BOOST_CHECK(st == st_empty); + BOOST_CHECK(st.is_equal(st_empty)); BOOST_CHECK(st.filtration() == 0); BOOST_CHECK(st.dimension() == -1); BOOST_CHECK(st.num_simplices() == 0); -- cgit v1.2.3 From 726e052cceda6d79792aceb6acb6f4d72bb99fca Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 9 Sep 2015 14:06:10 +0000 Subject: Minor clean-ups. Don't copy filtration_vect_. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@778 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: af49ecce9ce78f2436be10bb7aed5379466d1cce --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 28 +++++++++++++-------------- 1 file changed, 14 insertions(+), 14 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index e9b12fd7..b8c62cd1 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -290,7 +290,7 @@ class Simplex_tree { Simplex_tree(const Simplex_tree& simplex_source) : null_vertex_(simplex_source.null_vertex_), threshold_(simplex_source.threshold_), - filtration_vect_(simplex_source.filtration_vect_), + filtration_vect_(), dimension_(simplex_source.dimension_) { auto root_source = simplex_source.root_; auto memb_source = root_source.members(); @@ -299,16 +299,15 @@ class Simplex_tree { } /** \brief depth first search, inserts simplices when reaching a leaf. */ - void rec_copy(Siblings *sib, Siblings *sib_copy) { - for (auto sh = sib->members().begin(), sh_copy = sib_copy->members().begin(); - sh != sib->members().end(); ++sh, ++sh_copy) { - if (has_children(sh_copy)) { - Siblings * newsib = new Siblings(sib, sh_copy->first); - newsib->members_.reserve(sh_copy->second.children()->members().size()); - for (auto it = sh_copy->second.children()->members().begin(); - it != sh_copy->second.children()->members().end(); ++it) - newsib->members_.emplace_hint(newsib->members_.end(), it->first, Node(sib, it->second.filtration())); - rec_copy(newsib, sh_copy->second.children()); + void rec_copy(Siblings *sib, Siblings *sib_source) { + for (auto sh = sib->members().begin(), sh_source = sib_source->members().begin(); + sh != sib->members().end(); ++sh, ++sh_source) { + if (has_children(sh_source)) { + 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())); + rec_copy(newsib, sh_source->second.children()); sh->second.assign_children(newsib); } } @@ -318,7 +317,8 @@ class Simplex_tree { 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_)), + root_(std::move(old.root_)), + filtration_vect_(std::move(old.filtration_vect_)), dimension_(std::move(old.dimension_)) { old.dimension_ = -1; old.threshold_ = 0; @@ -366,10 +366,10 @@ class Simplex_tree { (sh1 != s1->members().end() && sh2 != s2->members().end()); ++sh1, ++sh2) { if (sh1->first != sh2->first || sh1->second.filtration() != sh2->second.filtration()) return false; - if (((!has_children(sh1)) && (has_children(sh2))) || ((has_children(sh1)) && (!has_children(sh2)))) + if (has_children(sh1) != has_children(sh2)) return false; // Recursivity on children only if both have children - else if (has_children(sh1) && has_children(sh2)) + else if (has_children(sh1)) if (!rec_equal(sh1->second.children(), sh2->second.children())) return false; } -- cgit v1.2.3 From 606d3470542a3112ce6d67d4a493b98be6ea2c94 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 9 Sep 2015 16:08:03 +0000 Subject: Minor clean-up. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@779 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: dbb319a592f041cccfa54f50cee2554d423a2291 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b8c62cd1..05c493dd 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -503,7 +503,7 @@ class Simplex_tree { Simplex_handle find_simplex(const std::vector & simplex) { Siblings * tmp_sib = &root_; Dictionary_it tmp_dit; - Vertex_handle last = simplex[simplex.size() - 1]; + Vertex_handle last = simplex.back(); for (auto v : simplex) { tmp_dit = tmp_sib->members_.find(v); if (tmp_dit == tmp_sib->members_.end()) { @@ -576,10 +576,10 @@ class Simplex_tree { * The filtration value * assigned to the new simplex must preserve the monotonicity of the filtration. * - * The type RandomAccessVertexRange must be a range for which .begin() and - * .end() return random access iterators, with 'value_type' Vertex_handle. */ - template - std::pair insert_simplex(const RandomAccessVertexRange & simplex, + * The type InputVertexRange must be a range for which .begin() and + * .end() return input iterators, with 'value_type' Vertex_handle. */ + template + std::pair insert_simplex(const InputVertexRange & simplex, Filtration_value filtration) { auto first = std::begin(simplex); auto last = std::end(simplex); -- cgit v1.2.3 From 2fcfb64cecea616c3a12f1f3bbd475ee33bb35b3 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 9 Sep 2015 16:35:51 +0000 Subject: FIXME -> Note. This is not a huge/trivial bug that has to be fixed immediately. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST-options@780 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: a4cb89782dc6d14ff1fc4a567e510ec4f40e0ac9 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index aeb0364f..03e15a7d 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -117,7 +117,7 @@ class Simplex_tree { /* Type of node in the simplex tree. */ typedef Simplex_tree_node_explicit_storage Node; /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */ - // FIXME: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and Simplex_key next to each other). + // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and Simplex_key next to each other). typedef typename boost::container::flat_map Dictionary; /* \brief Set of nodes sharing a same parent in the simplex tree. */ -- cgit v1.2.3 From 86d8370c00ec9733469864ed7842f72f4f8417b8 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 10 Sep 2015 07:49:57 +0000 Subject: operator== git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@782 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 498e8c3f35d105b22752983360fbf8229c224776 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 13 ++++++++----- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 10 +++------- 2 files changed, 11 insertions(+), 12 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 05c493dd..a5ad6a79 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -347,18 +347,21 @@ class Simplex_tree { public: /** \brief Checks if two simplex trees are equal. */ - // TODO: constify is required to make an operator== - bool is_equal(Simplex_tree& st2) - { + 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_); } - - /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ + + /** \brief Checks if two simplex trees are different. */ + bool operator!=(Simplex_tree& st2) { + return (!(*this == st2)); + } + private: + /** rec_equal: Checks recursively whether or not two simplex trees are equal, using depth first search. */ bool rec_equal(Siblings* s1, Siblings* s2) { if (s1->members().size() != s2->members().size()) return false; diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 6be6d4f3..eb3557ae 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -649,37 +649,33 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { st.set_dimension(3); std::cout << "Printing st - address = " << &st << std::endl; - //std::cout << st << std::endl; // Copy constructor typeST st_copy = st; std::cout << "Printing a copy of st - address = " << &st_copy << std::endl; - //std::cout << st_copy << std::endl; // Check the data are the same - BOOST_CHECK(st.is_equal(st_copy)); + BOOST_CHECK(st == st_copy); // Check there is a new simplex tree reference BOOST_CHECK(&st != &st_copy); // Move constructor typeST st_move = std::move(st); std::cout << "Printing a move of st - address = " << &st_move << std::endl; - //std::cout << st_move << std::endl; // Check the data are the same - BOOST_CHECK(st_move.is_equal(st_copy)); + BOOST_CHECK(st_move == st_copy); // Check there is a new simplex tree reference BOOST_CHECK(&st_move != &st_copy); BOOST_CHECK(&st_move != &st); typeST st_empty; // Check st has been emptied by the move - BOOST_CHECK(st.is_equal(st_empty)); + 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); std::cout << "Printing st once again- address = " << &st << std::endl; - //std::cout << st << std::endl; } -- cgit v1.2.3 From 281f792879fd3c84d89d38bb10019cc958120afa Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 10 Sep 2015 08:18:34 +0000 Subject: doc issue git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/copy_move@783 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e0fdf5443aea57b7231883c89e1e3fd5007db550 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index a5ad6a79..9989e850 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -528,7 +528,7 @@ class Simplex_tree { //{ return root_.members_.find(v); } private: - /** \brief Recursively insert a simplex represented by a vector of vertex. + /** \brief Inserts a simplex represented by a vector of vertex. \warning the vector must be sorted by increasing vertex handle order */ std::pair insert_vertex_vector(const std::vector& simplex, Filtration_value filtration) { -- cgit v1.2.3 From d8121aa7f9d6a9c8faa4aa532162b7d4452a6c29 Mon Sep 17 00:00:00 2001 From: glisse Date: Thu, 24 Sep 2015 13:06:54 +0000 Subject: There is little point obfuscating Filtration_simplex_range. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@792 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0365c6b1612bfdde72746765774729ccb6037f44 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 17 ++++++----------- 1 file changed, 6 insertions(+), 11 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b911552d..914247b5 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -213,12 +213,12 @@ class Simplex_tree { /** \brief Range over the simplices of the skeleton of the simplicial complex, for a given * dimension. */ typedef boost::iterator_range Skeleton_simplex_range; + /** \brief Range over the simplices of the simplicial complex, ordered by the filtration. */ + typedef std::vector Filtration_simplex_range; /** \brief Iterator over the simplices of the simplicial complex, ordered by the filtration. * * 'value_type' is Simplex_handle. */ - typedef typename std::vector::iterator Filtration_simplex_iterator; - /** \brief Range over the simplices of the simplicial complex, ordered by the filtration. */ - typedef boost::iterator_range Filtration_simplex_range; + typedef typename Filtration_simplex_range::const_iterator Filtration_simplex_iterator; /* @} */ // end name range and iterator types /** \name Range and iterator methods @@ -271,16 +271,11 @@ class Simplex_tree { * The filtration must be valid. If the filtration has not been initialized yet, the * method initializes it (i.e. order the simplices). If the complex has changed since the last time the filtration * was initialized, please call `initialize_filtration()` to recompute it. */ - Filtration_simplex_range filtration_simplex_range(Indexing_tag) { + Filtration_simplex_range const& filtration_simplex_range(Indexing_tag=Indexing_tag()) { if (filtration_vect_.empty()) { initialize_filtration(); } - return Filtration_simplex_range(filtration_vect_.begin(), - filtration_vect_.end()); - } - - Filtration_simplex_range filtration_simplex_range() { - return filtration_simplex_range(Indexing_tag()); + return filtration_vect_; } /** \brief Returns a range over the vertices of a simplex. @@ -1082,7 +1077,7 @@ class Simplex_tree { * of the simplex, and fil is its filtration value. */ void print_hasse(std::ostream& os) { os << num_simplices() << " " << std::endl; - for (auto sh : filtration_simplex_range(Indexing_tag())) { + for (auto sh : filtration_simplex_range()) { os << dimension(sh) << " "; for (auto b_sh : boundary_simplex_range(sh)) { os << key(b_sh) << " "; -- cgit v1.2.3 From 053a5a2f77f4747d45bc781c90b44791d6131488 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 30 Sep 2015 20:17:19 +0000 Subject: In is_before_in_filtration, access the filtration values directly without checking for null_simplex. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@811 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: cff7635e067a691764ca250067997b8b48cb6420 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/Simplex_tree/include') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 914247b5..96565ff1 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -908,8 +908,9 @@ class Simplex_tree { : st_(st) { } bool operator()(const Simplex_handle sh1, const Simplex_handle sh2) const { - if (st_->filtration(sh1) != st_->filtration(sh2)) { - return st_->filtration(sh1) < st_->filtration(sh2); + // 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(); } // is sh1 a proper subface of sh2 return st_->reverse_lexicographic_order(sh1, sh2); -- cgit v1.2.3