diff options
Diffstat (limited to 'src/Skeleton_blocker/include')
19 files changed, 697 insertions, 262 deletions
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 1d215984..eff37a18 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker.h - * - * Created on: Jan, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKER_H #define GUDHI_SKELETON_BLOCKER_H @@ -20,5 +34,164 @@ #include "gudhi/Utils.h" //xxx + +/** \defgroup skbl Skeleton-Blocker + +\author David Salinas + +\section Introduction +The Skeleton-Blocker data-structure had been introduced in the two papers +\cite socg_blockers_2011,\cite blockers2012. +It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its +simplices. +Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that +is very small in practice (see next section for a formal definition). +This data-structure handles all simplicial complexes operations such as + as simplex enumeration or simplex removal but operations that are particularly efficient + are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. + + +\section Definitions + +We recall briefly classical definitions of simplicial complexes + \cite Munkres-elementsalgtop1984. +An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. +Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of +\f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, +when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \sigma\f$. +An abstract simplicial complex is a set of simplices that contains all the faces of their 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 + + +To encode, a simplicial complex, one can encodes all its simplices. +In case when this number gets too large, +a lighter and implicit version consists of encoding only its graph plus some elements called missing faces or blockers. +A blocker is a simplex of dimension greater than 1 +that does not belong to the complex but whose all proper faces does. + + +Remark that for a clique complex (i.e. a simplicial complex whose simplices are cliques of its graph), the set of blockers +is empty and the data-structure is then particularly sparse. +One famous example of clique-complex is the Rips complex which is intensively used +in topological data-analysis. +In practice, the set of blockers of a simplicial complex +remains also small when simplifying a Rips complex with edge contractions +but also for most of the simplicial complexes used in topological data-analysis such as Delaunay, Cech or Witness complexes. +For instance, the numbers of blockers is depicted for random 3 dimensional spheres embedded into \f$R^4\f$ +in figure X. + + +*\image html "blockers_curve.png" "Number of blockers of random triangulations of 3-spheres" width=10cm + + + + +\section API + +\subsection Overview + +Four classes are implemented for simplicial complex in this representation namely : + +\li Skeleton_blocker_complex : a simplicial complex with basic operations such as vertex/edge/simplex enumeration and construction +\li Skeleton_blocker_link_complex : the link of a simplex in a parent complex. It is represented as a sub complex +of the parent complex +\li Skeleton_blocker_simplifiable_complex : a simplicial complex with simplification operations such as edge contraction or simplex collapse +\li Skeleton_blocker_geometric_complex : a simplifiable simplicial complex who has access to geometric points in \f$R^d\f$ + +The two last classes are derived classes from the <Code>Skeleton_blocker_complex</Code> class. The class <Code>Skeleton_blocker_link_complex</Code> inheritates from a template passed parameter +that may be either <Code>Skeleton_blocker_complex</Code> or <Code>Skeleton_blocker_geometric_complex</Code> (a link may store points coordinates or not). +Most user will just need to use Skeleton_blocker_geometric_complex. + +\subsection Visitor + +The class <Code>Skeleton_blocker_complex</Code> 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 +<Code>Contraction</Code> package). + + + + +\section Example + + +\subsection s Iterating through vertices, edges, blockers and simplices + +Iteration through vertices, edges, simplices or blockers is straightforward with c++11 for range loops. +Note that simplex iteration with this implicit data-structure just takes +a few more time compared to iteration via an explicit representation +such as the Simplex Tree. The following example computes the Euler Characteristic +of a simplicial complex. + + \code{.cpp} + typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; + typedef Complex::Vertex_handle Vertex_handle; + typedef Complex::Simplex_handle 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++) + //note that add_edge adds the edge and all its cofaces + complex.add_edge(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.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 + + +\verbatim +./SkeletonBlockerIteration +Saw 15 vertices, 105 edges and 32767 simplices +The Euler Characteristic is 1 + 0.537302s wall, 0.530000s user + 0.000000s system = 0.530000s CPU (98.6%) +\endverbatim + + + +\subsection Acknowledgements +The author wishes to thank Dominique Attali and André Lieutier for +their collaboration to write the two initial papers about this data-structure + and also Dominique for leaving him use a prototype. + + +\copyright GNU General Public License v3. +\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim +*/ +/** @} */ // end defgroup + + + #endif + + diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h index 4475afcc..3afd4cc7 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h @@ -1,10 +1,24 @@ -/* - * ComplexVisitor.h - * - * Created on: Dec 11, 2013 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_COMPLEXVISITOR_H_ #define GUDHI_COMPLEXVISITOR_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h index 864ee6ac..4e1c5178 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h @@ -1,11 +1,24 @@ -/* - * Skeleton_blocker_link_superior.h - * - * Created on: Feb 19, 2014 - * Author: David Salinas - * Copyright 2013 INRIA. All rights reserved - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKER_LINK_SUPERIOR_H_ #define GUDHI_SKELETON_BLOCKER_LINK_SUPERIOR_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h index 369635e5..fd44fba5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -1,30 +1,24 @@ -/* - * Skeleton_blocker_off_io.h - * Created on: Nov 28, 2014 - * 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-Méditerranée (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 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/>. + */ #ifndef SKELETON_BLOCKER_OFF_IO_H_ #define SKELETON_BLOCKER_OFF_IO_H_ @@ -34,6 +28,9 @@ namespace Gudhi { namespace skbl { +/** + *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. + */ template<typename Complex> class Skeleton_blocker_off_visitor_reader{ Complex& complex_; @@ -71,6 +68,9 @@ public: } }; +/** +*@brief Class that allows to load a Skeleton_blocker_complex from an off file. +*/ template<typename Complex> class Skeleton_blocker_off_reader{ public: diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h index 79a8e7aa..a24bea25 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simple_geometric_traits.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_SIMPLE_GEOMETRIC_TRAITS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLE_GEOMETRIC_TRAITS_H_ @@ -16,8 +30,12 @@ namespace Gudhi{ namespace skbl{ + /** * @extends SkeletonBlockerGeometricDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerGeometricDS and + * can be passed as a template argument to Skeleton_blocker_geometric_complex */ template<typename GeometryTrait> struct Skeleton_blocker_simple_geometric_traits : public skbl::Skeleton_blocker_simple_traits { @@ -35,6 +53,7 @@ public: template<class ComplexGeometricTraits> friend class Skeleton_blocker_geometric_complex; private: Point point_; + Point& point(){ return point_; } const Point& point() const { return point_; } }; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h index 3975bb46..e17ea9b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simple_traits.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_SIMPLE_TRAITS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLE_TRAITS_H_ @@ -18,11 +32,14 @@ namespace skbl { /** * @extends SkeletonBlockerDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerDS and + * can be passed as a template argument to Skeleton_blocker_complex */ struct Skeleton_blocker_simple_traits{ /** - * @brief global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. - * In gross, vertices are stored in a vector. + * @brief Global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. + * Vertices are stored in a vector. * For the root simplicial complex, the local and global descriptors are the same. * For a subcomplex L and one of its vertices 'v', the local descriptor of 'v' is its position in * the vertex vector of the subcomplex L whereas its global descriptor is the position of 'v' diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h index 5593a5a8..fb3d9470 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -1,3 +1,25 @@ + /* 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/>. + */ + #ifndef GUDHI_SKELETON_BLOCKER_SIMPLEX_H #define GUDHI_SKELETON_BLOCKER_SIMPLEX_H diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index 5ca8e9af..9b4253d1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -1,3 +1,25 @@ + /* 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/>. + */ + #ifndef GUDHI_SKELETON_BLOCKER_SUB_COMPLEX_H #define GUDHI_SKELETON_BLOCKER_SUB_COMPLEX_H @@ -11,7 +33,7 @@ namespace skbl { /** * @brief Simplicial subcomplex of a complex represented by a skeleton/blockers pair. - * + * @extends Skeleton_blocker_complex * @details Stores a subcomplex of a simplicial complex. * To simplify explanations below, we will suppose that : * - K is the root simplicial complex @@ -136,13 +158,13 @@ public: * Constructs the restricted complex of 'parent_complex' to * vertices of 'simplex'. */ - friend void make_restricted_complex(const ComplexType & parent_complex, const Simplex_handle& simplex, Skeleton_blocker_sub_complex & result){ - result.clear(); + void make_restricted_complex(const ComplexType & parent_complex, const Simplex_handle& simplex){ + this->clear(); // add vertices to the sub complex for (auto x : simplex){ assert(parent_complex.contains_vertex(x)); - auto x_local = result.add_vertex(parent_complex[x].get_id()); - result[x_local] = parent_complex[x]; + auto x_local = this->add_vertex(parent_complex[x].get_id()); + (*this)[x_local] = parent_complex[x]; } // add edges to the sub complex @@ -152,7 +174,7 @@ public: parent_complex.add_neighbours(x, x_neigh, true); x_neigh.intersection(simplex); for (auto y : x_neigh){ - result.add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); + this->add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); } } @@ -161,8 +183,8 @@ public: // check if it is the first time we encounter the blocker if (simplex.contains(*blocker)){ Root_simplex_handle blocker_root(parent_complex.get_id(*(blocker))); - Simplex_handle blocker_restr(*result.get_simplex_address(blocker_root)); - result.add_blocker(new Simplex_handle(blocker_restr)); + Simplex_handle blocker_restr(*(this->get_simplex_address(blocker_root))); + this->add_blocker(new Simplex_handle(blocker_restr)); } } } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h index 0d870f1a..32538f38 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h @@ -1,10 +1,24 @@ -/* - * Top_faces.h - * - * Created on: Oct 23, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef TOP_FACES_H_ #define TOP_FACES_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h index 21091d10..f6f2c955 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_blockers_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h index 82025a1c..918e3473 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators_out.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ #define GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h index cf827705..20a94734 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h index 5ac0f21e..0681d5da 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_simplices_iterators.h - * - * Created on: Sep 26, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_KELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h index 4b66ced5..1fdbdfc9 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_triangles_iterators.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h index 875e915a..4c90ee51 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_iterators_out.h - * - * Created on: Aug 25, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ #define GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index b4c1cd9e..81ff0231 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -1,8 +1,23 @@ -/* - * Skeleton_blocker_complex.h +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. * - * Created on: Jan, 2014 - * Author: dsalinas + * 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/>. */ #ifndef GUDHI_SKELETON_BLOCKER_COMPLEX_H @@ -42,21 +57,7 @@ namespace skbl { /** *@class Skeleton_blocker_complex *@brief Abstract Simplicial Complex represented with a skeleton/blockers pair. - * - * A simplicial complex is completely defined by : - * - the graph of its 1-skeleton; - * - its set of blockers. - * - * The graph is a boost graph templated with SkeletonBlockerDS::Graph_vertex and SkeletonBlockerDS::Graph_edge. - * - * One can accesses to vertices via SkeletonBlockerDS::Vertex_handle, to edges via Skeleton_blocker_complex::Edge_handle and - * simplices via Skeleton_blocker_simplex<Vertex_handle>. - * - * The SkeletonBlockerDS::Root_vertex_handle serves in the case of a subcomplex (see class Skeleton_blocker_sub_complex) - * to access to the address of one vertex in the parent complex. - * - * @todo TODO Simplex_handle are not classic handle - * + *@ingroup skbl */ template<class SkeletonBlockerDS> class Skeleton_blocker_complex @@ -73,19 +74,35 @@ class Skeleton_blocker_complex public: - + /** + * @brief The type of stored vertex node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_vertex Graph_vertex; + + /** + * @brief The type of stored edge node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_edge Graph_edge; typedef typename SkeletonBlockerDS::Root_vertex_handle Root_vertex_handle; + + /** + * @brief The type of an handle to a vertex of the complex. + */ typedef typename SkeletonBlockerDS::Vertex_handle Vertex_handle; typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle; + /** + * @brief A ordered set of integers that represents a simplex. + */ typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; typedef Skeleton_blocker_simplex<Root_vertex_handle> Root_simplex_handle; + /** + * @brief Handle to a blocker of the complex. + */ typedef Simplex_handle* Blocker_handle; @@ -117,12 +134,12 @@ protected: public: /** - * Handle to an edge of the complex. + * @brief Handle to an edge of the complex. */ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle; - +protected: typedef std::multimap<Vertex_handle,Simplex_handle *> BlockerMap; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::value_type BlockerPair; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::iterator BlockerMapIterator; @@ -149,7 +166,6 @@ protected: //todo remove!!! -public: /** Each vertex can access to the blockers passing through it. */ BlockerMap blocker_map_; @@ -163,9 +179,12 @@ public: ///////////////////////////////////////////////////////////////////////////// - /** @name Constructors / Destructors / Initialization + /** @name Constructors, Destructors */ //@{ + /** + *@brief constructs a simplicial complex with a given number of vertices and a visitor. + */ Skeleton_blocker_complex(int num_vertices_ = 0,Visitor* visitor_=NULL):visitor(visitor_){ clear(); for (int i=0; i<num_vertices_; ++i){ @@ -277,10 +296,9 @@ private: public: /** - * @brief Constructor with a list of simplices + * @brief Constructor with a list of simplices. * @details The list of simplices must be the list - * of simplices of a simplicial complex. - *todo rewrite as iterators + * of simplices of a simplicial complex. */ Skeleton_blocker_complex(std::list<Simplex_handle>& simplices,Visitor* visitor_=NULL): num_vertices_(0),num_blockers_(0), @@ -315,7 +333,6 @@ public: } - // We cannot use the default copy constructor since we need // to make a copy of each of the blockers Skeleton_blocker_complex(const Skeleton_blocker_complex& copy){ @@ -331,6 +348,8 @@ public: } } +/** +*/ Skeleton_blocker_complex& operator=(const Skeleton_blocker_complex& copy){ clear(); visitor = NULL; @@ -354,7 +373,7 @@ public: } /** - * Clears the simplicial complex. After a call to this function, + * @details Clears the simplicial complex. After a call to this function, * blockers are destroyed. The 1-skeleton and the set of blockers * are both empty. */ @@ -371,6 +390,9 @@ public: skeleton.clear(); } +/** +*@brief allows to change the visitor. +*/ void set_visitor(Visitor* other_visitor){ visitor = other_visitor; } @@ -397,11 +419,19 @@ public: return *local; } + /** + * @brief Return the vertex node associated to local Vertex_handle. + * @remark Assume that the vertex is present in the complex. + */ Graph_vertex& operator[](Vertex_handle address){ assert(0<=address.vertex && address.vertex< boost::num_vertices(skeleton)); return skeleton[address.vertex]; } + /** + * @brief Return the vertex node associated to local Vertex_handle. + * @remark Assume that the vertex is present in the complex. + */ const Graph_vertex& operator[](Vertex_handle address) const{ assert(0<=address.vertex && address.vertex< boost::num_vertices(skeleton)); return skeleton[address.vertex]; @@ -425,7 +455,8 @@ public: /** * @brief Remove a vertex from the simplicial complex - * @remark In fact, it just deactivates the vertex. + * @remark It just deactivates the vertex with a boolean flag but does not + * remove it from vertices from complexity issues. */ void remove_vertex(Vertex_handle address){ assert(contains_vertex(address)); @@ -437,17 +468,15 @@ public: if (visitor) visitor->on_remove_vertex(address); } - /** - * @return true iff the simplicial complex contains the vertex u - */ +/** +*/ bool contains_vertex(Vertex_handle u) const{ if (u.vertex<0 || u.vertex>=boost::num_vertices(skeleton)) return false; return (*this)[u].is_active(); } - /** - * @return true iff the simplicial complex contains the vertex u - */ +/** +*/ bool contains_vertex(Root_vertex_handle u) const{ boost::optional<Vertex_handle> address = get_address(u); return address && (*this)[*address].is_active(); @@ -465,9 +494,8 @@ public: } /** - * Given an Id return the address of the vertex having this Id in the complex. - * For a simplicial complex, the address is the id but it may not be the case for a SubComplex. - * + * @brief Given an Id return the address of the vertex having this Id in the complex. + * @remark For a simplicial complex, the address is the id but it may not be the case for a SubComplex. */ virtual boost::optional<Vertex_handle> get_address(Root_vertex_handle id) const{ boost::optional<Vertex_handle> res; @@ -487,10 +515,14 @@ public: /** + * @brief Convert an address of a vertex of a complex to the address in + * the current complex. + * @details * If the current complex is a sub (or sup) complex of 'other', it converts * the address of a vertex v expressed in 'other' to the address of the vertex * v in the current one. - * @remark this methods uses Root_vertex_handle to identify the vertex + * @remark this methods uses Root_vertex_handle to identify the vertex and + * assumes the vertex is present in the current complex. */ Vertex_handle convert_handle_from_another_complex( const Skeleton_blocker_complex& other,Vertex_handle vh_in_other) const{ @@ -499,7 +531,9 @@ public: return *vh_in_current_complex; } - + /** + * @brief return the graph degree of a vertex. + */ int degree(Vertex_handle local) const{ assert(0<=local.vertex && local.vertex< boost::num_vertices(skeleton)); return degree_[local.vertex]; @@ -526,24 +560,40 @@ public: return res; } + /** + * @brief returns the stored node associated to an edge + */ Graph_edge& operator[](Edge_handle edge_handle){ return skeleton[edge_handle]; } + /** + * @brief returns the stored node associated to an edge + */ const Graph_edge& operator[](Edge_handle edge_handle) const{ return skeleton[edge_handle]; } + /** + * @brief returns the first vertex of an edge + * @details it assumes that the edge is present in the complex + */ Vertex_handle first_vertex(Edge_handle edge_handle) const{ return source(edge_handle,skeleton); } + /** + * @brief returns the first vertex of an edge + * @details it assumes that the edge is present in the complex + */ Vertex_handle second_vertex(Edge_handle edge_handle) const{ return target(edge_handle,skeleton); } /** * @brief returns the simplex made with the two vertices of the edge + * @details it assumes that the edge is present in the complex + */ Simplex_handle get_vertices(Edge_handle edge_handle) const{ auto edge((*this)[edge_handle]); @@ -551,7 +601,7 @@ public: } /** - * @brief Adds an edge between vertices a and b + * @brief Adds an edge between vertices a and b and all its cofaces. */ Edge_handle add_edge(Vertex_handle a, Vertex_handle b){ assert(contains_vertex(a) && contains_vertex(b)); @@ -573,7 +623,7 @@ public: } /** - * @brief Adds all edges of simplex sigma to the simplicial complex. + * @brief Adds all edges and their cofaces of a simplex to the simplicial complex. */ void add_edges(const Simplex_handle & sigma){ Simplex_handle_iterator i, j; @@ -583,7 +633,8 @@ public: } /** - * @brief Removes edge ab from the simplicial complex. + * @brief Removes an edge from the simplicial complex and all its cofaces. + * @details returns the former Edge_handle representing the edge */ virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b){ bool found; @@ -602,7 +653,7 @@ public: /** - * @brief Removes edge from the simplicial complex. + * @brief Removes edge and its cofaces from the simplicial complex. */ void remove_edge(Edge_handle edge){ assert(contains_vertex(first_vertex(edge))); @@ -660,23 +711,10 @@ public: /** @name Blockers operations */ //@{ - /** - * Adds the 2-blocker abc - */ - void add_blocker(Vertex_handle a, Vertex_handle b, Vertex_handle c){ - add_blocker(Simplex_handle(a,b,c)); - } /** - * Adds the 3-blocker abcd - */ - void add_blocker(Vertex_handle a, Vertex_handle b, Vertex_handle c, Vertex_handle d){ - add_blocker(Simplex_handle(a,b,c,d)); - } - - /** - * Adds the simplex blocker_pt to the set of blockers and - * returns a Blocker_handle toward it if was not present before. + * @brief Adds the simplex to the set of blockers and + * returns a Blocker_handle toward it if was not present before and 0 otherwise. */ Blocker_handle add_blocker(const Simplex_handle& blocker){ if (contains_blocker(blocker)) @@ -700,7 +738,7 @@ public: protected: /** - * Adds the simplex s to the set of blockers + * @brief Adds the simplex to the set of blockers */ void add_blocker(Blocker_handle blocker){ if (contains_blocker(*blocker)) @@ -744,8 +782,8 @@ protected: public: /** - * Removes the simplex sigma from the set of blockers. - * sigma has to belongs to the set of blockers + * @brief Removes the simplex from the set of blockers. + * @remark sigma has to belongs to the set of blockers */ void remove_blocker(const Blocker_handle sigma){ for (auto vertex : *sigma){ @@ -758,7 +796,7 @@ public: /** - * Remove all blockers, in other words, it expand the simplicial + * @brief Remove all blockers, in other words, it expand the simplicial * complex to the smallest flag complex that contains it. */ void remove_blockers(){ @@ -850,17 +888,9 @@ private: - - ///////////////////////////////////////////////////////////////////////////// - /** @name Neighbourhood access - */ - //@{ - -public: +protected: /** - * @brief Adds to simplex n the neighbours of v: - * \f$ n \leftarrow n \cup N(v) \f$. - * + * @details Adds to simplex the neighbours of v e.g. \f$ n \leftarrow n \cup N(v) \f$. * If keep_only_superior is true then only vertices that are greater than v are added. */ virtual void add_neighbours(Vertex_handle v, Simplex_handle & n,bool keep_only_superior=false) const{ @@ -876,34 +906,25 @@ public: } /** - * @brief Add to simplex res all vertices which are + * @details Add to simplex res all vertices which are * neighbours of alpha: ie \f$ res \leftarrow res \cup N(alpha) \f$. * * If 'keep_only_superior' is true then only vertices that are greater than alpha are added. - * * todo revoir * */ virtual void add_neighbours(const Simplex_handle &alpha, Simplex_handle & res,bool keep_only_superior=false) const{ res.clear(); - // ---------------------------- - // Compute vertices in the link - // we compute the intersection of N(alpha_i) and store it in n - // ---------------------------- auto alpha_vertex = alpha.begin(); add_neighbours(*alpha_vertex,res,keep_only_superior); for (alpha_vertex = (alpha.begin())++ ; alpha_vertex != alpha.end() ; ++alpha_vertex) - { keep_neighbours(*alpha_vertex,res,keep_only_superior); - } } /** - * @brief Eliminates from simplex n all vertices which are - * not neighbours of v: \f$ res \leftarrow res \cap N(v) \f$. - * + * @details Remove from simplex n all vertices which are + * not neighbours of v e.g. \f$ res \leftarrow res \cap N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are keeped. - * */ virtual void keep_neighbours(Vertex_handle v, Simplex_handle& res,bool keep_only_superior=false) const{ Simplex_handle nv; @@ -912,32 +933,26 @@ public: } /** - * @brief Eliminates from simplex n all vertices which are - * neighbours of v: \f$ res \leftarrow res \setminus N(v) \f$. - * + * @details Remove from simplex all vertices which are + * neighbours of v eg \f$ res \leftarrow res \setminus N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are added. - * */ virtual void remove_neighbours(Vertex_handle v, Simplex_handle & res,bool keep_only_superior=false) const{ Simplex_handle nv; add_neighbours(v,nv,keep_only_superior); res.difference(nv); } - //@} - ///////////////////////////////////////////////////////////////////////////// - /** @name Operations on the simplicial complex - */ - //@{ public: /** * @brief Compute the local vertices of 's' in the current complex * If one of them is not present in the complex then the return value is uninitialized. * - * xxx rename get_address et place un using dans sub_complex + * */ + //xxx rename get_address et place un using dans sub_complex boost::optional<Simplex_handle> get_simplex_address(const Root_simplex_handle& s) const { boost::optional<Simplex_handle> res; @@ -1002,8 +1017,9 @@ public: /* * @brief returns the number of edges in the complex. - * todo in O(n), cache the value + * @details currently in O(n) */ + // todo cache the value int num_edges() const{ return boost::num_edges(skeleton); } @@ -1031,22 +1047,6 @@ public: return boost::connected_components(this->skeleton,&component[0]) - num_vert_collapsed; } - - //todo remove - // do - void keep_only_largest_cc(){ - std::vector<unsigned> component(skeleton.vertex_set().size()); - boost::connected_components(this->skeleton,&component[0]); - auto maxCC = min_element(component.begin(),component.end()); - for (unsigned i = 0; i != component.size(); ++i){ - if(component[i]!=*maxCC){ - if(this->contains_vertex(Vertex_handle(i))) - this->remove_vertex(Vertex_handle(i)); - } - } - } - - /** * @brief %Test if the complex is a cone. * @details Runs in O(n) where n is the number of vertices. @@ -1154,6 +1154,7 @@ private: public: typedef Triangle_around_vertex_iterator<Skeleton_blocker_complex,Superior_link> Superior_triangle_around_vertex_iterator; + typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex,Link> > Complex_triangle_around_vertex_range; /** @@ -1222,6 +1223,9 @@ public: typedef boost::iterator_range < Complex_simplex_iterator > Complex_simplex_range; + /** + * @brief Returns a Complex_simplex_range over all the simplices of the complex + */ Complex_simplex_range simplex_range() const { Complex_simplex_iterator end(this,true); @@ -1264,7 +1268,9 @@ private: public: - + /** + * @brief Returns a range of the blockers of the complex passing through a vertex + */ Complex_blocker_around_vertex_range blocker_range(Vertex_handle v) { auto begin = Complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v)); @@ -1273,7 +1279,7 @@ public: } /** - * @brief Returns a Complex_blocker_around_vertex_range over all blockers of the complex adjacent to the vertex v. + * @brief Returns a range of the blockers of the complex passing through a vertex */ Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const { @@ -1309,7 +1315,9 @@ private: public: - + /** + * @brief Returns a range of the blockers of the complex + */ Complex_blocker_range blocker_range() { auto begin = Complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end() ); @@ -1317,7 +1325,9 @@ public: return Complex_blocker_range(begin,end); } - + /** + * @brief Returns a range of the blockers of the complex + */ Const_complex_blocker_range const_blocker_range() const { auto begin = Const_complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end() ); @@ -1339,6 +1349,7 @@ public: */ //@{ public: + std::string to_string() const{ std::ostringstream stream; stream<<num_vertices()<<" vertices:\n"<<vertices_to_string()<<std::endl; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h index 924b653c..4dbabd60 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_geometric_complex.h - * - * Created on: Feb 11, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ #define SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ @@ -22,7 +36,7 @@ namespace skbl { /** * @brief Class that represents a geometric complex that can be simplified. * The class allows access to points of vertices. - * + * @ingroup skbl */ template<typename SkeletonBlockerGeometricDS> class Skeleton_blocker_geometric_complex : public Skeleton_blocker_simplifiable_complex<SkeletonBlockerGeometricDS> @@ -46,9 +60,10 @@ public: /** * @brief Add a vertex to the complex with its associated point. */ - void add_vertex(const Point& point){ + Vertex_handle add_vertex(const Point& point){ Vertex_handle ad = SimplifiableSkeletonblocker::add_vertex(); (*this)[ad].point() = point; + return ad; } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h index 29c0691b..f3ebfa60 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blockers_link_complex.h - * - * Created on: Feb 7, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_LINK_COMPLEX_H_ #define GUDHI_SKELETON_BLOCKERS_LINK_COMPLEX_H_ @@ -22,6 +36,7 @@ template<class ComplexType> class Skeleton_blocker_sub_complex; * \brief Class representing the link of a simplicial complex encoded by a skeleton/blockers pair. * It inherits from Skeleton_blocker_sub_complex because such complex is a sub complex of a * root complex. + * \ingroup skbl */ template<typename ComplexType> class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex<ComplexType> diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 4f9060ef..1a51e709 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -1,10 +1,24 @@ -/* - * Skeleton_blocker_simplifiable_complex.h - * - * Created on: Feb 4, 2014 - * Author: dsalinas - */ - + /* 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/>. + */ #ifndef GUDHI_SKELETON_BLOCKERS_SIMPLIFIABLE_COMPLEX_H_ #define GUDHI_SKELETON_BLOCKERS_SIMPLIFIABLE_COMPLEX_H_ @@ -17,6 +31,8 @@ namespace skbl { /** * \brief Class that allows simplification operation on a simplicial complex represented * by a skeleton/blockers pair. + * \ingroup skbl + * @extends Skeleton_blocker_complex */ template<typename SkeletonBlockerDS> class Skeleton_blocker_simplifiable_complex : public Skeleton_blocker_complex<SkeletonBlockerDS> |