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 +++++++++++++++++++++++ src/Simplex_tree/test/simplex_tree_unit_test.cpp | 46 ++++++++++ 2 files changed, 152 insertions(+) (limited to 'src') 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 diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 6b0a1f3d..f685f079 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -170,6 +170,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) +{ + 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); + 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; + } +} + BOOST_AUTO_TEST_CASE( simplex_tree_insertion ) { const Filtration_value FIRST_FILTRATION_VALUE = 0.1; @@ -587,4 +606,31 @@ BOOST_AUTO_TEST_CASE( NSimplexAndSubfaces_tree_insertion ) std::cout << std::endl; } + std::cout << "********************************************************************" << std::endl; + // TEST COFACE ALGORITHM + st.set_dimension(3); + std::cout << "COFACE ALGORITHM" << std::endl; + std::vector v; + v.push_back(3); + std::cout << "Star of (3):" << std::endl; + test_cofaces(st, v, 0, 4); + v.clear(); + v.push_back(1); + v.push_back(7); + 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); + std::cout << "Cofaces with a codimension too high (codimension + vetices > tree.dimension)" << std::endl; + test_cofaces(st, v, 5, 0); + std::cout << "Cofaces with an empty codimension" << std::endl; + test_cofaces(st, v, -1, 0); + std::cout << "Cofaces in an empty simplex tree" << std::endl; + typeST empty_tree; + test_cofaces(empty_tree, v, 1, 0); + std::cout << "Cofaces of an empty simplex" << std::endl; + v.clear(); + test_cofaces(st, v, 1, 0); + + } -- cgit v1.2.3