diff options
| -rw-r--r-- | src/Contraction/example/Rips_contraction.cpp | 63 | ||||
| -rw-r--r-- | src/Contraction/include/gudhi/Edge_contraction.h | 25 | ||||
| -rw-r--r-- | src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h | 15 | ||||
| -rw-r--r-- | src/common/doc/main_page.h | 4 |
4 files changed, 65 insertions, 42 deletions
diff --git a/src/Contraction/example/Rips_contraction.cpp b/src/Contraction/example/Rips_contraction.cpp index 869a3682..9d185f81 100644 --- a/src/Contraction/example/Rips_contraction.cpp +++ b/src/Contraction/example/Rips_contraction.cpp @@ -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 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/>. + */ #include <boost/timer/timer.hpp> #include <iostream> #include "gudhi/Edge_contraction.h" @@ -69,7 +69,6 @@ int main (int argc, char *argv[]) return -1; } - boost::timer::auto_cpu_timer t; Complex complex; // load the points @@ -78,14 +77,15 @@ int main (int argc, char *argv[]) std::cerr << "Unable to read file:"<<argv[1]<<std::endl; return EXIT_FAILURE; } - std::cout << "build the Rips complex"<<std::endl; + std::cout << "Build the Rips complex"<<std::endl; build_rips(complex,atof(argv[2])); + boost::timer::auto_cpu_timer t; std::cout << "Initial complex has "<< - complex.num_vertices()<<" vertices, and "<< - complex.num_edges()<<" edges."<<std::endl; + complex.num_vertices()<<" vertices and "<< + complex.num_edges()<<" edges"<<std::endl; Complex_contractor contractor(complex, new Edge_length_cost<Profile>, @@ -94,10 +94,17 @@ int main (int argc, char *argv[]) contraction::make_remove_popable_blockers_visitor<Profile>()); contractor.contract_edges(); - std::cout << "Resulting complex has "<< + std::cout << "Counting final number of simplices \n"; + unsigned num_simplices = std::distance(complex.simplex_range().begin(),complex.simplex_range().end()); + + std::cout << "Final complex has "<< complex.num_vertices()<<" vertices, "<< - complex.num_edges()<<" edges and "<< - complex.num_blockers()<<" blockers"<<std::endl; + complex.num_edges()<<" edges, "<< + complex.num_blockers()<<" blockers and "<< + num_simplices<<" simplices"<<std::endl; + + + std::cout << "Time to simplify and enumerate simplices:\n"; return EXIT_SUCCESS; } diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h index 895044ce..a8a342e6 100644 --- a/src/Contraction/include/gudhi/Edge_contraction.h +++ b/src/Contraction/include/gudhi/Edge_contraction.h @@ -33,6 +33,9 @@ #include "gudhi/Utils.h" +namespace Gudhi{ +namespace contraction{ + /** \defgroup contr Contraction @@ -41,7 +44,7 @@ \section Introduction The purpose of this package is to offer a user-friendly interface for edge contraction simplification of huge simplicial complexes. -It uses the Skeleton-Blocker data-structure whose size remains small during simplification +It uses the \ref skbl data-structure whose size remains small during simplification of most used geometrical complexes in topological data analysis such as the Rips or the Delaunay complexes (much lower than the total number of simplices in practice). The edge contraction operation consists in identifying two vertices of a simplicial complex. @@ -71,18 +74,29 @@ This class design is policy based and heavily inspired from the similar edge col Four policies can be customized in this package. \li Cost_policy: specify how much cost an edge contraction of a given edge. The edge with lowest cost is iteratively picked and contracted if valid. -\li Valid_policy: specify if a given edge contraction is valid. For instance, this policy can check the link condition which ensures that the homotopy type is preserved afer the edge contraction. -\li Placement: every time an edge is contracted, its points are merge to one point specified by this policy. This may be the middle of the edge of some more sofisticated point such as the minimum of a cost as in +\li Valid_contraction_policy: specify if a given edge contraction is valid. For instance, this policy can check the link condition which ensures that the homotopy type is preserved afer the edge contraction. +\li Placement_policy: every time an edge is contracted, its points are merge to one point specified by this policy. This may be the middle of the edge of some more sofisticated point such as the minimum of a cost as in \cite Garland. \subsection Visitor -A visitor which implements the class Contraction_visitor gets called when several +A visitor which implements the class Contraction_visitor gets called at several key moments +during the simplification: + +\li when the algorithms starts or ends +\li when an edge is seen for the first time +\li when an edge is considered for an edge contraction +\li before and after an edge is contracted + +This allows to implements most of edge contraction based algorithm with this +package. +\section Performance +TODO show curve CGAL \section Example @@ -183,6 +197,7 @@ int main (int argc, char *argv[]) */ /** @} */ // end defgroup - +} +} #endif /* GUDHI_EDGE_CONTRACTION_H_ */ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index b06c3513..7ea26190 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -34,7 +34,8 @@ #include "gudhi/Utils.h" //xxx - +namespace Gudhi{ +namespace skbl{ /** \defgroup skbl Skeleton-Blocker \author David Salinas @@ -101,15 +102,14 @@ 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). +The two last classes are derived classes from the Skeleton_blocker_complex class. The class Skeleton_blocker_link_complex inheritates from a template passed parameter +that may be either Skeleton_blocker_complex or Skeleton_blocker_geometric_complex (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). +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. @@ -189,7 +189,8 @@ their collaboration to write the two initial papers about this data-structure \verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim */ /** @} */ // end defgroup - +} +} #endif diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 8e361900..fd8f9046 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -23,10 +23,10 @@ for a detailed description of the design of the library. \section Compiling The library uses c++11 and requires Boost with version 1.48.0 or more recent : http://www.boost.org/. -The multi-field persistent homology algorithm has an optional dependency with GMP. +The multi-field persistent homology algorithm has a dependency with GMP and some demos requires CGAL https://www.cgal.org/. -The procedure to install these packages according to your operating system is +The procedure to install these libraries according to your operating system is detailled here http://doc.cgal.org/latest/Manual/installation.html The library compiles in Linux and Mac OSX. |