diff options
Diffstat (limited to 'src/Simplex_tree/include/gudhi')
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 104 |
1 files changed, 99 insertions, 5 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 9d0cf755..0c2c851a 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: @@ -156,6 +156,8 @@ class Simplex_tree { typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Simplex_vertex_iterator; /** \brief Range over the vertices of a simplex. */ typedef boost::iterator_range<Simplex_vertex_iterator> Simplex_vertex_range; + /** \brief Range over the cofaces of a simplex. */ + typedef std::vector<Simplex_handle> Cofaces_simplex_range; /** \brief Iterator over the simplices of the boundary of a simplex. * * 'value_type' is Simplex_handle. */ @@ -187,8 +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( @@ -206,6 +207,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 +254,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 (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. @@ -386,6 +390,8 @@ class Simplex_tree { bool has_children(Simplex_handle sh) const { 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 @@ -397,8 +403,8 @@ class Simplex_tree { */ template<class RandomAccessVertexRange> 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()); @@ -599,6 +605,94 @@ 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<Vertex_handle> &vertices, Siblings *curr_sib, int curr_nbVertices, std::vector<Simplex_handle>& 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 + { + 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<Vertex_handle> 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<Vertex_handle>())); // must be sorted in decreasing order + bool star = codimension == 0; + rec_coface(copy, &root_, 1, cofaces, star, codimension + (int)copy.size()); + return cofaces; + } + + + private: /** \brief Returns true iff the list of vertices of sh1 |