diff options
Diffstat (limited to 'include/gudhi/Skeleton_blocker.h')
| -rw-r--r-- | include/gudhi/Skeleton_blocker.h | 219 |
1 files changed, 110 insertions, 109 deletions
diff --git a/include/gudhi/Skeleton_blocker.h b/include/gudhi/Skeleton_blocker.h index 822282fd..32fe411c 100644 --- a/include/gudhi/Skeleton_blocker.h +++ b/include/gudhi/Skeleton_blocker.h @@ -1,24 +1,24 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ #ifndef SKELETON_BLOCKER_H_ #define SKELETON_BLOCKER_H_ @@ -37,11 +37,12 @@ namespace Gudhi { namespace skeleton_blocker { -/** \defgroup skbl Skeleton-Blocker +/** \defgroup skbl Skeleton-Blocker +@{ \author David Salinas -\section Introduction +\section skblintroduction Introduction The Skeleton-Blocker data-structure proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its simplices \cite socg_blockers_2011,\cite blockers2012. @@ -52,7 +53,7 @@ This data-structure handles all simplicial complexes operations such as are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. -\section Definitions +\section skbldefinitions Definitions We recall briefly classical definitions of simplicial complexes \cite Munkres-elementsalgtop1984. @@ -63,7 +64,7 @@ when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \si An abstract simplicial complex is a set of simplices that contains all the faces of its simplices. The 1-skeleton of a simplicial complex (or its graph) consists of its elements of dimension lower than 2. -*\image html "ds_representation.png" "Skeleton-blocker representation" width=20cm + *\image html "ds_representation.png" "Skeleton-blocker representation" width=20cm To encode, a simplicial complex, one can encodes all its simplices. @@ -85,7 +86,7 @@ in next figure. Storing the graph and blockers of such simplicial complexes is m their simplices. -*\image html "blockers_curve.png" "Number of blockers of random triangulations of 3-spheres" width=10cm + *\image html "blockers_curve.png" "Number of blockers of random triangulations of 3-spheres" width=10cm @@ -107,7 +108,7 @@ and point access in addition. -\subsection Visitor +\subsection skblvisitor Visitor The class Skeleton_blocker_complex has a visitor that is called when usual operations such as adding an edge or remove a vertex are called. You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the \ref contr package). @@ -115,7 +116,7 @@ You may want to use this visitor to compute statistics or to update another data -\section Example +\section skblexample Example \subsection Iterating Iterating through vertices, edges, blockers and simplices @@ -127,46 +128,46 @@ such as the Simplex Tree. The following example computes the Euler Characteristi of a simplicial complex. \code{.cpp} - typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; - typedef Complex::Vertex_handle Vertex_handle; - typedef Complex::Simplex Simplex; - - const int n = 15; - - // build a full complex with 10 vertices and 2^n-1 simplices - Complex complex; - for(int i=0;i<n;i++) - complex.add_vertex(); - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - complex.add_edge_without_blockers(Vertex_handle(i),Vertex_handle(j)); - - // this is just to illustrate iterators, to count number of vertices - // or edges, complex.num_vertices() and complex.num_edges() are - // more appropriated! - unsigned num_vertices = 0; - for(auto v : complex.vertex_range()){ - ++num_vertices; - } - - unsigned num_edges = 0; - for(auto e : complex.edge_range()) - ++num_edges; - - unsigned euler = 0; - unsigned num_simplices = 0; - // we use a reference to a simplex instead of a copy - // value here because a simplex is a set of integers - // and copying it cost time - for(const Simplex & s : complex.star_simplex_range()){ - ++num_simplices; - if(s.dimension()%2 == 0) - euler += 1; - else - euler -= 1; - } - std::cout << "Saw "<<num_vertices<<" vertices, "<<num_edges<<" edges and "<<num_simplices<<" simplices"<<std::endl; - std::cout << "The Euler Characteristic is "<<euler<<std::endl; + typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; + typedef Complex::Vertex_handle Vertex_handle; + typedef Complex::Simplex Simplex; + + const int n = 15; + + // build a full complex with 10 vertices and 2^n-1 simplices + Complex complex; + for(int i=0;i<n;i++) + complex.add_vertex(); + for(int i=0;i<n;i++) + for(int j=0;j<i;j++) + complex.add_edge_without_blockers(Vertex_handle(i),Vertex_handle(j)); + + // this is just to illustrate iterators, to count number of vertices + // or edges, complex.num_vertices() and complex.num_edges() are + // more appropriated! + unsigned num_vertices = 0; + for(auto v : complex.vertex_range()){ + ++num_vertices; + } + + unsigned num_edges = 0; + for(auto e : complex.edge_range()) + ++num_edges; + + unsigned euler = 0; + unsigned num_simplices = 0; + // we use a reference to a simplex instead of a copy + // value here because a simplex is a set of integers + // and copying it cost time + for(const Simplex & s : complex.star_simplex_range()){ + ++num_simplices; + if(s.dimension()%2 == 0) + euler += 1; + else + euler -= 1; + } + std::cout << "Saw "<<num_vertices<<" vertices, "<<num_edges<<" edges and "<<num_simplices<<" simplices"<<std::endl; + std::cout << "The Euler Characteristic is "<<euler<<std::endl; \endcode @@ -181,43 +182,43 @@ The Euler Characteristic is 1 \subsection s Constructing a skeleton-blockers from a list of maximal faces or from a list of faces \code{.cpp} - std::vector<Simplex> simplices; - - //add 4 triangles of a tetrahedron 0123 - simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(2))); - simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(1))); - - Complex complex; - //get complex from top faces - make_complex_from_top_faces(complex,simplices.begin(),simplices.end()); - - std::cout << "Simplices:"<<std::endl; - for(const Simplex & s : complex.star_simplex_range()) - std::cout << s << " "; - std::cout << std::endl; - - //One blocker as simplex 0123 is not in the complex but all its proper faces are. - std::cout << "Blockers: "<<complex.blockers_to_string()<<std::endl; - - //now build a complex from its full list of simplices - simplices.clear(); - simplices.push_back(Simplex(Vertex_handle(0))); - simplices.push_back(Simplex(Vertex_handle(1))); - simplices.push_back(Simplex(Vertex_handle(2))); - simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1))); - simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex(Vertex_handle(2),Vertex_handle(0))); - complex = Complex(simplices.begin(),simplices.end()); - - std::cout << "Simplices:"<<std::endl; - for(const Simplex & s : complex.star_simplex_range()) - std::cout << s << " "; - std::cout << std::endl; - - //One blocker as simplex 012 is not in the complex but all its proper faces are. - std::cout << "Blockers: "<<complex.blockers_to_string()<<std::endl; + std::vector<Simplex> simplices; + + //add 4 triangles of a tetrahedron 0123 + simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); + simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(1))); + + Complex complex; + //get complex from top faces + make_complex_from_top_faces(complex,simplices.begin(),simplices.end()); + + std::cout << "Simplices:"<<std::endl; + for(const Simplex & s : complex.star_simplex_range()) + std::cout << s << " "; + std::cout << std::endl; + + //One blocker as simplex 0123 is not in the complex but all its proper faces are. + std::cout << "Blockers: "<<complex.blockers_to_string()<<std::endl; + + //now build a complex from its full list of simplices + simplices.clear(); + simplices.push_back(Simplex(Vertex_handle(0))); + simplices.push_back(Simplex(Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(2),Vertex_handle(0))); + complex = Complex(simplices.begin(),simplices.end()); + + std::cout << "Simplices:"<<std::endl; + for(const Simplex & s : complex.star_simplex_range()) + std::cout << s << " "; + std::cout << std::endl; + + //One blocker as simplex 012 is not in the complex but all its proper faces are. + std::cout << "Blockers: "<<complex.blockers_to_string()<<std::endl; \endcode \verbatim ./SkeletonBlockerFromSimplices @@ -236,12 +237,12 @@ The author wishes to thank Dominique Attali and André Lieutier for their collaboration to write the two initial papers \cite socg_blockers_2011,\cite blockers2012 about this data-structure - and also Dominique for leaving him use a prototype. + and also Dominique for leaving him use a prototype. -\copyright GNU General Public License v3. -*/ -/** @} */ // end defgroup +\copyright GNU General Public License v3. + +@} */ } // namespace skeleton_blocker |