diff options
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 99 | ||||
| -rw-r--r-- | src/Simplex_tree/test/simplex_tree_unit_test.cpp | 1 |
2 files changed, 64 insertions, 36 deletions
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<class RandomAccessVertexRange> Simplex_handle find(RandomAccessVertexRange & s) { - if (s.begin() == s.end()) - std::cerr << "Empty simplex \n"; + std::vector<Vertex_handle> copy = s; + sort(s.begin(), s.end()); + return find_rec(s); + } - sort(s.begin(), s.end()); + private: + /** recursive function of find */ + template<class RandomAccessVertexRange> + 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<class RandomAccessVertexRange> - std::pair<Simplex_handle, bool> insert_simplex(RandomAccessVertexRange & simplex, + std::pair<Simplex_handle, bool> insert_simplex_rec(RandomAccessVertexRange & simplex, Filtration_value filtration) { if (simplex.empty()) { return std::pair<Simplex_handle, bool>(null_simplex(), true); } - - sort(simplex.begin(), simplex.end()); // must be sorted in increasing order - Siblings * curr_sib = &root_; std::pair<Simplex_handle, bool> 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<class RandomAccessVertexRange> +std::pair<Simplex_handle, bool> insert_simplex(RandomAccessVertexRange & simplex, + Filtration_value filtration) { + std::vector<Vertex_handle> 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<class RandomAccessVertexRange> 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<class RandomAccessVertexRange> + 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<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + std::pair<Simplex_handle, bool> 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<Simplex_handle, bool> returned = insert_simplex(Nsimplex, filtration); + std::pair<Simplex_handle, bool> 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; |