From c336a0789b088c729308f0ff31eb5e9a92375ca4 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 16 Jun 2015 14:01:45 +0000 Subject: This development includes the Simplex_tree coface and star functions implementation Simplex_tree find function fix (when find on an empty RandomAccessVertexRange) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@620 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5310514623bb7040a4118fa9c6898a5ce894d0c4 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 106 ++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) (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..a66aa9d1 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -398,7 +398,10 @@ class Simplex_tree { template Simplex_handle find(RandomAccessVertexRange & s) { if (s.begin() == s.end()) + { std::cerr << "Empty simplex \n"; + return null_simplex(); + } sort(s.begin(), s.end()); @@ -599,6 +602,109 @@ class Simplex_tree { std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); } + +private: + + /** Recursive search of cofaces + */ + template + void rec_coface(RandomAccessVertexRange &vertices, Siblings *curr_sib, Dictionary *curr_res, std::vector& cofaces, unsigned int length, unsigned long codimension) + { + for (auto sib = curr_sib->members().begin(); sib != curr_sib->members().end() && (vertices.empty() || sib->first <= vertices[vertices.size()-1]); ++sib) + { + bool continueRecursion = (codimension == length || curr_res->size() <= codimension); // dimension of actual simplex <= codimension + if (vertices.empty()) + { + if (curr_res->size() >= length && continueRecursion) + // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface + { + curr_res->emplace(sib->first, sib->second); + bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension + if (egalDim) + cofaces.push_back(*curr_res); + if (has_children(sib)) + rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); + curr_res->erase(curr_res->end()-1); + } + } + else if (continueRecursion) + { + if (sib->first == vertices[vertices.size()-1]) // If curr_sib matches with the top vertex + { + curr_res->emplace(sib->first, sib->second); + bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension + if (vertices.size() == 1 && curr_res->size() > length && egalDim) + cofaces.push_back(*curr_res); + if (has_children(sib)) + { // Rec call + Vertex_handle tmp = vertices[vertices.size()-1]; + vertices.pop_back(); + rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); + vertices.push_back(tmp); + } + curr_res->erase(curr_res->end()-1); + } + else // (sib->first < vertices[vertices.size()-1]) + { + if (has_children(sib)) + { + curr_res->emplace(sib->first, sib->second); + rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); + curr_res->erase(curr_res->end()-1); + } + } + } + } + } + +public: + /** \brief Compute the star of a n simplex + * \param vertices List of vertices which represent the n simplex. + * \return Vector of Dictionary, empty vector if no cofaces found. + */ + + std::vector star(const Simplex_handle &vertices) { + return coface(vertices, 0); + } + + + + /** \brief Compute the cofaces of a n simplex + * \param vertices List of vertices which represent the n simplex. + * \param codimension The function returns the n+codimension-simplices. If codimension = 0, return all cofaces (equivalent of star function) + * \return Vector of Dictionary, empty vector if no cofaces found. + * \warning n+codimension must be lower than Simplex_tree dimension, otherwise an an empty vector is returned. + */ + + std::vector coface(const Simplex_handle &vertices, int codimension) { + std::vector cofaces; + if (dimension_ == -1) + { + std::cerr << "Simplex_tree::coface - empty simplex tree" << std::endl; + return cofaces; // ----->> + } + if (vertices == null_simplex()) { + std::cerr << "Simplex_tree::coface - empty vertices list" << std::endl; + return cofaces; // ----->> + } + if (codimension < 0) { + std::cerr << "Simplex_tree::coface - codimension is empty" << std::endl; + return cofaces; // ----->> + } + std::vector copy; + Simplex_vertex_range rg = simplex_vertex_range(vertices); + for (auto it = rg.begin(); it != rg.end(); ++it) + copy.push_back(*it); + if (codimension + copy.size() > (unsigned long)(dimension_ + 1) || (codimension == 0 && copy.size() > (unsigned long)dimension_) ) { + std::cerr << "Simplex_tree::coface - codimension + vertices list size cannot be greater than Simplex_tree dimension" << std::endl; + return cofaces; // ----->> + } + std::sort(copy.begin(), copy.end(), std::greater()); // must be sorted in decreasing order + Dictionary res; + rec_coface(copy, &root_, &res, cofaces, copy.size(), codimension + copy.size()); + return cofaces; + } + private: /** \brief Returns true iff the list of vertices of sh1 -- cgit v1.2.3 From 6969ac7694dcbc859a770c9eccf997e64e08fff3 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 17 Jun 2015 13:33:18 +0000 Subject: Fix doc - coface function now returns std::vector - test function now tests the whole result - debug code deleted git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@621 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b4e55297e8891d45941006f3817787b293a47cc1 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 77 ++-- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 432 +++++++++++++---------- 2 files changed, 275 insertions(+), 234 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 a66aa9d1..26a8eba6 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -122,7 +122,7 @@ class Simplex_tree { 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: @@ -397,11 +397,8 @@ class Simplex_tree { */ template Simplex_handle find(RandomAccessVertexRange & s) { - if (s.begin() == s.end()) - { - std::cerr << "Empty simplex \n"; + if (s.begin() == s.end()) // Empty simplex return null_simplex(); - } sort(s.begin(), s.end()); @@ -606,9 +603,18 @@ class Simplex_tree { private: /** Recursive search of cofaces + * This function uses DFS + *\param vertices contains a list of vertices, which represent the simplex. + *\param curr_res contains a list of vertices, which represent the current path in the tree. + *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. + *\param length length of the vertices list + * 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_res so that we didn't change the parameters. + * If the vertices list is empty, we need to check if the size of the curr_res list matches with the dimension of the cofaces asked. */ template - void rec_coface(RandomAccessVertexRange &vertices, Siblings *curr_sib, Dictionary *curr_res, std::vector& cofaces, unsigned int length, unsigned long codimension) + void rec_coface(RandomAccessVertexRange &vertices, Siblings *curr_sib, RandomAccessVertexRange *curr_res, std::vector& cofaces, unsigned int length, unsigned long codimension) { for (auto sib = curr_sib->members().begin(); sib != curr_sib->members().end() && (vertices.empty() || sib->first <= vertices[vertices.size()-1]); ++sib) { @@ -618,23 +624,23 @@ private: if (curr_res->size() >= length && continueRecursion) // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface { - curr_res->emplace(sib->first, sib->second); + curr_res->push_back(sib->first); bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension if (egalDim) - cofaces.push_back(*curr_res); + cofaces.push_back(find(*curr_res)); if (has_children(sib)) rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); - curr_res->erase(curr_res->end()-1); + curr_res->pop_back(); } } else if (continueRecursion) { if (sib->first == vertices[vertices.size()-1]) // If curr_sib matches with the top vertex { - curr_res->emplace(sib->first, sib->second); + curr_res->push_back(sib->first); bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension if (vertices.size() == 1 && curr_res->size() > length && egalDim) - cofaces.push_back(*curr_res); + cofaces.push_back(find(*curr_res)); if (has_children(sib)) { // Rec call Vertex_handle tmp = vertices[vertices.size()-1]; @@ -642,15 +648,15 @@ private: rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); vertices.push_back(tmp); } - curr_res->erase(curr_res->end()-1); + curr_res->pop_back(); } else // (sib->first < vertices[vertices.size()-1]) { if (has_children(sib)) { - curr_res->emplace(sib->first, sib->second); + curr_res->push_back(sib->first); rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); - curr_res->erase(curr_res->end()-1); + curr_res->pop_back(); } } } @@ -659,48 +665,39 @@ private: public: /** \brief Compute the star of a n simplex - * \param vertices List of vertices which represent the n simplex. - * \return Vector of Dictionary, empty vector if no cofaces found. + * \param vertices handles the simplex of which we search the star + * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - std::vector star(const Simplex_handle &vertices) { + std::vector star(const Simplex_handle &vertices) { return coface(vertices, 0); } /** \brief Compute the cofaces of a n simplex - * \param vertices List of vertices which represent the n simplex. - * \param codimension The function returns the n+codimension-simplices. If codimension = 0, return all cofaces (equivalent of star function) - * \return Vector of Dictionary, empty vector if no cofaces found. + * \param vertices handles 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. * \warning n+codimension must be lower than Simplex_tree dimension, otherwise an an empty vector is returned. */ - std::vector coface(const Simplex_handle &vertices, int codimension) { - std::vector cofaces; - if (dimension_ == -1) - { - std::cerr << "Simplex_tree::coface - empty simplex tree" << std::endl; - return cofaces; // ----->> - } - if (vertices == null_simplex()) { - std::cerr << "Simplex_tree::coface - empty vertices list" << std::endl; - return cofaces; // ----->> - } - if (codimension < 0) { - std::cerr << "Simplex_tree::coface - codimension is empty" << std::endl; - return cofaces; // ----->> - } + std::vector coface(const Simplex_handle &vertices, int codimension) { + std::vector cofaces; + if (dimension_ == -1) // Empty simplex tree + return cofaces; + if (vertices == null_simplex()) // Empty simplex + return cofaces; + if (codimension < 0) // codimension must be positive or null integer + return cofaces; std::vector copy; Simplex_vertex_range rg = simplex_vertex_range(vertices); for (auto it = rg.begin(); it != rg.end(); ++it) copy.push_back(*it); - if (codimension + copy.size() > (unsigned long)(dimension_ + 1) || (codimension == 0 && copy.size() > (unsigned long)dimension_) ) { - std::cerr << "Simplex_tree::coface - codimension + vertices list size cannot be greater than Simplex_tree dimension" << std::endl; - return cofaces; // ----->> - } + if (codimension + copy.size() > (unsigned long)(dimension_ + 1) || (codimension == 0 && copy.size() > (unsigned long)dimension_) ) // n+codimension greater than dimension_ + return cofaces; std::sort(copy.begin(), copy.end(), std::greater()); // must be sorted in decreasing order - Dictionary res; + std::vector res; rec_coface(copy, &root_, &res, cofaces, copy.size(), codimension + copy.size()); return cofaces; } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index f685f079..eaae4149 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -1,9 +1,11 @@ #define BOOST_TEST_MODULE simplex_tree test #include +#include #include #include #include #include +#include #include // std::pair, std::make_pair @@ -24,6 +26,7 @@ typedef std::pair typeSimplex; const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) -1; const Filtration_value DEFAULT_FILTRATION_VALUE = (const Filtration_value) 0.0; + void test_empty_simplex_tree(typeST& tst) { BOOST_CHECK(tst.null_vertex() == DEFAULT_VERTEX_HANDLE); BOOST_CHECK(tst.filtration() == DEFAULT_FILTRATION_VALUE); @@ -36,6 +39,7 @@ void test_empty_simplex_tree(typeST& tst) { BOOST_CHECK(tst.dimension() == -1); } + void test_iterators_on_empty_simplex_tree(typeST& tst) { std::cout << "Iterator on vertices: " << std::endl; for (auto vertex : tst.complex_vertex_range()) { @@ -170,22 +174,25 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons BOOST_CHECK(simplexTree.num_simplices() == nb_simplices); } -void test_cofaces(typeST& st, std::vector v, int dim, int res) +void test_cofaces(typeST& st, std::vector v, int dim, std::vector> res) { - std::vector cofaces; + std::vector cofaces; if (dim == 0) cofaces = st.star(st.find(v)); else cofaces = st.coface(st.find(v), dim); - BOOST_CHECK(cofaces.size() == (size_t)res); + std::vector currentVertices; for (unsigned long i = 0; i < cofaces.size(); ++i) { - std::cout << "("; - auto j = cofaces[i].begin(); - std::cout << j->first; - for (auto j = cofaces[i].begin() + 1; j != cofaces[i].end(); ++j) - std::cout << "," << j->first; - std::cout << ")" << std::endl; + typeST::Simplex_vertex_range rg = st.simplex_vertex_range(cofaces[i]); + currentVertices.clear(); + for (auto j = rg.begin(); j != rg.end(); ++j) + { + std::cout << "(" << *j << ")"; + currentVertices.push_back(*j); + } + BOOST_CHECK(std::find(res.begin(), res.end(), currentVertices)!=res.end()); + std::cout << std::endl; } } @@ -427,210 +434,247 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) { - Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle)0; - Vertex_handle SECOND_VERTEX_HANDLE = (Vertex_handle) 1; - Vertex_handle THIRD_VERTEX_HANDLE = (Vertex_handle) 2; - Vertex_handle FOURTH_VERTEX_HANDLE = (Vertex_handle) 3; - Vertex_handle FIFTH_VERTEX_HANDLE = (Vertex_handle) 4; - Vertex_handle SIXTH_VERTEX_HANDLE = (Vertex_handle) 5; - Vertex_handle SEVENTH_VERTEX_HANDLE = (Vertex_handle) 6; - Vertex_handle EIGHTH_VERTEX_HANDLE = (Vertex_handle) 7; - - // TEST OF INSERTION - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF INSERTION" << std::endl; - typeST st; - - // ++ FIRST - std::cout << " - INSERT (2,1,0)" << std::endl; - typeVectorVertex SimplexVector1; - SimplexVector1.push_back(THIRD_VERTEX_HANDLE); - SimplexVector1.push_back(SECOND_VERTEX_HANDLE); - SimplexVector1.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector1.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector1 ); - - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // +3 (2, 1 and 0 are not existing) - - // ++ SECOND - std::cout << " - INSERT 3" << std::endl; - typeVectorVertex SimplexVector2; - SimplexVector2.push_back(FOURTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector2.size() == 1 ); - st.insert_simplex_and_subfaces ( SimplexVector2 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // +1 (3 is not existing) - - // ++ THIRD - std::cout << " - INSERT (0,3)" << std::endl; - typeVectorVertex SimplexVector3; - SimplexVector3.push_back(FOURTH_VERTEX_HANDLE); - SimplexVector3.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector3.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector3 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) - - // ++ FOURTH - std::cout << " - INSERT (1,0) (already inserted)" << std::endl; - typeVectorVertex SimplexVector4; - SimplexVector4.push_back(SECOND_VERTEX_HANDLE); - SimplexVector4.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector4.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector4 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) - - // ++ FIFTH - std::cout << " - INSERT (3,4,5)" << std::endl; - typeVectorVertex SimplexVector5; - SimplexVector5.push_back(FOURTH_VERTEX_HANDLE); - SimplexVector5.push_back(FIFTH_VERTEX_HANDLE); - SimplexVector5.push_back(SIXTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector5.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector5 ); - - BOOST_CHECK( st.num_vertices() == (size_t)6 ); - - // ++ SIXTH - std::cout << " - INSERT (0,1,6,7)" << std::endl; - typeVectorVertex SimplexVector6; - SimplexVector6.push_back(FIRST_VERTEX_HANDLE); - SimplexVector6.push_back(SECOND_VERTEX_HANDLE); - SimplexVector6.push_back(SEVENTH_VERTEX_HANDLE); - SimplexVector6.push_back(EIGHTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector6.size() == 4 ); - st.insert_simplex_and_subfaces ( SimplexVector6 ); + Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle)0; + Vertex_handle SECOND_VERTEX_HANDLE = (Vertex_handle) 1; + Vertex_handle THIRD_VERTEX_HANDLE = (Vertex_handle) 2; + Vertex_handle FOURTH_VERTEX_HANDLE = (Vertex_handle) 3; + Vertex_handle FIFTH_VERTEX_HANDLE = (Vertex_handle) 4; + Vertex_handle SIXTH_VERTEX_HANDLE = (Vertex_handle) 5; + Vertex_handle SEVENTH_VERTEX_HANDLE = (Vertex_handle) 6; + Vertex_handle EIGHTH_VERTEX_HANDLE = (Vertex_handle) 7; + + // TEST OF INSERTION + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST OF INSERTION" << std::endl; + typeST st; + + // ++ FIRST + std::cout << " - INSERT (2,1,0)" << std::endl; + typeVectorVertex SimplexVector1; + SimplexVector1.push_back(THIRD_VERTEX_HANDLE); + SimplexVector1.push_back(SECOND_VERTEX_HANDLE); + SimplexVector1.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector1.size() == 3 ); + st.insert_simplex_and_subfaces ( SimplexVector1 ); + + BOOST_CHECK( st.num_vertices() == (size_t)3 ); // +3 (2, 1 and 0 are not existing) + + // ++ SECOND + std::cout << " - INSERT 3" << std::endl; + typeVectorVertex SimplexVector2; + SimplexVector2.push_back(FOURTH_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector2.size() == 1 ); + st.insert_simplex_and_subfaces ( SimplexVector2 ); + + BOOST_CHECK( st.num_vertices() == (size_t)4 ); // +1 (3 is not existing) + + // ++ THIRD + std::cout << " - INSERT (0,3)" << std::endl; + typeVectorVertex SimplexVector3; + SimplexVector3.push_back(FOURTH_VERTEX_HANDLE); + SimplexVector3.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector3.size() == 2 ); + st.insert_simplex_and_subfaces ( SimplexVector3 ); + + BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) + + // ++ FOURTH + std::cout << " - INSERT (1,0) (already inserted)" << std::endl; + typeVectorVertex SimplexVector4; + SimplexVector4.push_back(SECOND_VERTEX_HANDLE); + SimplexVector4.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector4.size() == 2 ); + st.insert_simplex_and_subfaces ( SimplexVector4 ); + + BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) + + // ++ FIFTH + std::cout << " - INSERT (3,4,5)" << std::endl; + typeVectorVertex SimplexVector5; + SimplexVector5.push_back(FOURTH_VERTEX_HANDLE); + SimplexVector5.push_back(FIFTH_VERTEX_HANDLE); + SimplexVector5.push_back(SIXTH_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector5.size() == 3 ); + st.insert_simplex_and_subfaces ( SimplexVector5 ); + + BOOST_CHECK( st.num_vertices() == (size_t)6 ); + + // ++ SIXTH + std::cout << " - INSERT (0,1,6,7)" << std::endl; + typeVectorVertex SimplexVector6; + SimplexVector6.push_back(FIRST_VERTEX_HANDLE); + SimplexVector6.push_back(SECOND_VERTEX_HANDLE); + SimplexVector6.push_back(SEVENTH_VERTEX_HANDLE); + SimplexVector6.push_back(EIGHTH_VERTEX_HANDLE); + BOOST_CHECK( SimplexVector6.size() == 4 ); + st.insert_simplex_and_subfaces ( SimplexVector6 ); + + BOOST_CHECK( st.num_vertices() == (size_t)8 ); // +2 (6 and 7 are not existing - 0 and 1 are already existing) + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + /* */ + /* In other words: */ + /* A facet [2,1,0] */ + /* An edge [0,3] */ + /* A facet [3,4,5] */ + /* A cell [0,1,6,7] */ + + typeSimplex simplexPair1 = std::make_pair(SimplexVector1, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair2 = std::make_pair(SimplexVector2, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair3 = std::make_pair(SimplexVector3, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); + test_simplex_tree_contains(st,simplexPair1,6); // (2,1,0) is in position 6 + test_simplex_tree_contains(st,simplexPair2,7); // (3) is in position 7 + test_simplex_tree_contains(st,simplexPair3,8); // (3,0) is in position 8 + test_simplex_tree_contains(st,simplexPair4,2); // (1,0) is in position 2 + test_simplex_tree_contains(st,simplexPair5,14); // (3,4,5) is in position 14 + test_simplex_tree_contains(st,simplexPair6,26); // (7,6,1,0) is in position 26 + + // ------------------------------------------------------------------------------------------------------------------ + // Find in the simplex_tree + // ------------------------------------------------------------------------------------------------------------------ + typeVectorVertex simpleSimplexVector; + simpleSimplexVector.push_back(SECOND_VERTEX_HANDLE); + Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); + std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); + + Vertex_handle UNKNOWN_VERTEX_HANDLE = (Vertex_handle) 15; + typeVectorVertex unknownSimplexVector; + unknownSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); + simplexFound = st.find(unknownSimplexVector); + std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is NOT found + BOOST_CHECK(simplexFound == st.null_simplex()); + + simplexFound = st.find(SimplexVector6); + std::cout << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); + + typeVectorVertex otherSimplexVector; + otherSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); + otherSimplexVector.push_back(SECOND_VERTEX_HANDLE); + simplexFound = st.find(otherSimplexVector); + std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is NOT found + BOOST_CHECK(simplexFound == st.null_simplex()); + + typeVectorVertex invSimplexVector; + invSimplexVector.push_back(SECOND_VERTEX_HANDLE); + invSimplexVector.push_back(THIRD_VERTEX_HANDLE); + invSimplexVector.push_back(FIRST_VERTEX_HANDLE); + simplexFound = st.find(invSimplexVector); + std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); - BOOST_CHECK( st.num_vertices() == (size_t)8 ); // +2 (6 and 7 are not existing - 0 and 1 are already existing) - /* Inserted simplex: */ - /* 1 6 */ - /* o---o */ - /* /X\7/ */ - /* o---o---o---o */ - /* 2 0 3\X/4 */ - /* o */ - /* 5 */ - /* */ - /* In other words: */ - /* A facet [2,1,0] */ - /* An edge [0,3] */ - /* A facet [3,4,5] */ - /* A cell [0,1,6,7] */ - - typeSimplex simplexPair1 = std::make_pair(SimplexVector1, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair2 = std::make_pair(SimplexVector2, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair3 = std::make_pair(SimplexVector3, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); - test_simplex_tree_contains(st,simplexPair1,6); // (2,1,0) is in position 6 - test_simplex_tree_contains(st,simplexPair2,7); // (3) is in position 7 - test_simplex_tree_contains(st,simplexPair3,8); // (3,0) is in position 8 - test_simplex_tree_contains(st,simplexPair4,2); // (1,0) is in position 2 - test_simplex_tree_contains(st,simplexPair5,14); // (3,4,5) is in position 14 - test_simplex_tree_contains(st,simplexPair6,26); // (7,6,1,0) is in position 26 - - // ------------------------------------------------------------------------------------------------------------------ - // Find in the simplex_tree - // ------------------------------------------------------------------------------------------------------------------ - typeVectorVertex simpleSimplexVector; - simpleSimplexVector.push_back(SECOND_VERTEX_HANDLE); - Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); - std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - Vertex_handle UNKNOWN_VERTEX_HANDLE = (Vertex_handle) 15; - typeVectorVertex unknownSimplexVector; - unknownSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); - simplexFound = st.find(unknownSimplexVector); - std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is NOT found - BOOST_CHECK(simplexFound == st.null_simplex()); - - simplexFound = st.find(SimplexVector6); - std::cout << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - typeVectorVertex otherSimplexVector; - otherSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); - otherSimplexVector.push_back(SECOND_VERTEX_HANDLE); - simplexFound = st.find(otherSimplexVector); - std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is NOT found - BOOST_CHECK(simplexFound == st.null_simplex()); - - typeVectorVertex invSimplexVector; - invSimplexVector.push_back(SECOND_VERTEX_HANDLE); - invSimplexVector.push_back(THIRD_VERTEX_HANDLE); - invSimplexVector.push_back(FIRST_VERTEX_HANDLE); - simplexFound = st.find(invSimplexVector); - std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - // Display the Simplex_tree - Can not be done in the middle of 2 inserts - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for( auto f_simplex : st.filtration_simplex_range() ) - { - std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { - std::cout << (int)vertex << " "; - } - std::cout << std::endl; - } + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for( auto f_simplex : st.filtration_simplex_range() ) + { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for( auto vertex : st.simplex_vertex_range(f_simplex) ) + { + std::cout << (int)vertex << " "; + } + std::cout << std::endl; + } + std::cout << "********************************************************************" << std::endl; // TEST COFACE ALGORITHM st.set_dimension(3); std::cout << "COFACE ALGORITHM" << std::endl; std::vector v; + std::vector> result; v.push_back(3); + std::cout << "First test : " << std::endl; std::cout << "Star of (3):" << std::endl; - test_cofaces(st, v, 0, 4); + int firstCoface[] = {3, 0}; + int secondCoface[] = {4, 3}; + int thirdCoface[] = {5, 4, 3}; + int fourthCoface[] = {5, 3}; + result.push_back(std::vector(firstCoface, firstCoface + 2)); + result.push_back(std::vector(secondCoface, secondCoface + 2)); + result.push_back(std::vector(thirdCoface, thirdCoface + 3)); + result.push_back(std::vector(fourthCoface, fourthCoface + 2)); + test_cofaces(st, v, 0, result); v.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; - test_cofaces(st, v, 0, 3); - std::cout << "Cofaces of (1,7) of dimension 2: " << std::endl; - test_cofaces(st, v, 1, 2); + int firstCoface2[] = {7, 6, 1, 0}; + int secondCoface2[] = {7, 1, 0}; + int thirdCoface2[] = {7 ,6, 1}; + result.push_back(std::vector(firstCoface2, firstCoface2 + 4)); + result.push_back(std::vector(secondCoface2, secondCoface2 + 3)); + result.push_back(std::vector(thirdCoface2, thirdCoface2 + 3)); + test_cofaces(st, v, 0, result); + result.clear(); + + std::cout << "Third test : " << std::endl; + std::cout << "2-dimension Cofaces of simplex(1,7) : " << std::endl; + int secondCoface3[] = {7, 1, 0}; + int firstCoface3[] = {7, 6, 1}; + result.push_back(std::vector(firstCoface3, firstCoface3 + 3)); + result.push_back(std::vector(secondCoface3, secondCoface3 + 3)); + test_cofaces(st, v, 1, result); + result.clear(); + std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension)" << std::endl; - test_cofaces(st, v, 5, 0); + test_cofaces(st, v, 5, result); std::cout << "Cofaces with an empty codimension" << std::endl; - test_cofaces(st, v, -1, 0); + test_cofaces(st, v, -1, result); std::cout << "Cofaces in an empty simplex tree" << std::endl; typeST empty_tree; - test_cofaces(empty_tree, v, 1, 0); + test_cofaces(empty_tree, v, 1, result); std::cout << "Cofaces of an empty simplex" << std::endl; v.clear(); - test_cofaces(st, v, 1, 0); - + test_cofaces(st, v, 1, result); + + /* + // TEST Off read + std::cout << "********************************************************************" << std::endl; + typeST st2; + st2.tree_from_off("test.off"); + std::cout << st2; + */ } -- cgit v1.2.3 From 7a8800cd5b94201cba53458897cad23856e3d3ee Mon Sep 17 00:00:00 2001 From: anmoreau Date: Thu, 18 Jun 2015 08:33:57 +0000 Subject: Fix : name of parameters and functions git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@622 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 15c8419159a268dcb5b8bbfa63fb01adc8851905 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 18 +++++++++--------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 4 ++-- 2 files changed, 11 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 26a8eba6..eb423082 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -627,7 +627,7 @@ private: curr_res->push_back(sib->first); bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension if (egalDim) - cofaces.push_back(find(*curr_res)); + cofaces.push_back(curr_sib->members().find(sib->first)); if (has_children(sib)) rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); curr_res->pop_back(); @@ -640,7 +640,7 @@ private: curr_res->push_back(sib->first); bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension if (vertices.size() == 1 && curr_res->size() > length && egalDim) - cofaces.push_back(find(*curr_res)); + cofaces.push_back(curr_sib->members().find(sib->first)); if (has_children(sib)) { // Rec call Vertex_handle tmp = vertices[vertices.size()-1]; @@ -665,33 +665,33 @@ private: public: /** \brief Compute the star of a n simplex - * \param vertices handles the simplex of which we search the star + * \param simplex handles the simplex of which we search the star * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - std::vector star(const Simplex_handle &vertices) { - return coface(vertices, 0); + std::vector star_simplex_range(const Simplex_handle simplex) { + return cofaces_simplex_range(simplex, 0); } /** \brief Compute the cofaces of a n simplex - * \param vertices handles the n-simplex of which we search the n+codimension cofaces + * \param simplex handles 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. * \warning n+codimension must be lower than Simplex_tree dimension, otherwise an an empty vector is returned. */ - std::vector coface(const Simplex_handle &vertices, int codimension) { + std::vector cofaces_simplex_range(const Simplex_handle simplex, int codimension) { std::vector cofaces; if (dimension_ == -1) // Empty simplex tree return cofaces; - if (vertices == null_simplex()) // Empty simplex + if (simplex == null_simplex()) // Empty simplex return cofaces; if (codimension < 0) // codimension must be positive or null integer return cofaces; std::vector copy; - Simplex_vertex_range rg = simplex_vertex_range(vertices); + Simplex_vertex_range rg = simplex_vertex_range(simplex); for (auto it = rg.begin(); it != rg.end(); ++it) copy.push_back(*it); if (codimension + copy.size() > (unsigned long)(dimension_ + 1) || (codimension == 0 && copy.size() > (unsigned long)dimension_) ) // n+codimension greater than dimension_ diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index eaae4149..f8de1c24 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -178,9 +178,9 @@ void test_cofaces(typeST& st, std::vector v, int dim, std::vector { std::vector cofaces; if (dim == 0) - cofaces = st.star(st.find(v)); + cofaces = st.star_simplex_range(st.find(v)); else - cofaces = st.coface(st.find(v), dim); + cofaces = st.cofaces_simplex_range(st.find(v), dim); std::vector currentVertices; for (unsigned long i = 0; i < cofaces.size(); ++i) { -- cgit v1.2.3 From 9d3c9ae3ccd861c00d113c17da7ec896eece7dac Mon Sep 17 00:00:00 2001 From: anmoreau Date: Fri, 19 Jun 2015 09:47:36 +0000 Subject: multiple fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@627 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 54af67a192141448c344e7bbc59b1e55ff660f30 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 33 ++++++++++++--------------- 1 file changed, 15 insertions(+), 18 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 eb423082..241b692f 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -613,19 +613,18 @@ private: * Postfix actions : Finally, we add back the removed vertex into vertices, and remove this vertex from curr_res so that we didn't change the parameters. * If the vertices list is empty, we need to check if the size of the curr_res list matches with the dimension of the cofaces asked. */ - template - void rec_coface(RandomAccessVertexRange &vertices, Siblings *curr_sib, RandomAccessVertexRange *curr_res, std::vector& cofaces, unsigned int length, unsigned long codimension) + void rec_coface(std::vector &vertices, Siblings *curr_sib, std::vector *curr_res, std::vector& cofaces, int length, long codimension) { - for (auto sib = curr_sib->members().begin(); sib != curr_sib->members().end() && (vertices.empty() || sib->first <= vertices[vertices.size()-1]); ++sib) + for (auto sib = curr_sib->members().begin(); sib != curr_sib->members().end() && (vertices.empty() || sib->first <= vertices.back()); ++sib) { - bool continueRecursion = (codimension == length || curr_res->size() <= codimension); // dimension of actual simplex <= codimension + bool continueRecursion = (codimension == length || (int)curr_res->size() <= codimension); // dimension of actual simplex <= codimension if (vertices.empty()) { - if (curr_res->size() >= length && continueRecursion) + if ((int)curr_res->size() >= length && continueRecursion) // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface { curr_res->push_back(sib->first); - bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension + bool egalDim = (codimension == length || (int)curr_res->size() == codimension); // dimension of actual simplex == codimension if (egalDim) cofaces.push_back(curr_sib->members().find(sib->first)); if (has_children(sib)) @@ -635,22 +634,22 @@ private: } else if (continueRecursion) { - if (sib->first == vertices[vertices.size()-1]) // If curr_sib matches with the top vertex + if (sib->first == vertices.back()) // If curr_sib matches with the top vertex { curr_res->push_back(sib->first); - bool egalDim = (codimension == length || curr_res->size() == codimension); // dimension of actual simplex == codimension - if (vertices.size() == 1 && curr_res->size() > length && egalDim) + bool equalDim = (codimension == length || (int)curr_res->size() == codimension); // dimension of actual simplex == codimension + if (vertices.size() == 1 && (int)curr_res->size() > length && equalDim) cofaces.push_back(curr_sib->members().find(sib->first)); if (has_children(sib)) { // Rec call - Vertex_handle tmp = vertices[vertices.size()-1]; + Vertex_handle tmp = vertices.back(); vertices.pop_back(); rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); vertices.push_back(tmp); } curr_res->pop_back(); } - else // (sib->first < vertices[vertices.size()-1]) + else // (sib->first < vertices.back() { if (has_children(sib)) { @@ -665,7 +664,7 @@ private: public: /** \brief Compute the star of a n simplex - * \param simplex handles the simplex of which we search the star + * \param simplex represent the simplex of which we search the star * \return Vector of Simplex_handle, empty vector if no cofaces found. */ @@ -676,7 +675,7 @@ public: /** \brief Compute the cofaces of a n simplex - * \param simplex handles the n-simplex of which we search the n+codimension cofaces + * \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. * \warning n+codimension must be lower than Simplex_tree dimension, otherwise an an empty vector is returned. @@ -690,15 +689,13 @@ public: return cofaces; if (codimension < 0) // codimension must be positive or null integer return cofaces; - std::vector copy; Simplex_vertex_range rg = simplex_vertex_range(simplex); - for (auto it = rg.begin(); it != rg.end(); ++it) - copy.push_back(*it); - if (codimension + copy.size() > (unsigned long)(dimension_ + 1) || (codimension == 0 && copy.size() > (unsigned long)dimension_) ) // n+codimension greater than dimension_ + std::vector copy(rg.begin(), rg.end()); + if (codimension + (int)copy.size() > dimension_ + 1 || (codimension == 0 && (int)copy.size() > dimension_) ) // n+codimension greater than dimension_ return cofaces; std::sort(copy.begin(), copy.end(), std::greater()); // must be sorted in decreasing order std::vector res; - rec_coface(copy, &root_, &res, cofaces, copy.size(), codimension + copy.size()); + rec_coface(copy, &root_, &res, cofaces, (int)copy.size(), codimension + (int)copy.size()); return cofaces; } -- cgit v1.2.3 From 4eb1939d74050c9193daecba2f69471b915180b2 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 23 Jun 2015 15:01:05 +0000 Subject: multiple fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@634 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0bcb4f121da2714128c3ae8ab0da2000e815d339 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 109 ++++++++++++---------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 114 +++++++++++++++-------- 2 files changed, 134 insertions(+), 89 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 241b692f..a355c334 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -156,6 +156,12 @@ 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. */ + /** \brief Iterator over the cofaces of a simplex. + * + * 'value_type' is Vertex_handle. */ + typedef typename std::vector::iterator Coface_simplex_iterator; + typedef boost::iterator_range Coface_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -187,8 +193,7 @@ 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( @@ -206,6 +211,7 @@ class Simplex_tree { Complex_simplex_iterator()); } + /** \brief Returns a range over the simplices of the dim-skeleton of the simplicial complex. * * The \f$d\f$-skeleton of a simplicial complex \f$\mathbf{K}\f$ is the simplicial complex containing the @@ -252,10 +258,12 @@ 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 (simplex != null_simplex()); // Empty simplex return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } + /** \brief Returns a range over the simplices of the boundary of a simplex. * * The boundary of a simplex is the set of codimension \f$1\f$ subsimplices of the simplex. @@ -386,6 +394,12 @@ class Simplex_tree { 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(Dit_value_t 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 @@ -607,55 +621,57 @@ private: *\param vertices contains a list of vertices, which represent the simplex. *\param curr_res contains a list of vertices, which represent the current path in the tree. *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. - *\param length length of the vertices list + *\param length length of the vertex list "vertices" * 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_res so that we didn't change the parameters. * If the vertices list is empty, we need to check if the size of the curr_res list matches with the dimension of the cofaces asked. */ - void rec_coface(std::vector &vertices, Siblings *curr_sib, std::vector *curr_res, std::vector& cofaces, int length, long codimension) + void rec_coface(std::vector &vertices, Siblings *curr_sib, std::vector &curr_res, std::vector& cofaces, int length, int nbVertices) { - for (auto sib = curr_sib->members().begin(); sib != curr_sib->members().end() && (vertices.empty() || sib->first <= vertices.back()); ++sib) + if (!(nbVertices == length || (int)curr_res.size() <= nbVertices)) // dimension of actual simplex <= nbVertices + return; +// for (auto simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) + for (auto& simplex : curr_sib->members()) { - bool continueRecursion = (codimension == length || (int)curr_res->size() <= codimension); // dimension of actual simplex <= codimension if (vertices.empty()) + { + // if ((int)curr_res.size() >= length && continueRecursion) + // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface + curr_res.push_back(simplex.first); + bool equalDim = (nbVertices == length || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices + if (equalDim) + cofaces.push_back(curr_sib->members().find(simplex.first)); + if (has_children(simplex)) + rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); + curr_res.pop_back(); + } + else { - if ((int)curr_res->size() >= length && continueRecursion) - // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface + if (simplex.first == vertices.back()) // If curr_sib matches with the top vertex { - curr_res->push_back(sib->first); - bool egalDim = (codimension == length || (int)curr_res->size() == codimension); // dimension of actual simplex == codimension - if (egalDim) - cofaces.push_back(curr_sib->members().find(sib->first)); - if (has_children(sib)) - rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); - curr_res->pop_back(); - } - } - else if (continueRecursion) - { - if (sib->first == vertices.back()) // If curr_sib matches with the top vertex - { - curr_res->push_back(sib->first); - bool equalDim = (codimension == length || (int)curr_res->size() == codimension); // dimension of actual simplex == codimension - if (vertices.size() == 1 && (int)curr_res->size() > length && equalDim) - cofaces.push_back(curr_sib->members().find(sib->first)); - if (has_children(sib)) + curr_res.push_back(simplex.first); + bool equalDim = (nbVertices == length || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices + if (vertices.size() == 1 && (int)curr_res.size() > length && equalDim) + cofaces.push_back(curr_sib->members().find(simplex.first)); + if (has_children(simplex)) { // Rec call Vertex_handle tmp = vertices.back(); vertices.pop_back(); - rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); + rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); vertices.push_back(tmp); } - curr_res->pop_back(); + curr_res.pop_back(); } - else // (sib->first < vertices.back() + else if (simplex.first > vertices.back()) + return; + else // (simplex.first < vertices.back() { - if (has_children(sib)) + if (has_children(simplex)) { - curr_res->push_back(sib->first); - rec_coface(vertices, sib->second.children(), curr_res, cofaces, length, codimension); - curr_res->pop_back(); + curr_res.push_back(simplex.first); + rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); + curr_res.pop_back(); } } } @@ -668,8 +684,8 @@ public: * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - std::vector star_simplex_range(const Simplex_handle simplex) { - return cofaces_simplex_range(simplex, 0); + Coface_simplex_range star_simplex_range(const Simplex_handle simplex) { + return coface_simplex_range(simplex, 0); } @@ -678,27 +694,24 @@ public: * \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. - * \warning n+codimension must be lower than Simplex_tree dimension, otherwise an an empty vector is returned. */ - std::vector cofaces_simplex_range(const Simplex_handle simplex, int codimension) { + Coface_simplex_range coface_simplex_range(const Simplex_handle simplex, int codimension) { std::vector cofaces; - if (dimension_ == -1) // Empty simplex tree - return cofaces; - if (simplex == null_simplex()) // Empty simplex - return cofaces; - if (codimension < 0) // codimension must be positive or null integer - return cofaces; + assert (simplex != null_simplex()); // Empty simplex + assert (codimension >= 0); // codimension must be positive or null integer Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector copy(rg.begin(), rg.end()); if (codimension + (int)copy.size() > dimension_ + 1 || (codimension == 0 && (int)copy.size() > dimension_) ) // n+codimension greater than dimension_ - return cofaces; - std::sort(copy.begin(), copy.end(), std::greater()); // must be sorted in decreasing order + return Coface_simplex_range(cofaces.begin(), cofaces.end()); + assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); // must be sorted in decreasing order std::vector res; - rec_coface(copy, &root_, &res, cofaces, (int)copy.size(), codimension + (int)copy.size()); - return cofaces; + rec_coface(copy, &root_, res, cofaces, (int)copy.size(), codimension + (int)copy.size()); + return Coface_simplex_range(cofaces.begin(), cofaces.end()); } - + + + private: /** \brief Returns true iff the list of vertices of sh1 diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index f8de1c24..344cb009 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -174,25 +174,20 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons BOOST_CHECK(simplexTree.num_simplices() == nb_simplices); } -void test_cofaces(typeST& st, std::vector v, int dim, std::vector> res) -{ - std::vector cofaces; +void test_cofaces(typeST& st, std::vector v, int dim, std::vector res) { + typeST::Coface_simplex_range cofaces; if (dim == 0) cofaces = st.star_simplex_range(st.find(v)); else - cofaces = st.cofaces_simplex_range(st.find(v), dim); - std::vector currentVertices; - for (unsigned long i = 0; i < cofaces.size(); ++i) + cofaces = st.coface_simplex_range(st.find(v), dim); + for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) { - typeST::Simplex_vertex_range rg = st.simplex_vertex_range(cofaces[i]); - currentVertices.clear(); - for (auto j = rg.begin(); j != rg.end(); ++j) - { - std::cout << "(" << *j << ")"; - currentVertices.push_back(*j); + typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); + for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { + std::cout << "(" << *vertex << ")" ; } - BOOST_CHECK(std::find(res.begin(), res.end(), currentVertices)!=res.end()); std::cout << std::endl; + BOOST_CHECK(std::find(res.begin(), res.end(), *simplex)!=res.end()); } } @@ -620,18 +615,32 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) st.set_dimension(3); std::cout << "COFACE ALGORITHM" << std::endl; std::vector v; - std::vector> result; + std::vector simplex; + std::vector result; v.push_back(3); std::cout << "First test : " << std::endl; std::cout << "Star of (3):" << std::endl; - int firstCoface[] = {3, 0}; - int secondCoface[] = {4, 3}; - int thirdCoface[] = {5, 4, 3}; - int fourthCoface[] = {5, 3}; - result.push_back(std::vector(firstCoface, firstCoface + 2)); - result.push_back(std::vector(secondCoface, secondCoface + 2)); - result.push_back(std::vector(thirdCoface, thirdCoface + 3)); - result.push_back(std::vector(fourthCoface, fourthCoface + 2)); + 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(); result.clear(); @@ -640,34 +649,57 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) v.push_back(7); std::cout << "Second test : " << std::endl; std::cout << "Star of (1,7): " << std::endl; - int firstCoface2[] = {7, 6, 1, 0}; - int secondCoface2[] = {7, 1, 0}; - int thirdCoface2[] = {7 ,6, 1}; - result.push_back(std::vector(firstCoface2, firstCoface2 + 4)); - result.push_back(std::vector(secondCoface2, secondCoface2 + 3)); - result.push_back(std::vector(thirdCoface2, thirdCoface2 + 3)); + + 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); result.clear(); std::cout << "Third test : " << std::endl; std::cout << "2-dimension Cofaces of simplex(1,7) : " << std::endl; - int secondCoface3[] = {7, 1, 0}; - int firstCoface3[] = {7, 6, 1}; - result.push_back(std::vector(firstCoface3, firstCoface3 + 3)); - result.push_back(std::vector(secondCoface3, secondCoface3 + 3)); + + 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, 1, result); result.clear(); - std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension)" << std::endl; + 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); - 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 << "Cofaces with an empty codimension" << std::endl; +// test_cofaces(st, v, -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); /* // TEST Off read -- cgit v1.2.3 From 39dbac0617b4a542f47225a9dcf6f088a12be5be Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 23 Jun 2015 15:17:53 +0000 Subject: multiple fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@636 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 36023554707626e7c66d52777f4d4b9245e95317 --- src/Simplex_tree/include/gudhi/Simplex_tree.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.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index a355c334..ad9f7dd7 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -258,7 +258,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 (simplex != null_simplex()); // Empty simplex + assert (sh != null_simplex()); // Empty simplex return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -698,7 +698,6 @@ public: Coface_simplex_range coface_simplex_range(const Simplex_handle simplex, int codimension) { std::vector cofaces; - assert (simplex != null_simplex()); // Empty simplex assert (codimension >= 0); // codimension must be positive or null integer Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector copy(rg.begin(), rg.end()); -- cgit v1.2.3 From a602092b3437afb3271196f21dea4f4e944436c3 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Wed, 24 Jun 2015 08:49:50 +0000 Subject: Multiple fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@637 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d44b4ced5406c0b8ab305ec752077f9b5c242d4d --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 16 ++++++---------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 2 +- 2 files changed, 7 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 ad9f7dd7..4dee1432 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -157,11 +157,7 @@ class Simplex_tree { /** \brief Range over the vertices of a simplex. */ typedef boost::iterator_range Simplex_vertex_range; /** \brief Range over the cofaces of a simplex. */ - /** \brief Iterator over the cofaces of a simplex. - * - * 'value_type' is Vertex_handle. */ - typedef typename std::vector::iterator Coface_simplex_iterator; - typedef boost::iterator_range Coface_simplex_range; + typedef std::vector Coface_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -397,7 +393,7 @@ class Simplex_tree { /** \brief Returns true iff the node in the simplex tree pointed by * sh has children.*/ - bool has_children(Dit_value_t sh) { + bool has_children(Dit_value_t & sh) { return (sh.second.children()->parent() == sh.first); } @@ -685,7 +681,7 @@ public: */ Coface_simplex_range star_simplex_range(const Simplex_handle simplex) { - return coface_simplex_range(simplex, 0); + return cofaces_simplex_range(simplex, 0); } @@ -696,8 +692,8 @@ public: * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - Coface_simplex_range coface_simplex_range(const Simplex_handle simplex, int codimension) { - std::vector cofaces; + Coface_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) { + Coface_simplex_range cofaces; assert (codimension >= 0); // codimension must be positive or null integer Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector copy(rg.begin(), rg.end()); @@ -706,7 +702,7 @@ public: assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); // must be sorted in decreasing order std::vector res; rec_coface(copy, &root_, res, cofaces, (int)copy.size(), codimension + (int)copy.size()); - return Coface_simplex_range(cofaces.begin(), cofaces.end()); + return cofaces; } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 344cb009..968a67b3 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -179,7 +179,7 @@ void test_cofaces(typeST& st, std::vector v, int dim, std::vector if (dim == 0) cofaces = st.star_simplex_range(st.find(v)); else - cofaces = st.coface_simplex_range(st.find(v), dim); + 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); -- cgit v1.2.3 From 07faa8ef38b4ffe8c9e8e5e4e70717ff2500e08f Mon Sep 17 00:00:00 2001 From: anmoreau Date: Thu, 25 Jun 2015 11:39:49 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@650 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: ad75901b33f5037cbb8234b5179cea436a46b23b --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 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 4dee1432..47a96303 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -625,20 +625,19 @@ private: */ void rec_coface(std::vector &vertices, Siblings *curr_sib, std::vector &curr_res, std::vector& cofaces, int length, int nbVertices) { - if (!(nbVertices == length || (int)curr_res.size() <= nbVertices)) // dimension of actual simplex <= nbVertices + bool star = nbVertices == length; + if (!(star || (int)curr_res.size() <= nbVertices)) // dimension of actual simplex <= nbVertices return; -// for (auto simplex = curr_sib->members().begin(); simplex != curr_sib->members().end(); ++simplex) for (auto& simplex : curr_sib->members()) { if (vertices.empty()) { - // if ((int)curr_res.size() >= length && continueRecursion) // If we reached the end of the vertices, and the simplex has more vertices than the given simplex, we found a coface curr_res.push_back(simplex.first); - bool equalDim = (nbVertices == length || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices - if (equalDim) + bool addCoface = (star || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices + if (addCoface) cofaces.push_back(curr_sib->members().find(simplex.first)); - if (has_children(simplex)) + if ((!addCoface || star) && has_children(simplex)) // Rec call rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); curr_res.pop_back(); } @@ -648,10 +647,11 @@ private: { curr_res.push_back(simplex.first); bool equalDim = (nbVertices == length || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices - if (vertices.size() == 1 && (int)curr_res.size() > length && equalDim) + bool addCoface = vertices.size() == 1 && (int)curr_res.size() > length && equalDim; + if (addCoface) cofaces.push_back(curr_sib->members().find(simplex.first)); - if (has_children(simplex)) - { // Rec call + if ((!addCoface || star) && has_children(simplex)) + { // Rec call Vertex_handle tmp = vertices.back(); vertices.pop_back(); rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); -- cgit v1.2.3 From 5a9dee66373ff67ef1f3ecc13f57e3ce449ba921 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 30 Jun 2015 17:11:21 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@670 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 37d77e33cbff77414eea51e4ff91c865f6707850 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 44 +++++++++++++----------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 2 +- 2 files changed, 24 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 47a96303..b9723c04 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -157,7 +157,7 @@ class Simplex_tree { /** \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 Coface_simplex_range; + typedef std::vector Cofaces_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -391,12 +391,15 @@ class Simplex_tree { return (sh->second.children()->parent() == sh->first); } + private: /** \brief Returns true iff the node in the simplex tree pointed by * sh has children.*/ bool has_children(Dit_value_t & sh) { return (sh.second.children()->parent() == sh.first); } + public: + /** \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. @@ -614,40 +617,40 @@ private: /** Recursive search of cofaces * This function uses DFS - *\param vertices contains a list of vertices, which represent the simplex. - *\param curr_res contains a list of vertices, which represent the current path in the tree. + *\param vertices contains a list of vertices, which represent the vertices of the simplex not found yet. + *\param curr_res represents the number of vertices of the simplex found. *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. - *\param length length of the vertex list "vertices" + *\param length number of vertices in the Simplex_handle of which we search the cofaces. * 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_res so that we didn't change the parameters. * If the vertices list is empty, we need to check if the size of the curr_res list matches with the dimension of the cofaces asked. */ - void rec_coface(std::vector &vertices, Siblings *curr_sib, std::vector &curr_res, std::vector& cofaces, int length, int nbVertices) + void rec_coface(std::vector &vertices, Siblings *curr_sib, int curr_res, std::vector& cofaces, int length, int nbVertices) { bool star = nbVertices == length; - if (!(star || (int)curr_res.size() <= nbVertices)) // dimension of actual simplex <= nbVertices + if (!(star || curr_res <= nbVertices)) // dimension of actual simplex <= nbVertices return; for (auto& simplex : curr_sib->members()) { 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 - curr_res.push_back(simplex.first); - bool addCoface = (star || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices + curr_res++; + bool addCoface = (star || curr_res == nbVertices); // dimension of actual simplex == nbVertices if (addCoface) cofaces.push_back(curr_sib->members().find(simplex.first)); if ((!addCoface || star) && has_children(simplex)) // Rec call rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); - curr_res.pop_back(); + curr_res--; } else { if (simplex.first == vertices.back()) // If curr_sib matches with the top vertex { - curr_res.push_back(simplex.first); - bool equalDim = (nbVertices == length || (int)curr_res.size() == nbVertices); // dimension of actual simplex == nbVertices - bool addCoface = vertices.size() == 1 && (int)curr_res.size() > length && equalDim; + curr_res++; + bool equalDim = (nbVertices == length || curr_res == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = vertices.size() == 1 && curr_res > length && equalDim; if (addCoface) cofaces.push_back(curr_sib->members().find(simplex.first)); if ((!addCoface || star) && has_children(simplex)) @@ -657,7 +660,7 @@ private: rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); vertices.push_back(tmp); } - curr_res.pop_back(); + curr_res--; } else if (simplex.first > vertices.back()) return; @@ -665,9 +668,9 @@ private: { if (has_children(simplex)) { - curr_res.push_back(simplex.first); + curr_res++; rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); - curr_res.pop_back(); + curr_res--; } } } @@ -680,7 +683,7 @@ public: * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - Coface_simplex_range star_simplex_range(const Simplex_handle simplex) { + Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) { return cofaces_simplex_range(simplex, 0); } @@ -692,16 +695,15 @@ public: * \return Vector of Simplex_handle, empty vector if no cofaces found. */ - Coface_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) { - Coface_simplex_range cofaces; + Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) { + Cofaces_simplex_range cofaces; assert (codimension >= 0); // codimension must be positive or null integer Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector copy(rg.begin(), rg.end()); if (codimension + (int)copy.size() > dimension_ + 1 || (codimension == 0 && (int)copy.size() > dimension_) ) // n+codimension greater than dimension_ - return Coface_simplex_range(cofaces.begin(), cofaces.end()); + return cofaces; assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); // must be sorted in decreasing order - std::vector res; - rec_coface(copy, &root_, res, cofaces, (int)copy.size(), codimension + (int)copy.size()); + rec_coface(copy, &root_, 0, cofaces, (int)copy.size(), codimension + (int)copy.size()); return cofaces; } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 968a67b3..a6328663 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -175,7 +175,7 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons } void test_cofaces(typeST& st, std::vector v, int dim, std::vector res) { - typeST::Coface_simplex_range cofaces; + typeST::Cofaces_simplex_range cofaces; if (dim == 0) cofaces = st.star_simplex_range(st.find(v)); else -- cgit v1.2.3 From 6930f8cebfbea8678603bc55e4eea293d2e3e902 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 6 Jul 2015 15:19:18 +0000 Subject: Fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@682 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: e9d8b582ff8b566596daea71760f683443e8a329 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 34 ++++++++++----------------- 1 file changed, 13 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 b9723c04..cb189d76 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -391,13 +391,6 @@ class Simplex_tree { return (sh->second.children()->parent() == sh->first); } - private: - /** \brief Returns true iff the node in the simplex tree pointed by - * sh has children.*/ - bool has_children(Dit_value_t & sh) { - return (sh.second.children()->parent() == sh.first); - } - public: /** \brief Given a range of Vertex_handles, returns the Simplex_handle @@ -621,55 +614,54 @@ private: *\param curr_res represents the number of vertices of the simplex found. *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. *\param length number of vertices in the Simplex_handle of which we search the cofaces. + *\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_res so that we didn't change the parameters. - * If the vertices list is empty, we need to check if the size of the curr_res list matches with the dimension of the cofaces asked. + * If the vertices list is empty, we need to check if curr_res matches with the dimension of the cofaces asked. */ void rec_coface(std::vector &vertices, Siblings *curr_sib, int curr_res, std::vector& cofaces, int length, int nbVertices) { bool star = nbVertices == length; if (!(star || curr_res <= nbVertices)) // dimension of actual simplex <= nbVertices return; - for (auto& simplex : curr_sib->members()) + curr_res++; + 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 - curr_res++; bool addCoface = (star || curr_res == nbVertices); // dimension of actual simplex == nbVertices if (addCoface) - cofaces.push_back(curr_sib->members().find(simplex.first)); + cofaces.push_back(simplex); if ((!addCoface || star) && has_children(simplex)) // Rec call - rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_res, cofaces, length, nbVertices); curr_res--; } else { - if (simplex.first == vertices.back()) // If curr_sib matches with the top vertex + if (simplex->first == vertices.back()) // If curr_sib matches with the top vertex { - curr_res++; - bool equalDim = (nbVertices == length || curr_res == nbVertices); // dimension of actual simplex == nbVertices + bool equalDim = (star || curr_res == nbVertices); // dimension of actual simplex == nbVertices bool addCoface = vertices.size() == 1 && curr_res > length && equalDim; if (addCoface) - cofaces.push_back(curr_sib->members().find(simplex.first)); + 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_res, cofaces, length, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_res, cofaces, length, nbVertices); vertices.push_back(tmp); } curr_res--; } - else if (simplex.first > vertices.back()) + else if (simplex->first > vertices.back()) return; - else // (simplex.first < vertices.back() + else // (simplex->first < vertices.back() { if (has_children(simplex)) { - curr_res++; - rec_coface(vertices, simplex.second.children(), curr_res, cofaces, length, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_res, cofaces, length, nbVertices); curr_res--; } } -- cgit v1.2.3 From 51192ba9c5991a4d232417dd49ce15a14b400599 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Mon, 6 Jul 2015 15:22:36 +0000 Subject: Fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@683 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c15bed57474202a9bf05aabc7eb33ac1b3c32a41 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 30 +++++++++++++-------------- 1 file changed, 15 insertions(+), 15 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 cb189d76..f2b726f9 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -611,49 +611,49 @@ 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_res represents the number of vertices of the simplex found. + *\param curr_nbVertices represents the number of vertices of the simplex found. *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. *\param length number of vertices in the Simplex_handle of which we search the cofaces. *\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_res so that we didn't change the parameters. - * If the vertices list is empty, we need to check if curr_res matches with the dimension of the cofaces asked. + * 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_res, std::vector& cofaces, int length, int nbVertices) + void rec_coface(std::vector &vertices, Siblings *curr_sib, int curr_nbVertices, std::vector& cofaces, int length, int nbVertices) { bool star = nbVertices == length; - if (!(star || curr_res <= nbVertices)) // dimension of actual simplex <= nbVertices + if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices return; - curr_res++; + curr_nbVertices++; 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 - bool addCoface = (star || curr_res == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices if (addCoface) cofaces.push_back(simplex); if ((!addCoface || star) && has_children(simplex)) // Rec call - rec_coface(vertices, simplex->second.children(), curr_res, cofaces, length, nbVertices); - curr_res--; + rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); + curr_nbVertices--; } else { if (simplex->first == vertices.back()) // If curr_sib matches with the top vertex { - bool equalDim = (star || curr_res == nbVertices); // dimension of actual simplex == nbVertices - bool addCoface = vertices.size() == 1 && curr_res > length && equalDim; + bool equalDim = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = vertices.size() == 1 && curr_nbVertices > length && 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_res, cofaces, length, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); vertices.push_back(tmp); } - curr_res--; + curr_nbVertices--; } else if (simplex->first > vertices.back()) return; @@ -661,8 +661,8 @@ private: { if (has_children(simplex)) { - rec_coface(vertices, simplex->second.children(), curr_res, cofaces, length, nbVertices); - curr_res--; + rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); + curr_nbVertices--; } } } -- cgit v1.2.3 From 505a0c3159b1c1a74884b8e28d9eb18aafa57cca Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 7 Jul 2015 10:05:01 +0000 Subject: Fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@687 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 537ff69dd4c762a196c80d051995c3a4145f7c99 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 28 +++++++++--------------- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 10 +++++++++ 2 files changed, 20 insertions(+), 18 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 f2b726f9..f5add449 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -613,58 +613,49 @@ private: *\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 found. *\param cofaces contains a list of Simplex_handle, representing all the cofaces asked. - *\param length number of vertices in the Simplex_handle of which we search the cofaces. + *\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, int length, int nbVertices) + void rec_coface(std::vector &vertices, Siblings *curr_sib, int curr_nbVertices, std::vector& cofaces, bool star, int nbVertices) { - bool star = nbVertices == length; if (!(star || curr_nbVertices <= nbVertices)) // dimension of actual simplex <= nbVertices return; - curr_nbVertices++; 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 - bool addCoface = (star || curr_nbVertices == nbVertices); // dimension of actual simplex == nbVertices + bool addCoface = (star || curr_nbVertices == nbVertices); // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices if (addCoface) cofaces.push_back(simplex); if ((!addCoface || star) && has_children(simplex)) // Rec call - rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); - curr_nbVertices--; + 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 && curr_nbVertices > length && equalDim; + bool addCoface = vertices.size() == 1 && equalDim; if (addCoface) cofaces.push_back(simplex); - if ((!addCoface || star) && has_children(simplex)) + if ((!addCoface || star) && has_children(simplex)) // Rec call { // Rec call Vertex_handle tmp = vertices.back(); vertices.pop_back(); - rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); vertices.push_back(tmp); } - curr_nbVertices--; } else if (simplex->first > vertices.back()) return; else // (simplex->first < vertices.back() - { if (has_children(simplex)) - { - rec_coface(vertices, simplex->second.children(), curr_nbVertices, cofaces, length, nbVertices); - curr_nbVertices--; - } - } + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); } } } @@ -695,7 +686,8 @@ public: if (codimension + (int)copy.size() > dimension_ + 1 || (codimension == 0 && (int)copy.size() > dimension_) ) // n+codimension greater than dimension_ return cofaces; assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); // must be sorted in decreasing order - rec_coface(copy, &root_, 0, cofaces, (int)copy.size(), codimension + (int)copy.size()); + bool star = codimension == 0; + rec_coface(copy, &root_, 1, cofaces, star, codimension + (int)copy.size()); return cofaces; } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index a6328663..55a055a0 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -620,6 +620,11 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) 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)); @@ -650,6 +655,11 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) 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); -- cgit v1.2.3 From 41ac7d00bac4c1cead095354dc2e8032855d3730 Mon Sep 17 00:00:00 2001 From: anmoreau Date: Tue, 7 Jul 2015 12:51:31 +0000 Subject: fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@690 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c321cdfd965487fb41801f4456838637512d0c2d --- 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 0c2c851a..75471e3a 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -189,7 +189,7 @@ 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( -- cgit v1.2.3 From 7302345da9d33699b2478ded8ee3f0f9bfa3e715 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 7 Jul 2015 14:17:48 +0000 Subject: Fix ident + cpplint git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@691 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: f282adfdec4429e426a46be9f83d149c69892ec5 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 329 +++++----- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 800 +++++++++++------------ 2 files changed, 561 insertions(+), 568 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 75471e3a..2507f783 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -35,9 +35,10 @@ #include #include #include +#include // for greater<> namespace Gudhi { - + /** \defgroup simplex_tree Filtered Complexes * * A simplicial complex \f$\mathbf{K}\f$ @@ -72,6 +73,7 @@ namespace Gudhi { * \copyright GNU General Public License v3. * @{ */ + /** * \brief Simplex Tree data structure for representing simplicial complexes. * @@ -84,8 +86,8 @@ namespace Gudhi { * */ template class Simplex_tree { @@ -130,6 +132,7 @@ class Simplex_tree { typedef typename Dictionary_it::value_type Dit_value_t; struct return_first { + Vertex_handle operator()(const Dit_value_t& p_sh) const { return p_sh.first; } @@ -185,7 +188,7 @@ class Simplex_tree { /** \brief Range over the simplices of the simplicial complex, ordered by the filtration. */ typedef boost::iterator_range Filtration_simplex_range; - /* @} */ // end name range and iterator types + /* @} */ // end name range and iterator types /** \name Range and iterator methods * @{ */ @@ -193,8 +196,8 @@ class Simplex_tree { * 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. @@ -207,7 +210,6 @@ class Simplex_tree { Complex_simplex_iterator()); } - /** \brief Returns a range over the simplices of the dim-skeleton of the simplicial complex. * * The \f$d\f$-skeleton of a simplicial complex \f$\mathbf{K}\f$ is the simplicial complex containing the @@ -247,6 +249,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, @@ -254,12 +257,11 @@ 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 + assert(sh != null_simplex()); // Empty simplex return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } - /** \brief Returns a range over the simplices of the boundary of a simplex. * * The boundary of a simplex is the set of codimension \f$1\f$ subsimplices of the simplex. @@ -279,19 +281,18 @@ class Simplex_tree { Boundary_simplex_iterator(this)); } - /** @} */ // end range and iterator methods + /** @} */ // end range and iterator methods /** \name Constructor/Destructor * @{ */ /** \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 Destructor; deallocates the whole tree structure. */ ~Simplex_tree() { @@ -301,7 +302,7 @@ class Simplex_tree { } } } - /** @} */ // end constructor/destructor + /** @} */ // end constructor/destructor private: /** Recursive deletion. */ void rec_delete(Siblings * sib) { @@ -320,12 +321,14 @@ class Simplex_tree { 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) { return filtration_vect_[key]; } + /** \brief Returns the filtration value of a simplex. * * Called on the null_simplex, returns INFINITY. */ @@ -334,12 +337,14 @@ class Simplex_tree { return sh->second.filtration(); } else { return INFINITY; - } // filtration(); } + } // filtration(); } } + /** \brief Returns an upper bound of the filtration values of the simplices. */ Filtration_value filtration() const { return threshold_; } + /** \brief Returns a Simplex_handle different from all Simplex_handles * associated to the simplices in the simplicial complex. * @@ -347,20 +352,24 @@ class Simplex_tree { Simplex_handle null_simplex() const { return Dictionary_it(NULL); } + /** \brief Returns a key different for all keys associated to the * simplices of the simplicial complex. */ Simplex_key null_key() const { 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. */ @@ -380,6 +389,7 @@ class Simplex_tree { } return dim - 1; } + /** \brief Returns an upper bound on the dimension of the simplicial complex. */ int dimension() const { return dimension_; @@ -390,9 +400,8 @@ class Simplex_tree { bool has_children(Simplex_handle sh) const { return (sh->second.children()->parent() == sh->first); } - - public: + public: /** \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. @@ -404,7 +413,7 @@ class Simplex_tree { template Simplex_handle find(RandomAccessVertexRange & s) { if (s.begin() == s.end()) // Empty simplex - return null_simplex(); + return null_simplex(); sort(s.begin(), s.end()); @@ -429,7 +438,7 @@ class Simplex_tree { Simplex_handle find_vertex(Vertex_handle v) { return root_.members_.begin() + v; } -//{ return root_.members_.find(v); } + //{ return root_.members_.find(v); } /** \brief Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex. * @@ -456,12 +465,12 @@ 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) { if (simplex.empty()) { return std::pair(null_simplex(), true); } - sort(simplex.begin(), simplex.end()); // must be sorted in increasing order + sort(simplex.begin(), simplex.end()); // must be sorted in increasing order Siblings * curr_sib = &root_; std::pair res_insert; @@ -474,34 +483,33 @@ class Simplex_tree { 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 + return std::pair(null_simplex(), false); // if filtration value unchanged } // otherwise the insertion has succeeded return res_insert; } - /** \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. - */ + */ template void insert_simplex_and_subfaces(RandomAccessVertexRange& Nsimplex, - Filtration_value filtration = 0.0) { + 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()]); + NsimplexMinusOne.push_back(Nsimplex[(NIndex + NListIter) % Nsimplex.size()]); } // (N-1)-Simplex recursive call insert_simplex_and_subfaces(NsimplexMinusOne, filtration); @@ -534,8 +542,8 @@ class Simplex_tree { * 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())); + root_.members_.find(sh->first), + root_.members_.find(self_siblings(sh)->parent())); } /** Returns the Siblings containing a simplex.*/ @@ -546,12 +554,12 @@ class Simplex_tree { 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 << " ";} @@ -563,15 +571,16 @@ class Simplex_tree { 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(unsigned int num_simplices) { num_simplices_ = num_simplices; } + /** Set a dimension for the simplicial complex. */ void set_dimension(int dimension) { dimension_ = dimension; @@ -597,7 +606,7 @@ class Simplex_tree { filtration_vect_.clear(); filtration_vect_.reserve(num_simplices()); for (auto cpx_it = complex_simplex_range().begin(); - cpx_it != complex_simplex_range().end(); ++cpx_it) { + cpx_it != complex_simplex_range().end(); ++cpx_it) { filtration_vect_.push_back(*cpx_it); } @@ -605,94 +614,86 @@ class Simplex_tree { std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); } - -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) + + 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 + bool addCoface = (star || curr_nbVertices == nbVertices); // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with 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 { - 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 - bool addCoface = (star || curr_nbVertices == nbVertices); // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with 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 - { // 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); - } - } + 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 + { // 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; - assert (codimension >= 0); // codimension must be positive or null integer - Simplex_vertex_range rg = simplex_vertex_range(simplex); - std::vector copy(rg.begin(), rg.end()); - if (codimension + (int)copy.size() > dimension_ + 1 || (codimension == 0 && (int)copy.size() > dimension_) ) // n+codimension greater than dimension_ - return cofaces; - assert(std::is_sorted(copy.begin(), copy.end(), std::greater())); // must be sorted in decreasing order - bool star = codimension == 0; - rec_coface(copy, &root_, 1, cofaces, star, codimension + (int)copy.size()); - return cofaces; - } + 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 @@ -717,6 +718,7 @@ public: } return ((it1 == rg1.end()) && (it2 != rg2.end())); } + /** \brief StrictWeakOrdering, for the simplices, defined by the filtration. * * It corresponds to the partial order @@ -724,16 +726,16 @@ public: * Reverse lexicographic order has the property to always consider the subsimplex of a simplex * 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 + return st_->reverse_lexicographic_order(sh1, sh2); // is sh1 a proper subface of sh2 } Simplex_tree * st_; @@ -760,7 +762,7 @@ public: * must be undirected_tag. */ template void insert_graph(const OneSkeletonGraph& skel_graph) { - assert(num_simplices() == 0); // the simplex tree must be empty + assert(num_simplices() == 0); // the simplex tree must be empty if (boost::num_vertices(skel_graph) == 0) { return; @@ -778,30 +780,31 @@ public: 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. * @@ -816,7 +819,7 @@ public: 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); } @@ -826,8 +829,8 @@ public: private: /** \brief Recursive expansion of the simplex tree.*/ - void siblings_expansion(Siblings * siblings, // must contain elements - int k) { + void siblings_expansion(Siblings * siblings, // must contain elements + int k) { if (dimension_ > k) { dimension_ = k; } @@ -836,33 +839,34 @@ public: Dictionary_it next = siblings->members().begin(); ++next; - static std::vector > inter; // static, not thread-safe. + 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 + Siblings * new_sib = new Siblings(siblings, // oncles + 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 + s_h->second.assign_children(siblings); // ensure the children property inter.clear(); } } } } + /** \brief Intersects Dictionary 1 [begin1;end1) with Dictionary 2 [begin2,end2) * and assigns the maximal possible Filtration_value to the Nodes. */ static void intersection(std::vector >& intersection, @@ -870,17 +874,17 @@ public: Dictionary_it begin2, Dictionary_it end2, Filtration_value filtration) { if (begin1 == end1 || begin2 == end2) - return; // ----->> + 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)))); + std::pair( + begin1->first, + Node(NULL, maximum(begin1->second.filtration(), begin2->second.filtration(), filtration)))); ++begin1; ++begin2; if (begin1 == end1 || begin2 == end2) - return; // ----->> + return; // ----->> } else { if (begin1->first < begin2->first) { ++begin1; @@ -889,11 +893,12 @@ public: } else { ++begin2; if (begin2 == end2) - return; // ----->> + return; // ----->> } } } } + /** Maximum over 3 values.*/ static Filtration_value maximum(Filtration_value a, Filtration_value b, Filtration_value c) { @@ -934,6 +939,7 @@ public: }; // Print a Simplex_tree in os. + template std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { for (auto sh : st.filtration_simplex_range()) { @@ -941,10 +947,11 @@ std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { for (auto v : st.simplex_vertex_range(sh)) { os << v << " "; } - os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n"; + os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n"; } return os; } + template std::istream& operator>>(std::istream & is, Simplex_tree & st) { // assert(st.num_simplices() == 0); @@ -954,16 +961,16 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { typename Simplex_tree::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 + int dim = static_cast (simplex.size() - 1); // Warning : simplex_size needs to be casted in int - Can be 0 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 + st.insert_simplex(simplex, fil); // insert every simplex in the simplex tree simplex.clear(); } st.set_num_simplices(num_simplices); @@ -972,8 +979,8 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { return is; } +/** @} */ // end defgroup simplex_tree -/** @} */ // end defgroup simplex_tree } // namespace Gudhi #endif // SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 55a055a0..7f2172a2 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -23,10 +23,9 @@ typedef std::pair typePairSimplexBool; typedef std::vector typeVectorVertex; typedef std::pair typeSimplex; -const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) -1; +const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) - 1; const Filtration_value DEFAULT_FILTRATION_VALUE = (const Filtration_value) 0.0; - void test_empty_simplex_tree(typeST& tst) { BOOST_CHECK(tst.null_vertex() == DEFAULT_VERTEX_HANDLE); BOOST_CHECK(tst.filtration() == DEFAULT_FILTRATION_VALUE); @@ -39,30 +38,28 @@ void test_empty_simplex_tree(typeST& tst) { BOOST_CHECK(tst.dimension() == -1); } - void test_iterators_on_empty_simplex_tree(typeST& tst) { std::cout << "Iterator on vertices: " << std::endl; for (auto vertex : tst.complex_vertex_range()) { std::cout << "vertice:" << vertex << std::endl; - BOOST_CHECK(false); // shall be empty + BOOST_CHECK(false); // shall be empty } std::cout << "Iterator on simplices: " << std::endl; for (auto simplex : tst.complex_simplex_range()) { - BOOST_CHECK(simplex != simplex); // shall be empty - to remove warning of non-used simplex + BOOST_CHECK(simplex != simplex); // shall be empty - to remove warning of non-used simplex } std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : tst.filtration_simplex_range()) { - BOOST_CHECK(false); // shall be empty + BOOST_CHECK(false); // shall be empty std::cout << "test_iterators_on_empty_simplex_tree - filtration=" << tst.filtration(f_simplex) << std::endl; } } -BOOST_AUTO_TEST_CASE( simplex_tree_when_empty ) -{ +BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) { const Filtration_value DEFAULT_FILTRATION_VALUE = 0; // TEST OF DEFAULT CONSTRUCTOR @@ -70,29 +67,28 @@ BOOST_AUTO_TEST_CASE( simplex_tree_when_empty ) std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; typeST st; - test_empty_simplex_tree (st); + test_empty_simplex_tree(st); - test_iterators_on_empty_simplex_tree (st); + test_iterators_on_empty_simplex_tree(st); // TEST OF EMPTY INSERTION std::cout << "TEST OF EMPTY INSERTION" << std::endl; typeVectorVertex simplexVectorEmpty; BOOST_CHECK(simplexVectorEmpty.empty() == true); typePairSimplexBool returnEmptyValue = st.insert_simplex(simplexVectorEmpty, - DEFAULT_FILTRATION_VALUE); + DEFAULT_FILTRATION_VALUE); BOOST_CHECK(returnEmptyValue.first == typeST::Simplex_handle(NULL)); BOOST_CHECK(returnEmptyValue.second == true); - test_empty_simplex_tree (st); + test_empty_simplex_tree(st); - test_iterators_on_empty_simplex_tree (st); + test_iterators_on_empty_simplex_tree(st); } bool AreAlmostTheSame(float a, float b) { return std::fabs(a - b) < std::numeric_limits::epsilon(); } -BOOST_AUTO_TEST_CASE( simplex_tree_from_file ) -{ +BOOST_AUTO_TEST_CASE(simplex_tree_from_file) { // TEST OF INSERTION std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl; @@ -112,16 +108,14 @@ BOOST_AUTO_TEST_CASE( simplex_tree_from_file ) BOOST_CHECK(st.filtration() == 0.4); int previous_size = 0; - for( auto f_simplex : st.filtration_simplex_range() ) - { + for (auto f_simplex : st.filtration_simplex_range()) { // Size of simplex int size = 0; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { + for (auto vertex : st.simplex_vertex_range(f_simplex)) { size++; } - BOOST_CHECK(AreAlmostTheSame(st.filtration(f_simplex),(0.1* size))); // Specific test: filtration = 0.1 * simplex_size - BOOST_CHECK(previous_size <= size);// Check list is sorted (because of sorted filtrations in simplex_tree.txt) + BOOST_CHECK(AreAlmostTheSame(st.filtration(f_simplex), (0.1 * size))); // Specific test: filtration = 0.1 * simplex_size + BOOST_CHECK(previous_size <= size); // Check list is sorted (because of sorted filtrations in simplex_tree.txt) previous_size = size; } simplex_tree_stream.close(); @@ -131,13 +125,12 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p auto f_simplex = simplexTree.filtration_simplex_range().begin() + pos; std::cout << "test_simplex_tree_contains - filtration=" << simplexTree.filtration(*f_simplex) << "||" << simplex.second << std::endl; - BOOST_CHECK( AreAlmostTheSame(simplexTree.filtration(*f_simplex),simplex.second) ); + BOOST_CHECK(AreAlmostTheSame(simplexTree.filtration(*f_simplex), simplex.second)); - int simplexIndex=simplex.first.size()-1; - for( auto vertex : simplexTree.simplex_vertex_range(*f_simplex) ) - { + int simplexIndex = simplex.first.size() - 1; + 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(vertex == simplex.first.at(simplexIndex)); BOOST_CHECK(simplexIndex >= 0); simplexIndex--; } @@ -145,7 +138,7 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p void test_simplex_tree_insert_returns_true(const typePairSimplexBool& returnValue) { BOOST_CHECK(returnValue.second == true); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned != typeST::Simplex_handle(NULL)); } @@ -175,24 +168,22 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons } 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()); - } + 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_AUTO_TEST_CASE( simplex_tree_insertion ) -{ +BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { const Filtration_value FIRST_FILTRATION_VALUE = 0.1; const Filtration_value SECOND_FILTRATION_VALUE = 0.2; const Filtration_value THIRD_FILTRATION_VALUE = 0.3; @@ -211,88 +202,88 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) std::cout << " - INSERT 0" << std::endl; typeVectorVertex firstSimplexVector; firstSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( firstSimplexVector.size() == 1 ); + BOOST_CHECK(firstSimplexVector.size() == 1); typeSimplex firstSimplex = std::make_pair( - firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); typePairSimplexBool returnValue = st.insert_simplex(firstSimplex.first, - firstSimplex.second); + firstSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, firstSimplexVector.size(), firstSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)1 ); + BOOST_CHECK(st.num_vertices() == (size_t) 1); // ++ SECOND std::cout << " - INSERT 1" << std::endl; typeVectorVertex secondSimplexVector; secondSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( secondSimplexVector.size() == 1 ); + BOOST_CHECK(secondSimplexVector.size() == 1); typeSimplex secondSimplex = std::make_pair( - secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( secondSimplex.first, secondSimplex.second ); + st.insert_simplex(secondSimplex.first, secondSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, secondSimplexVector.size(), secondSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)2 ); + BOOST_CHECK(st.num_vertices() == (size_t) 2); // ++ THIRD std::cout << " - INSERT (0,1)" << std::endl; typeVectorVertex thirdSimplexVector; thirdSimplexVector.push_back(FIRST_VERTEX_HANDLE); thirdSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( thirdSimplexVector.size() == 2 ); + BOOST_CHECK(thirdSimplexVector.size() == 2); typeSimplex thirdSimplex = std::make_pair( - thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( thirdSimplex.first, thirdSimplex.second ); + st.insert_simplex(thirdSimplex.first, thirdSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, thirdSimplexVector.size(), thirdSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)2 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 2); // Not incremented !! // ++ FOURTH std::cout << " - INSERT 2" << std::endl; typeVectorVertex fourthSimplexVector; fourthSimplexVector.push_back(THIRD_VERTEX_HANDLE); - BOOST_CHECK( fourthSimplexVector.size() == 1 ); + BOOST_CHECK(fourthSimplexVector.size() == 1); typeSimplex fourthSimplex = std::make_pair( - fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( fourthSimplex.first, fourthSimplex.second ); + st.insert_simplex(fourthSimplex.first, fourthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, fourthSimplexVector.size(), fourthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); + BOOST_CHECK(st.num_vertices() == (size_t) 3); // ++ FIFTH std::cout << " - INSERT (2,0)" << std::endl; typeVectorVertex fifthSimplexVector; fifthSimplexVector.push_back(THIRD_VERTEX_HANDLE); fifthSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( fifthSimplexVector.size() == 2 ); + BOOST_CHECK(fifthSimplexVector.size() == 2); typeSimplex fifthSimplex = std::make_pair( - fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( fifthSimplex.first, fifthSimplex.second ); + st.insert_simplex(fifthSimplex.first, fifthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, fifthSimplexVector.size(), fifthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SIXTH std::cout << " - INSERT (2,1)" << std::endl; typeVectorVertex sixthSimplexVector; sixthSimplexVector.push_back(THIRD_VERTEX_HANDLE); sixthSimplexVector.push_back(SECOND_VERTEX_HANDLE); - BOOST_CHECK( sixthSimplexVector.size() == 2 ); + BOOST_CHECK(sixthSimplexVector.size() == 2); typeSimplex sixthSimplex = std::make_pair( - sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( sixthSimplex.first, sixthSimplex.second ); + st.insert_simplex(sixthSimplex.first, sixthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, sixthSimplexVector.size(), sixthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ SEVENTH std::cout << " - INSERT (2,1,0)" << std::endl; @@ -300,61 +291,61 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) seventhSimplexVector.push_back(THIRD_VERTEX_HANDLE); seventhSimplexVector.push_back(SECOND_VERTEX_HANDLE); seventhSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( seventhSimplexVector.size() == 3 ); + BOOST_CHECK(seventhSimplexVector.size() == 3); typeSimplex seventhSimplex = std::make_pair( - seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); + seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( seventhSimplex.first, seventhSimplex.second ); + st.insert_simplex(seventhSimplex.first, seventhSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, seventhSimplexVector.size(), seventhSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! // ++ EIGHTH std::cout << " - INSERT 3" << std::endl; typeVectorVertex eighthSimplexVector; eighthSimplexVector.push_back(FOURTH_VERTEX_HANDLE); - BOOST_CHECK( eighthSimplexVector.size() == 1 ); + BOOST_CHECK(eighthSimplexVector.size() == 1); typeSimplex eighthSimplex = std::make_pair( - eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( eighthSimplex.first, eighthSimplex.second ); + st.insert_simplex(eighthSimplex.first, eighthSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // ++ NINETH std::cout << " - INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector; ninethSimplexVector.push_back(FOURTH_VERTEX_HANDLE); ninethSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( ninethSimplexVector.size() == 2 ); + BOOST_CHECK(ninethSimplexVector.size() == 2); typeSimplex ninethSimplex = std::make_pair( - ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( ninethSimplex.first, ninethSimplex.second ); + st.insert_simplex(ninethSimplex.first, ninethSimplex.second); - test_simplex_tree_insert_returns_true (returnValue); + test_simplex_tree_insert_returns_true(returnValue); set_and_test_simplex_tree_dim_fil(st, ninethSimplexVector.size(), ninethSimplex.second); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented !! + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! // ++ TENTH std::cout << " - INSERT 0 (already inserted)" << std::endl; typeVectorVertex tenthSimplexVector; tenthSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( tenthSimplexVector.size() == 1 ); + BOOST_CHECK(tenthSimplexVector.size() == 1); typeSimplex tenthSimplex = std::make_pair( - tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); // With a different filtration value + tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); // With a different filtration value returnValue = - st.insert_simplex ( tenthSimplex.first, tenthSimplex.second ); + st.insert_simplex(tenthSimplex.first, tenthSimplex.second); BOOST_CHECK(returnValue.second == false); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented !! - BOOST_CHECK( st.dimension() == dim_max ); - BOOST_CHECK( AreAlmostTheSame(st.filtration(), max_fil) ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! + BOOST_CHECK(st.dimension() == dim_max); + BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); // ++ ELEVENTH std::cout << " - INSERT (2,1,0) (already inserted)" << std::endl; @@ -362,18 +353,18 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) eleventhSimplexVector.push_back(THIRD_VERTEX_HANDLE); eleventhSimplexVector.push_back(SECOND_VERTEX_HANDLE); eleventhSimplexVector.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( eleventhSimplexVector.size() == 3 ); + BOOST_CHECK(eleventhSimplexVector.size() == 3); typeSimplex eleventhSimplex = std::make_pair( - eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); + eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); returnValue = - st.insert_simplex ( eleventhSimplex.first, eleventhSimplex.second ); + st.insert_simplex(eleventhSimplex.first, eleventhSimplex.second); BOOST_CHECK(returnValue.second == false); - shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); - BOOST_CHECK( st.num_vertices() == (size_t)4 );// Not incremented !! - BOOST_CHECK( st.dimension() == dim_max ); - BOOST_CHECK( AreAlmostTheSame(st.filtration(), max_fil) ); + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! + BOOST_CHECK(st.dimension() == dim_max); + BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); /* Inserted simplex: */ /* 1 */ @@ -393,330 +384,325 @@ BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) // [0.3] 2 1 0 // !! Be careful, simplex are sorted by filtration value on insertion !! std::cout << "simplex_tree_insertion - first - 0" << std::endl; - test_simplex_tree_contains(st, firstSimplex, 0);// (0) -> 0 + test_simplex_tree_contains(st, firstSimplex, 0); // (0) -> 0 std::cout << "simplex_tree_insertion - second - 1" << std::endl; - test_simplex_tree_contains(st, secondSimplex, 1);// (1) -> 1 + test_simplex_tree_contains(st, secondSimplex, 1); // (1) -> 1 std::cout << "simplex_tree_insertion - third - 4" << std::endl; - test_simplex_tree_contains(st, thirdSimplex, 4);// (0,1) -> 4 + test_simplex_tree_contains(st, thirdSimplex, 4); // (0,1) -> 4 std::cout << "simplex_tree_insertion - fourth - 2" << std::endl; - test_simplex_tree_contains(st, fourthSimplex, 2);// (2) -> 2 + test_simplex_tree_contains(st, fourthSimplex, 2); // (2) -> 2 std::cout << "simplex_tree_insertion - fifth - 5" << std::endl; - test_simplex_tree_contains(st, fifthSimplex, 5);// (2,0) -> 5 + test_simplex_tree_contains(st, fifthSimplex, 5); // (2,0) -> 5 std::cout << "simplex_tree_insertion - sixth - 6" << std::endl; - test_simplex_tree_contains(st, sixthSimplex, 6);//(2,1) -> 6 + test_simplex_tree_contains(st, sixthSimplex, 6); //(2,1) -> 6 std::cout << "simplex_tree_insertion - seventh - 8" << std::endl; - test_simplex_tree_contains(st, seventhSimplex, 8);// (2,1,0) -> 8 + test_simplex_tree_contains(st, seventhSimplex, 8); // (2,1,0) -> 8 std::cout << "simplex_tree_insertion - eighth - 3" << std::endl; - test_simplex_tree_contains(st, eighthSimplex, 3);// (3) -> 3 + test_simplex_tree_contains(st, eighthSimplex, 3); // (3) -> 3 std::cout << "simplex_tree_insertion - nineth - 7" << std::endl; - test_simplex_tree_contains(st, ninethSimplex, 7);// (3,0) -> 7 + test_simplex_tree_contains(st, ninethSimplex, 7); // (3,0) -> 7 // Display the Simplex_tree - Can not be done in the middle of 2 inserts std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for( auto f_simplex : st.filtration_simplex_range() ) - { + for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { - std::cout << (int)vertex << " "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; } std::cout << std::endl; } } -BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) -{ - Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle)0; - Vertex_handle SECOND_VERTEX_HANDLE = (Vertex_handle) 1; - Vertex_handle THIRD_VERTEX_HANDLE = (Vertex_handle) 2; - Vertex_handle FOURTH_VERTEX_HANDLE = (Vertex_handle) 3; - Vertex_handle FIFTH_VERTEX_HANDLE = (Vertex_handle) 4; - Vertex_handle SIXTH_VERTEX_HANDLE = (Vertex_handle) 5; - Vertex_handle SEVENTH_VERTEX_HANDLE = (Vertex_handle) 6; - Vertex_handle EIGHTH_VERTEX_HANDLE = (Vertex_handle) 7; - - // TEST OF INSERTION - std::cout << "********************************************************************" << std::endl; - std::cout << "TEST OF INSERTION" << std::endl; - typeST st; - - // ++ FIRST - std::cout << " - INSERT (2,1,0)" << std::endl; - typeVectorVertex SimplexVector1; - SimplexVector1.push_back(THIRD_VERTEX_HANDLE); - SimplexVector1.push_back(SECOND_VERTEX_HANDLE); - SimplexVector1.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector1.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector1 ); - - BOOST_CHECK( st.num_vertices() == (size_t)3 ); // +3 (2, 1 and 0 are not existing) - - // ++ SECOND - std::cout << " - INSERT 3" << std::endl; - typeVectorVertex SimplexVector2; - SimplexVector2.push_back(FOURTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector2.size() == 1 ); - st.insert_simplex_and_subfaces ( SimplexVector2 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // +1 (3 is not existing) - - // ++ THIRD - std::cout << " - INSERT (0,3)" << std::endl; - typeVectorVertex SimplexVector3; - SimplexVector3.push_back(FOURTH_VERTEX_HANDLE); - SimplexVector3.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector3.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector3 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) - - // ++ FOURTH - std::cout << " - INSERT (1,0) (already inserted)" << std::endl; - typeVectorVertex SimplexVector4; - SimplexVector4.push_back(SECOND_VERTEX_HANDLE); - SimplexVector4.push_back(FIRST_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector4.size() == 2 ); - st.insert_simplex_and_subfaces ( SimplexVector4 ); - - BOOST_CHECK( st.num_vertices() == (size_t)4 ); // Not incremented (all are existing) - - // ++ FIFTH - std::cout << " - INSERT (3,4,5)" << std::endl; - typeVectorVertex SimplexVector5; - SimplexVector5.push_back(FOURTH_VERTEX_HANDLE); - SimplexVector5.push_back(FIFTH_VERTEX_HANDLE); - SimplexVector5.push_back(SIXTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector5.size() == 3 ); - st.insert_simplex_and_subfaces ( SimplexVector5 ); - - BOOST_CHECK( st.num_vertices() == (size_t)6 ); - - // ++ SIXTH - std::cout << " - INSERT (0,1,6,7)" << std::endl; - typeVectorVertex SimplexVector6; - SimplexVector6.push_back(FIRST_VERTEX_HANDLE); - SimplexVector6.push_back(SECOND_VERTEX_HANDLE); - SimplexVector6.push_back(SEVENTH_VERTEX_HANDLE); - SimplexVector6.push_back(EIGHTH_VERTEX_HANDLE); - BOOST_CHECK( SimplexVector6.size() == 4 ); - st.insert_simplex_and_subfaces ( SimplexVector6 ); - - BOOST_CHECK( st.num_vertices() == (size_t)8 ); // +2 (6 and 7 are not existing - 0 and 1 are already existing) - - /* Inserted simplex: */ - /* 1 6 */ - /* o---o */ - /* /X\7/ */ - /* o---o---o---o */ - /* 2 0 3\X/4 */ - /* o */ - /* 5 */ - /* */ - /* In other words: */ - /* A facet [2,1,0] */ - /* An edge [0,3] */ - /* A facet [3,4,5] */ - /* A cell [0,1,6,7] */ - - typeSimplex simplexPair1 = std::make_pair(SimplexVector1, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair2 = std::make_pair(SimplexVector2, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair3 = std::make_pair(SimplexVector3, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); - typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); - test_simplex_tree_contains(st,simplexPair1,6); // (2,1,0) is in position 6 - test_simplex_tree_contains(st,simplexPair2,7); // (3) is in position 7 - test_simplex_tree_contains(st,simplexPair3,8); // (3,0) is in position 8 - test_simplex_tree_contains(st,simplexPair4,2); // (1,0) is in position 2 - test_simplex_tree_contains(st,simplexPair5,14); // (3,4,5) is in position 14 - test_simplex_tree_contains(st,simplexPair6,26); // (7,6,1,0) is in position 26 - - // ------------------------------------------------------------------------------------------------------------------ - // Find in the simplex_tree - // ------------------------------------------------------------------------------------------------------------------ - typeVectorVertex simpleSimplexVector; - simpleSimplexVector.push_back(SECOND_VERTEX_HANDLE); - Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); - std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - Vertex_handle UNKNOWN_VERTEX_HANDLE = (Vertex_handle) 15; - typeVectorVertex unknownSimplexVector; - unknownSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); - simplexFound = st.find(unknownSimplexVector); - std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is NOT found - BOOST_CHECK(simplexFound == st.null_simplex()); - - simplexFound = st.find(SimplexVector6); - std::cout << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - typeVectorVertex otherSimplexVector; - otherSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); - otherSimplexVector.push_back(SECOND_VERTEX_HANDLE); - simplexFound = st.find(otherSimplexVector); - std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is NOT found - BOOST_CHECK(simplexFound == st.null_simplex()); - - typeVectorVertex invSimplexVector; - invSimplexVector.push_back(SECOND_VERTEX_HANDLE); - invSimplexVector.push_back(THIRD_VERTEX_HANDLE); - invSimplexVector.push_back(FIRST_VERTEX_HANDLE); - simplexFound = st.find(invSimplexVector); - std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; - if (simplexFound != st.null_simplex()) - std::cout << "***+ YES IT IS!\n"; - else - std::cout << "***- NO IT ISN'T\n"; - // Check it is found - BOOST_CHECK(simplexFound != st.null_simplex()); - - - - // Display the Simplex_tree - Can not be done in the middle of 2 inserts - std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; - std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; - for( auto f_simplex : st.filtration_simplex_range() ) - { - std::cout << " " << "[" << st.filtration(f_simplex) << "] "; - for( auto vertex : st.simplex_vertex_range(f_simplex) ) - { - std::cout << (int)vertex << " "; - } - std::cout << std::endl; - } - - std::cout << "********************************************************************" << std::endl; - // TEST COFACE ALGORITHM - st.set_dimension(3); - std::cout << "COFACE ALGORITHM" << std::endl; - std::vector v; - std::vector simplex; - 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(); - 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); - result.clear(); - - std::cout << "Third test : " << std::endl; - std::cout << "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.push_back(7); - simplex.push_back(6); - simplex.push_back(1); - result.push_back(st.find(simplex)); - simplex.clear(); - - test_cofaces(st, v, 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); -// 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); - - /* - // TEST Off read - std::cout << "********************************************************************" << std::endl; - typeST st2; - st2.tree_from_off("test.off"); - std::cout << st2; - */ +BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { + Vertex_handle FIRST_VERTEX_HANDLE = (Vertex_handle) 0; + Vertex_handle SECOND_VERTEX_HANDLE = (Vertex_handle) 1; + Vertex_handle THIRD_VERTEX_HANDLE = (Vertex_handle) 2; + Vertex_handle FOURTH_VERTEX_HANDLE = (Vertex_handle) 3; + Vertex_handle FIFTH_VERTEX_HANDLE = (Vertex_handle) 4; + Vertex_handle SIXTH_VERTEX_HANDLE = (Vertex_handle) 5; + Vertex_handle SEVENTH_VERTEX_HANDLE = (Vertex_handle) 6; + Vertex_handle EIGHTH_VERTEX_HANDLE = (Vertex_handle) 7; + + // TEST OF INSERTION + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST OF INSERTION" << std::endl; + typeST st; + + // ++ FIRST + std::cout << " - INSERT (2,1,0)" << std::endl; + typeVectorVertex SimplexVector1; + SimplexVector1.push_back(THIRD_VERTEX_HANDLE); + SimplexVector1.push_back(SECOND_VERTEX_HANDLE); + SimplexVector1.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector1.size() == 3); + st.insert_simplex_and_subfaces(SimplexVector1); + + BOOST_CHECK(st.num_vertices() == (size_t) 3); // +3 (2, 1 and 0 are not existing) + + // ++ SECOND + std::cout << " - INSERT 3" << std::endl; + typeVectorVertex SimplexVector2; + SimplexVector2.push_back(FOURTH_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector2.size() == 1); + st.insert_simplex_and_subfaces(SimplexVector2); + + BOOST_CHECK(st.num_vertices() == (size_t) 4); // +1 (3 is not existing) + + // ++ THIRD + std::cout << " - INSERT (0,3)" << std::endl; + typeVectorVertex SimplexVector3; + SimplexVector3.push_back(FOURTH_VERTEX_HANDLE); + SimplexVector3.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector3.size() == 2); + st.insert_simplex_and_subfaces(SimplexVector3); + + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented (all are existing) + + // ++ FOURTH + std::cout << " - INSERT (1,0) (already inserted)" << std::endl; + typeVectorVertex SimplexVector4; + SimplexVector4.push_back(SECOND_VERTEX_HANDLE); + SimplexVector4.push_back(FIRST_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector4.size() == 2); + st.insert_simplex_and_subfaces(SimplexVector4); + + BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented (all are existing) + + // ++ FIFTH + std::cout << " - INSERT (3,4,5)" << std::endl; + typeVectorVertex SimplexVector5; + SimplexVector5.push_back(FOURTH_VERTEX_HANDLE); + SimplexVector5.push_back(FIFTH_VERTEX_HANDLE); + SimplexVector5.push_back(SIXTH_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector5.size() == 3); + st.insert_simplex_and_subfaces(SimplexVector5); + + BOOST_CHECK(st.num_vertices() == (size_t) 6); + + // ++ SIXTH + std::cout << " - INSERT (0,1,6,7)" << std::endl; + typeVectorVertex SimplexVector6; + SimplexVector6.push_back(FIRST_VERTEX_HANDLE); + SimplexVector6.push_back(SECOND_VERTEX_HANDLE); + SimplexVector6.push_back(SEVENTH_VERTEX_HANDLE); + SimplexVector6.push_back(EIGHTH_VERTEX_HANDLE); + BOOST_CHECK(SimplexVector6.size() == 4); + st.insert_simplex_and_subfaces(SimplexVector6); + + BOOST_CHECK(st.num_vertices() == (size_t) 8); // +2 (6 and 7 are not existing - 0 and 1 are already existing) + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + /* */ + /* In other words: */ + /* A facet [2,1,0] */ + /* An edge [0,3] */ + /* A facet [3,4,5] */ + /* A cell [0,1,6,7] */ + + typeSimplex simplexPair1 = std::make_pair(SimplexVector1, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair2 = std::make_pair(SimplexVector2, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair3 = std::make_pair(SimplexVector3, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); + test_simplex_tree_contains(st, simplexPair1, 6); // (2,1,0) is in position 6 + test_simplex_tree_contains(st, simplexPair2, 7); // (3) is in position 7 + test_simplex_tree_contains(st, simplexPair3, 8); // (3,0) is in position 8 + test_simplex_tree_contains(st, simplexPair4, 2); // (1,0) is in position 2 + test_simplex_tree_contains(st, simplexPair5, 14); // (3,4,5) is in position 14 + test_simplex_tree_contains(st, simplexPair6, 26); // (7,6,1,0) is in position 26 + + // ------------------------------------------------------------------------------------------------------------------ + // Find in the simplex_tree + // ------------------------------------------------------------------------------------------------------------------ + typeVectorVertex simpleSimplexVector; + simpleSimplexVector.push_back(SECOND_VERTEX_HANDLE); + Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); + std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); + + Vertex_handle UNKNOWN_VERTEX_HANDLE = (Vertex_handle) 15; + typeVectorVertex unknownSimplexVector; + unknownSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); + simplexFound = st.find(unknownSimplexVector); + std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is NOT found + BOOST_CHECK(simplexFound == st.null_simplex()); + + simplexFound = st.find(SimplexVector6); + std::cout << "**************IS THE SIMPLEX {0,1,6,7} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); + + typeVectorVertex otherSimplexVector; + otherSimplexVector.push_back(UNKNOWN_VERTEX_HANDLE); + otherSimplexVector.push_back(SECOND_VERTEX_HANDLE); + simplexFound = st.find(otherSimplexVector); + std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is NOT found + BOOST_CHECK(simplexFound == st.null_simplex()); + + typeVectorVertex invSimplexVector; + invSimplexVector.push_back(SECOND_VERTEX_HANDLE); + invSimplexVector.push_back(THIRD_VERTEX_HANDLE); + invSimplexVector.push_back(FIRST_VERTEX_HANDLE); + simplexFound = st.find(invSimplexVector); + std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != st.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + // Check it is found + BOOST_CHECK(simplexFound != st.null_simplex()); + + + + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << (int) vertex << " "; + } + std::cout << std::endl; + } + + std::cout << "********************************************************************" << std::endl; + // TEST COFACE ALGORITHM + st.set_dimension(3); + std::cout << "COFACE ALGORITHM" << std::endl; + std::vector v; + std::vector simplex; + 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(); + 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); + result.clear(); + + std::cout << "Third test : " << std::endl; + std::cout << "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.push_back(7); + simplex.push_back(6); + simplex.push_back(1); + result.push_back(st.find(simplex)); + simplex.clear(); + + test_cofaces(st, v, 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); + // 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); + + /* + // TEST Off read + std::cout << "********************************************************************" << std::endl; + typeST st2; + st2.tree_from_off("test.off"); + std::cout << st2; + */ } -- cgit v1.2.3 From c265cc17993fb6319af9baea9ca431e171815335 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 7 Jul 2015 14:30:02 +0000 Subject: cpplint fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@692 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 85df90931dc594c38fa7dd564ec1c731b5be748b --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 53 +++++++++++++++------------ 1 file changed, 29 insertions(+), 24 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 2507f783..0a383492 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -132,7 +132,6 @@ class Simplex_tree { typedef typename Dictionary_it::value_type Dit_value_t; struct return_first { - Vertex_handle operator()(const Dit_value_t& p_sh) const { return p_sh.first; } @@ -469,8 +468,8 @@ class Simplex_tree { if (simplex.empty()) { return std::pair(null_simplex(), true); } - - sort(simplex.begin(), simplex.end()); // must be sorted in increasing order + // must be sorted in increasing order + sort(simplex.begin(), simplex.end()); Siblings * curr_sib = &root_; std::pair res_insert; @@ -483,12 +482,15 @@ class Simplex_tree { 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; @@ -637,27 +639,30 @@ class Simplex_tree { bool addCoface = (star || curr_nbVertices == nbVertices); // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices if (addCoface) cofaces.push_back(simplex); - if ((!addCoface || star) && has_children(simplex)) // Rec call + 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 + 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 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 - { // Rec call + 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()) + } else if (simplex->first > vertices.back()) { return; - else // (simplex->first < vertices.back() + } else { + // (simplex->first < vertices.back() if (has_children(simplex)) - rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + rec_coface(vertices, simplex->second.children(), curr_nbVertices + 1, cofaces, star, nbVertices); + } } } } @@ -726,7 +731,6 @@ class Simplex_tree { * Reverse lexicographic order has the property to always consider the subsimplex of a simplex * to be smaller. The filtration function must be monotonic. */ struct is_before_in_filtration { - explicit is_before_in_filtration(Simplex_tree * st) : st_(st) { } @@ -829,7 +833,7 @@ class Simplex_tree { private: /** \brief Recursive expansion of the simplex tree.*/ - void siblings_expansion(Siblings * siblings, // must contain elements + void siblings_expansion(Siblings * siblings, // must contain elements int k) { if (dimension_ > k) { dimension_ = k; @@ -839,28 +843,29 @@ class Simplex_tree { Dictionary_it next = siblings->members().begin(); ++next; - static std::vector > inter; // static, not thread-safe. + static std::vector > inter; // static, not thread-safe. for (Dictionary_it s_h = siblings->members().begin(); s_h != siblings->members().end(); ++s_h, ++next) { Simplex_handle root_sh = find_vertex(s_h->first); if (has_children(root_sh)) { intersection( - inter, // output intersection - next, // begin - siblings->members().end(), // end + 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 + Siblings * new_sib = new Siblings(siblings, // oncles + 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(); } } -- cgit v1.2.3 From 2cdff70bfd4dd1307cea047017fa58fb116207a8 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 7 Jul 2015 14:44:01 +0000 Subject: cpplint fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@693 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c59d90f177f6b7bc2192189cff926336fec6d97d --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 62 +++++++++++++++------------ 1 file changed, 34 insertions(+), 28 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 0a383492..3ed59c04 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 @@ -86,9 +86,8 @@ namespace Gudhi { * */ template class Simplex_tree { public: @@ -187,7 +186,7 @@ class Simplex_tree { /** \brief Range over the simplices of the simplicial complex, ordered by the filtration. */ typedef boost::iterator_range Filtration_simplex_range; - /* @} */ // end name range and iterator types + /* @} */ // end name range and iterator types /** \name Range and iterator methods * @{ */ @@ -256,7 +255,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 + assert(sh != null_simplex()); // Empty simplex return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -280,7 +279,7 @@ class Simplex_tree { Boundary_simplex_iterator(this)); } - /** @} */ // end range and iterator methods + /** @} */ // end range and iterator methods /** \name Constructor/Destructor * @{ */ @@ -301,9 +300,9 @@ class Simplex_tree { } } } - /** @} */ // end constructor/destructor + /** @} */ // 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)) { @@ -336,7 +335,7 @@ class Simplex_tree { return sh->second.filtration(); } else { return INFINITY; - } // filtration(); } + } } /** \brief Returns an upper bound of the filtration values of the simplices. */ @@ -411,7 +410,7 @@ class Simplex_tree { */ template Simplex_handle find(RandomAccessVertexRange & s) { - if (s.begin() == s.end()) // Empty simplex + if (s.begin() == s.end()) // Empty simplex return null_simplex(); sort(s.begin(), s.end()); @@ -630,13 +629,17 @@ class Simplex_tree { * 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 + 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 - bool addCoface = (star || curr_nbVertices == nbVertices); // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices + // 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 @@ -690,7 +693,7 @@ class Simplex_tree { 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 || + 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 @@ -879,17 +882,17 @@ class Simplex_tree { Dictionary_it begin2, Dictionary_it end2, Filtration_value filtration) { if (begin1 == end1 || begin2 == end2) - return; // ----->> + 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)))); + intersection.push_back(std::pair(begin1->first, + Node(NULL, + maximum(begin1->second.filtration(), + begin2->second.filtration(), filtration)))); ++begin1; ++begin2; if (begin1 == end1 || begin2 == end2) - return; // ----->> + return; // ----->> } else { if (begin1->first < begin2->first) { ++begin1; @@ -898,7 +901,7 @@ class Simplex_tree { } else { ++begin2; if (begin2 == end2) - return; // ----->> + return; // ----->> } } } @@ -966,16 +969,19 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { typename Simplex_tree::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); @@ -988,4 +994,4 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { } // namespace Gudhi -#endif // SRC_SIMPLEX_TREE_INCLUDE_GUDHI_SIMPLEX_TREE_H_ +#endif // SIMPLEX_TREE_H_ -- cgit v1.2.3 From 76fa90a05998bd2015afb53f96e0512cd41826af Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 7 Jul 2015 14:53:07 +0000 Subject: cpplint fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/coface@694 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 80593486ab7473309e5ae00305561a331e527cc5 --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 23 ++++++++++++----------- 1 file changed, 12 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 3ed59c04..95a6d090 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -637,7 +637,7 @@ class Simplex_tree { 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) @@ -645,14 +645,13 @@ class Simplex_tree { 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 - { + 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)) - { + if ((!addCoface || star) && has_children(simplex)) { // Rec call Vertex_handle tmp = vertices.back(); vertices.pop_back(); @@ -741,8 +740,8 @@ class Simplex_tree { 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_; @@ -769,7 +768,8 @@ class Simplex_tree { * 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; @@ -798,7 +798,8 @@ class Simplex_tree { ++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)); @@ -955,7 +956,7 @@ std::ostream& operator<<(std::ostream & os, Simplex_tree & st) { for (auto v : st.simplex_vertex_range(sh)) { os << v << " "; } - os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n"; + os << st.filtration(sh) << "\n"; // TODO(VR): why adding the key ?? not read ?? << " " << st.key(sh) << " \n"; } return os; } @@ -990,7 +991,7 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { return is; } -/** @} */ // end defgroup simplex_tree +/** @} */ // end defgroup simplex_tree } // namespace Gudhi -- cgit v1.2.3