diff options
Diffstat (limited to 'src/Skeleton_blocker')
33 files changed, 2299 insertions, 2182 deletions
diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h index c0386590..d82425a0 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h @@ -1,20 +1,31 @@ -/* - * SkeletonBlockerDS.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: Feb 20, 2014 - * Author: David Salinas - * Copyright 2013 INRIA. All rights reserved + * 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 GUDHI_SKELETONBLOCKERDS_H_ -#define GUDHI_SKELETONBLOCKERDS_H_ - +#ifndef CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERDS_H_ +#define CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERDS_H_ namespace Gudhi { -namespace skbl { - - +namespace skeleton_blocker { /** \brief Concept for the template class passed for Skeleton_blocker_complex. * Most importantly, it contains the nodes for vertices and edges @@ -22,104 +33,97 @@ namespace skbl { * complex. The user can redefine these classes to attach * additional information to vertices and edges. */ -struct SkeletonBlockerDS -{ - /** - * @brief index that allows to find the vertex in the boost graph - */ - typedef int boost_vertex_handle; - - - /** - * @brief Root_vertex_handle and Vertex_handle are similar to global and local vertex descriptor - * used in <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a> - * and allow to localize a vertex of a subcomplex on its parent root complex. - * - * In gross, vertices are stored in a vector - * and the Root_vertex_handle and Vertex_handle store indices of a vertex in this vector. - * - * For the root simplicial complex, the Root_vertex_handle and Vertex_handle of a vertex - * are the same. - * - * - * For a subcomplex L of a simplicial complex K, the local descriptor, ie the Vertex_handle, of a - * vertex v (that belongs to L) is its position in the vector of vertices - * of the subcomplex L whereas its Root_vertex_handle (global descriptor) is the position of v in the vector of the - * vertices of the root simplicial complex K. - */ - struct Root_vertex_handle{ - - boost_vertex_handle vertex; - - friend ostream& operator << (ostream& o, const Root_vertex_handle & v); - }; - - /** - * A Vertex_handle must be Default Constructible, Assignable and Equality Comparable. - */ - struct Vertex_handle{ - boost_vertex_handle vertex; - - friend ostream& operator << (ostream& o, const Vertex_handle & v); - }; - - - /** - * \brief The type of vertices that are stored the boost graph. - * A Vertex must be Default Constructible and Equality Comparable. - * - */ - struct Graph_vertex{ - /** \brief Used to deactivate a vertex for example when contracting an edge. - * It allows in some cases to remove the vertex at low cost. - */ - void deactivate(); - - /** \brief Used to activate a vertex. - */ - void activate(); - - /** \brief Tells if the vertex is active. - */ - bool is_active() const; - - void set_id(Root_vertex_handle i); - Root_vertex_handle get_id() const; - virtual string to_string() const ; - friend ostream& operator << (ostream& o, const Graph_vertex & v); - }; - - - /** - * \brief The type of edges that are stored the boost graph. - * An Edge must be Default Constructible and Equality Comparable. - */ - struct Graph_edge{ - /** - * @brief Allows to modify vertices of the edge. - */ - void setId(Root_vertex_handle a,Root_vertex_handle b); - - /** - * @brief Returns the first vertex of the edge. - */ - Root_vertex_handle first() const ; - - /** - * @brief Returns the second vertex of the edge. - */ - Root_vertex_handle second() const ; - - friend ostream& operator << (ostream& o, const Simple_edge & v); - }; - - +struct SkeletonBlockerDS { + /** + * @brief index that allows to find the vertex in the boost graph + */ + typedef int boost_vertex_handle; + + /** + * @brief Root_vertex_handle and Vertex_handle are similar to global and local vertex descriptor + * used in <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a> + * and allow to localize a vertex of a subcomplex on its parent root complex. + * + * In gross, vertices are stored in a vector + * and the Root_vertex_handle and Vertex_handle store indices of a vertex in this vector. + * + * For the root simplicial complex, the Root_vertex_handle and Vertex_handle of a vertex + * are the same. + * + * + * For a subcomplex L of a simplicial complex K, the local descriptor, ie the Vertex_handle, of a + * vertex v (that belongs to L) is its position in the vector of vertices + * of the subcomplex L whereas its Root_vertex_handle (global descriptor) is the position of v in the vector of the + * vertices of the root simplicial complex K. + */ + struct Root_vertex_handle { + boost_vertex_handle vertex; + + friend ostream& operator<<(ostream& o, const Root_vertex_handle & v); + }; + + /** + * A Vertex_handle must be Default Constructible, Assignable and Equality Comparable. + */ + struct Vertex_handle { + boost_vertex_handle vertex; + + friend ostream& operator<<(ostream& o, const Vertex_handle & v); + }; + + /** + * \brief The type of vertices that are stored the boost graph. + * A Vertex must be Default Constructible and Equality Comparable. + * + */ + struct Graph_vertex { + /** \brief Used to deactivate a vertex for example when contracting an edge. + * It allows in some cases to remove the vertex at low cost. + */ + void deactivate(); + + /** \brief Used to activate a vertex. + */ + void activate(); + + /** \brief Tells if the vertex is active. + */ + bool is_active() const; + + void set_id(Root_vertex_handle i); + Root_vertex_handle get_id() const; + virtual string to_string() const; + friend ostream& operator<<(ostream& o, const Graph_vertex & v); + }; + + /** + * \brief The type of edges that are stored the boost graph. + * An Edge must be Default Constructible and Equality Comparable. + */ + struct Graph_edge { + /** + * @brief Allows to modify vertices of the edge. + */ + void setId(Root_vertex_handle a, Root_vertex_handle b); + + /** + * @brief Returns the first vertex of the edge. + */ + Root_vertex_handle first() const; + + /** + * @brief Returns the second vertex of the edge. + */ + Root_vertex_handle second() const; + + friend ostream& operator<<(ostream& o, const Simple_edge & v); + }; }; +} // namespace skeleton_blocker +namespace skbl = skeleton_blocker; -} // namespace skbl -} // namespace GUDHI - +} // namespace Gudhi -#endif /* GUDHI_SKELETONBLOCKERDS_H_ */ +#endif // CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERDS_H_ diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h index 8fbf0d12..477464c4 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h @@ -1,16 +1,30 @@ -/* - * SkeletonBlockerGeometricDS.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: Feb 20, 2014 - * Author: David Salinas - * Copyright 2013 INRIA. All rights reserved + * 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 GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ -#define GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ +#ifndef CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERGEOMETRICDS_H_ +#define CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERGEOMETRICDS_H_ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * \brief Concept for template class of Skeleton_blocker_geometric_complex . @@ -20,55 +34,57 @@ namespace skbl { * Graph_edge must specify how to access to an index. * */ - //todo the index is just for contraction, to remove -template<typename GeometryTrait> -struct SkeletonBlockerGeometricDS : public SkeletonBlockerDS -{ +// TODO(DS): the index is just for contraction, to remove - /** - * Geometry information. - */ - typedef GeometryTrait GT ; +template<typename GeometryTrait> +struct SkeletonBlockerGeometricDS : public SkeletonBlockerDS { + /** + * Geometry information. + */ + typedef GeometryTrait GT; - /** - * Type of point (should be the same as GT::Point). - */ - typedef typename GeometryTrait::Point Point; + /** + * Type of point (should be the same as GT::Point). + */ + typedef typename GeometryTrait::Point Point; - /** - * @brief Vertex that stores a point. - */ - class Graph_vertex : public SkeletonBlockerDS::Graph_vertex{ - public: - /** - * @brief Access to the point. - */ - Point& point(); - /** - * @brief Access to the point. - */ - const Point& point(); - }; + /** + * @brief Vertex that stores a point. + */ + class Graph_vertex : public SkeletonBlockerDS::Graph_vertex { + public: + /** + * @brief Access to the point. + */ + Point& point(); + /** + * @brief Access to the point. + */ + const Point& point(); + }; - /** - * @brief Edge that allows to access to an index. - * The indices of the edges are used to store heap information - * in the edge contraction algorithm. - */ - class Graph_Edge : public SkeletonBlockerDS::Graph_edge{ - public: - /** - * @brief Access to the index. - */ - int& index(); - /** - * @brief Access to the index. - */ - int index(); - }; + /** + * @brief Edge that allows to access to an index. + * The indices of the edges are used to store heap information + * in the edge contraction algorithm. + */ + class Graph_Edge : public SkeletonBlockerDS::Graph_edge { + public: + /** + * @brief Access to the index. + */ + int& index(); + /** + * @brief Access to the index. + */ + int index(); + }; }; -} // namespace skbl -} // namespace GUDHI +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi -#endif /* GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ */ +#endif // CONCEPT_SKELETON_BLOCKER_SKELETONBLOCKERGEOMETRICDS_H_ diff --git a/src/Skeleton_blocker/example/CMakeLists.txt b/src/Skeleton_blocker/example/CMakeLists.txt index de0c7bba..cc7f37f3 100644 --- a/src/Skeleton_blocker/example/CMakeLists.txt +++ b/src/Skeleton_blocker/example/CMakeLists.txt @@ -1,5 +1,5 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIskbl) +project(Skeleton_blocker_examples) add_executable(SkeletonBlockerFromSimplices Skeleton_blocker_from_simplices.cpp) add_executable(SkeletonBlockerIteration Skeleton_blocker_iteration.cpp) diff --git a/src/Skeleton_blocker/example/Skeleton_blocker_from_simplices.cpp b/src/Skeleton_blocker/example/Skeleton_blocker_from_simplices.cpp index 2738c01c..076c6a53 100644 --- a/src/Skeleton_blocker/example/Skeleton_blocker_from_simplices.cpp +++ b/src/Skeleton_blocker/example/Skeleton_blocker_from_simplices.cpp @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -29,30 +29,26 @@ #include <sstream> #include <vector> -using namespace std; -using namespace Gudhi; -using namespace skbl; - -typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_traits Traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_complex<Traits> Complex; typedef Complex::Vertex_handle Vertex_handle; -typedef Complex::Simplex_handle Simplex_handle; -typedef Complex::Simplex_handle Simplex; +typedef Complex::Simplex Simplex; int main(int argc, char *argv[]) { - std::vector<Simplex_handle> simplices; + std::vector<Simplex> simplices; // add 4 triangles of a tetrahedron 0123 - simplices.push_back(Simplex_handle(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3))); - simplices.push_back(Simplex_handle(Vertex_handle(3), Vertex_handle(0), Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(3), Vertex_handle(0), Vertex_handle(1))); + 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))); // get complex from top faces - Complex complex(make_complex_from_top_faces<Complex>(simplices.begin(), simplices.end())); + Complex complex(Gudhi::skeleton_blocker::make_complex_from_top_faces<Complex>(simplices.begin(), simplices.end())); std::cout << "Simplices:" << std::endl; - for (const Simplex & s : complex.simplex_range()) + for (const Simplex & s : complex.complex_simplex_range()) std::cout << s << " "; std::cout << std::endl; @@ -61,16 +57,16 @@ int main(int argc, char *argv[]) { // now build a complex from its full list of simplices simplices.clear(); - simplices.push_back(Simplex_handle(Vertex_handle(0))); - simplices.push_back(Simplex_handle(Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(0), Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(1), Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(2), Vertex_handle(0))); + 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.simplex_range()) + for (const Simplex & s : complex.complex_simplex_range()) std::cout << s << " "; std::cout << std::endl; diff --git a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp index 69557694..6a1bc480 100644 --- a/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp +++ b/src/Skeleton_blocker/example/Skeleton_blocker_iteration.cpp @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -30,14 +30,10 @@ #include <fstream> #include <sstream> - -using namespace std; -using namespace Gudhi; -using namespace skbl; - -typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_traits Traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_complex<Traits> Complex; typedef Complex::Vertex_handle Vertex_handle; -typedef Complex::Simplex_handle Simplex; +typedef Complex::Simplex Simplex; Complex build_complete_complex(int n) { // build a full complex with n vertices and 2^n-1 simplices @@ -46,8 +42,7 @@ Complex build_complete_complex(int n) { complex.add_vertex(); for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) - // note that add_edge, add the edge and all its cofaces - complex.add_edge(Vertex_handle(i), Vertex_handle(j)); + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); return complex; } @@ -77,7 +72,7 @@ int main(int argc, char *argv[]) { // 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()) { + for (const Simplex & s : complex.complex_simplex_range()) { ++num_simplices; if (s.dimension() % 2 == 0) euler += 1; diff --git a/src/Skeleton_blocker/example/Skeleton_blocker_link.cpp b/src/Skeleton_blocker/example/Skeleton_blocker_link.cpp index 002cbc49..58322038 100644 --- a/src/Skeleton_blocker/example/Skeleton_blocker_link.cpp +++ b/src/Skeleton_blocker/example/Skeleton_blocker_link.cpp @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -28,40 +28,42 @@ #include <fstream> #include <sstream> -using namespace std; -using namespace Gudhi; -using namespace skbl; - -typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_traits Traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_complex<Traits> Complex; typedef Complex::Vertex_handle Vertex_handle; typedef Complex::Root_vertex_handle Root_vertex_handle; -typedef Complex::Simplex_handle Simplex; +typedef Complex::Simplex Simplex; int main(int argc, char *argv[]) { // build a full complex with 4 vertices and 2^4-1 simplices - // Initial vertices are (0,1,2,3,4) - Simplex tetrahedron(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + + // Create a complex with four vertices (0,1,2,3) Complex complex; + + // Add a tetrahedron to this complex + Simplex tetrahedron(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); complex.add_simplex(tetrahedron); - cout << "complex:" << complex.to_string() << endl; + std::cout << "complex:" << complex.to_string() << std::endl; // build the link of vertex 1, eg a triangle {0,2,3} auto link = complex.link(Vertex_handle(1)); - cout << "link:" << link.to_string() << endl; + std::cout << "link:" << link.to_string() << std::endl; // Internally link is a subcomplex of 'complex' and its vertices are stored in a vector. // They can be accessed via Vertex_handle(x) where x is an index of the vector. // In that example, link has three vertices and thus it contains only // Vertex_handle(0),Vertex_handle(1) and Vertex_handle(2) are). for (int i = 0; i < 5; ++i) - cout << "link.contains_vertex(Vertex_handle(" << i << ")):" << link.contains_vertex(Vertex_handle(i)) << endl; - cout << endl; + std::cout << "link.contains_vertex(Vertex_handle(" << i << ")):" << link.contains_vertex(Vertex_handle(i)) << + std::endl; + std::cout << std::endl; // To access to the initial vertices eg (0,1,2,3,4), Root_vertex_handle must be used. // For instance, to test if the link contains the vertex that was labeled i: for (int i = 0; i < 5; ++i) - cout << "link.contains_vertex(Root_vertex_handle(" << i << ")):" << link.contains_vertex(Root_vertex_handle(i)) << endl; + std::cout << "link.contains_vertex(Root_vertex_handle(" << i << ")):" << + link.contains_vertex(Root_vertex_handle(i)) << std::endl; return EXIT_SUCCESS; } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 792a7994..32fe411c 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/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_ @@ -31,17 +31,18 @@ #include <gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h> -#include <gudhi/Utils.h> // xxx +#include <gudhi/Debug_utils.h> namespace Gudhi { -namespace skbl { +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,47 +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_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; + 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 @@ -182,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_handle> simplices; - - //add 4 triangles of a tetrahedron 0123 - simplices.push_back(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - simplices.push_back(Simplex_handle(Vertex_handle(3),Vertex_handle(0),Vertex_handle(2))); - simplices.push_back(Simplex_handle(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.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_handle(Vertex_handle(0))); - simplices.push_back(Simplex_handle(Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(0),Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(2),Vertex_handle(0))); - complex = Complex(simplices.begin(),simplices.end()); - - std::cout << "Simplices:"<<std::endl; - for(const Simplex & s : complex.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 @@ -237,15 +237,16 @@ 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. -\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim -*/ -/** @} */ // end defgroup +\copyright GNU General Public License v3. -} // namespace skbl +@} */ + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 72bdf4c9..ba3636bc 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ #define SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ @@ -26,8 +27,8 @@ namespace Gudhi { -namespace skbl { -// todo rajouter les const +namespace skeleton_blocker { +// TODO(DS): to be constified /** *@class Skeleton_blocker_complex_visitor @@ -36,12 +37,12 @@ namespace skbl { template<typename Vertex_handle> class Skeleton_blocker_complex_visitor { public: - virtual ~Skeleton_blocker_complex_visitor() {} + virtual ~Skeleton_blocker_complex_visitor() { } virtual void on_add_vertex(Vertex_handle) = 0; virtual void on_remove_vertex(Vertex_handle) = 0; - virtual void on_add_edge(Vertex_handle a, Vertex_handle b) = 0; + virtual void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) = 0; virtual void on_remove_edge(Vertex_handle a, Vertex_handle b) = 0; /** @@ -54,16 +55,16 @@ class Skeleton_blocker_complex_visitor { * @brief Called when performing an edge contraction when * an edge bx is replaced by an edge ax (not already present). * Precisely, this methods is called this way in contract_edge : - * add_edge(a,x) + * add_edge_without_blockers(a,x) * on_swaped_edge(a,b,x) * remove_edge(b,x) */ virtual void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) = 0; virtual void on_add_blocker( - const Skeleton_blocker_simplex<Vertex_handle>&) = 0; + const Skeleton_blocker_simplex<Vertex_handle>&) = 0; virtual void on_delete_blocker( - const Skeleton_blocker_simplex<Vertex_handle>*) = 0; + const Skeleton_blocker_simplex<Vertex_handle>*) = 0; }; /** @@ -73,24 +74,23 @@ class Skeleton_blocker_complex_visitor { */ template<typename Vertex_handle> class Dummy_complex_visitor : public Skeleton_blocker_complex_visitor< - Vertex_handle> { +Vertex_handle> { public: - void on_add_vertex(Vertex_handle) { - } - void on_remove_vertex(Vertex_handle) { - } - void on_add_edge(Vertex_handle a, Vertex_handle b) { - } - void on_remove_edge(Vertex_handle a, Vertex_handle b) { - } - void on_changed_edge(Vertex_handle a, Vertex_handle b) { - } - void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { - } - void on_add_blocker(const Skeleton_blocker_simplex<Vertex_handle>&) { - } - void on_delete_blocker(const Skeleton_blocker_simplex<Vertex_handle>*) { - } + void on_add_vertex(Vertex_handle) { } + + void on_remove_vertex(Vertex_handle) { } + + void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { } + + void on_remove_edge(Vertex_handle a, Vertex_handle b) { } + + void on_changed_edge(Vertex_handle a, Vertex_handle b) { } + + void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { } + + void on_add_blocker(const Skeleton_blocker_simplex<Vertex_handle>&) { } + + void on_delete_blocker(const Skeleton_blocker_simplex<Vertex_handle>*) { } }; /** @@ -100,35 +100,44 @@ class Dummy_complex_visitor : public Skeleton_blocker_complex_visitor< */ template<typename Vertex_handle> class Print_complex_visitor : public Skeleton_blocker_complex_visitor< - Vertex_handle> { +Vertex_handle> { public: void on_add_vertex(Vertex_handle v) { std::cerr << "on_add_vertex:" << v << std::endl; } + void on_remove_vertex(Vertex_handle v) { std::cerr << "on_remove_vertex:" << v << std::endl; } - void on_add_edge(Vertex_handle a, Vertex_handle b) { - std::cerr << "on_add_edge:" << a << "," << b << std::endl; + + void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { + std::cerr << "on_add_edge_without_blockers:" << a << "," << b << std::endl; } + void on_remove_edge(Vertex_handle a, Vertex_handle b) { std::cerr << "on_remove_edge:" << a << "," << b << std::endl; } + void on_changed_edge(Vertex_handle a, Vertex_handle b) { std::cerr << "on_changed_edge:" << a << "," << b << std::endl; } + void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { std::cerr << "on_swaped_edge:" << a << "," << b << "," << x << std::endl; } + void on_add_blocker(const Skeleton_blocker_simplex<Vertex_handle>& b) { std::cerr << "on_add_blocker:" << b << std::endl; } + void on_delete_blocker(const Skeleton_blocker_simplex<Vertex_handle>* b) { std::cerr << "on_delete_blocker:" << b << std::endl; } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 d39fa9f3..d4b60613 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SKELETON_BLOCKER_LINK_SUPERIOR_H_ #define SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ @@ -26,7 +27,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { template<class ComplexType> class Skeleton_blocker_sub_complex; @@ -36,7 +37,7 @@ template<class ComplexType> class Skeleton_blocker_sub_complex; */ template<typename ComplexType> class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< - ComplexType> { +ComplexType> { typedef typename ComplexType::Edge_handle Edge_handle; typedef typename ComplexType::boost_vertex_handle boost_vertex_handle; @@ -44,33 +45,32 @@ class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< public: typedef typename ComplexType::Vertex_handle Vertex_handle; typedef typename ComplexType::Root_vertex_handle Root_vertex_handle; - typedef typename ComplexType::Simplex_handle Simplex_handle; + typedef typename ComplexType::Simplex Simplex; typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; typedef typename ComplexType::BlockerMap BlockerMap; typedef typename ComplexType::BlockerPair BlockerPair; typedef typename ComplexType::BlockerMapIterator BlockerMapIterator; typedef typename ComplexType::BlockerMapConstIterator BlockerMapConstIterator; - typedef typename ComplexType::Simplex_handle::Simplex_vertex_const_iterator AddressSimplexConstIterator; + typedef typename ComplexType::Simplex::Simplex_vertex_const_iterator AddressSimplexConstIterator; typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator IdSimplexConstIterator; Skeleton_blocker_link_superior() - : Skeleton_blocker_link_complex<ComplexType>(true) { - } + : Skeleton_blocker_link_complex<ComplexType>(true) { } Skeleton_blocker_link_superior(const ComplexType & parent_complex, - Simplex_handle& alpha_parent_adress) + Simplex& alpha_parent_adress) : Skeleton_blocker_link_complex<ComplexType>(parent_complex, - alpha_parent_adress, true) { - } + alpha_parent_adress, true) { } Skeleton_blocker_link_superior(const ComplexType & parent_complex, Vertex_handle a_parent_adress) : Skeleton_blocker_link_complex<ComplexType>(parent_complex, - a_parent_adress, true) { - } + a_parent_adress, true) { } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 ec000986..747e60f1 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SKELETON_BLOCKER_OFF_IO_H_ #define SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ @@ -30,7 +31,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. @@ -49,8 +50,8 @@ class Skeleton_blocker_off_flag_visitor_reader { load_only_points_(load_only_points) { } void init(int dim, int num_vertices, int num_faces, int num_edges) { - // todo do an assert to check that this number are correctly read - // todo reserve size for vector points + // TODO(DS): do an assert to check that this number are correctly read + // TODO(DS): reserve size for vector points } void point(const std::vector<double>& point) { @@ -61,7 +62,7 @@ class Skeleton_blocker_off_flag_visitor_reader { if (!load_only_points_) { for (size_t i = 0; i < face.size(); ++i) for (size_t j = i + 1; j < face.size(); ++j) { - complex_.add_edge(Vertex_handle(face[i]), Vertex_handle(face[j])); + complex_.add_edge_without_blockers(Vertex_handle(face[i]), Vertex_handle(face[j])); } } } @@ -76,12 +77,12 @@ template<typename Complex> class Skeleton_blocker_off_visitor_reader { Complex& complex_; typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; typedef typename Complex::Point Point; const bool load_only_points_; std::vector<Point> points_; - std::vector<Simplex_handle> maximal_faces_; + std::vector<Simplex> maximal_faces_; public: explicit Skeleton_blocker_off_visitor_reader(Complex& complex, bool load_only_points = false) : @@ -99,7 +100,7 @@ class Skeleton_blocker_off_visitor_reader { void maximal_face(const std::vector<int>& face) { if (!load_only_points_) { - Simplex_handle s; + Simplex s; for (auto x : face) s.add_vertex(Vertex_handle(x)); maximal_faces_.emplace_back(s); @@ -108,7 +109,7 @@ class Skeleton_blocker_off_visitor_reader { void done() { complex_ = make_complex_from_top_faces<Complex>(maximal_faces_.begin(), maximal_faces_.end(), - points_.begin(), points_.end() ); + points_.begin(), points_.end()); } }; @@ -140,7 +141,7 @@ class Skeleton_blocker_off_reader { } /** - * return true iff reading did not meet problems. + * return true if reading did not meet problems. */ bool is_valid() const { return valid_; @@ -193,7 +194,9 @@ class Skeleton_blocker_off_writer { } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 8508d9a5..275376e6 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ #define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ @@ -29,7 +30,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * @extends SkeletonBlockerGeometricDS @@ -39,7 +40,7 @@ namespace skbl { */ template<typename GeometryTrait> struct Skeleton_blocker_simple_geometric_traits : - public skbl::Skeleton_blocker_simple_traits { +public Skeleton_blocker_simple_traits { public: typedef GeometryTrait GT; typedef typename GT::Point Point; @@ -57,19 +58,20 @@ struct Skeleton_blocker_simple_geometric_traits : Point& point() { return point_; } + const Point& point() const { return point_; } }; class Simple_geometric_edge : - public Skeleton_blocker_simple_traits::Graph_edge { + public Skeleton_blocker_simple_traits::Graph_edge { int index_; public: Simple_geometric_edge() : Skeleton_blocker_simple_traits::Graph_edge(), - index_(-1) { - } + index_(-1) { } + /** * @brief Allows to modify the index of the edge. * The indices of the edge are used to store heap information @@ -78,6 +80,7 @@ struct Skeleton_blocker_simple_geometric_traits : int& index() { return index_; } + int index() const { return index_; } @@ -87,7 +90,9 @@ struct Skeleton_blocker_simple_geometric_traits : typedef Skeleton_blocker_simple_traits::Graph_edge Graph_edge; }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 0d2de767..3835cf77 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ #define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ @@ -29,7 +30,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * @extends SkeletonBlockerDS @@ -48,9 +49,9 @@ struct Skeleton_blocker_simple_traits { */ struct Root_vertex_handle { typedef int boost_vertex_handle; + explicit Root_vertex_handle(boost_vertex_handle val = -1) - : vertex(val) { - } + : vertex(val) { } boost_vertex_handle vertex; bool operator!=(const Root_vertex_handle& other) const { @@ -65,8 +66,8 @@ struct Skeleton_blocker_simple_traits { return this->vertex < other.vertex; } - friend std::ostream& operator <<(std::ostream& o, - const Root_vertex_handle & v) { + friend std::ostream& operator<<(std::ostream& o, + const Root_vertex_handle & v) { o << v.vertex; return o; } @@ -74,11 +75,13 @@ struct Skeleton_blocker_simple_traits { struct Vertex_handle { typedef int boost_vertex_handle; + explicit Vertex_handle(boost_vertex_handle val = -1) - : vertex(val) { - } + : vertex(val) { } - operator int() const { return static_cast<int>(vertex); } + operator int() const { + return static_cast<int> (vertex); + } boost_vertex_handle vertex; @@ -94,7 +97,7 @@ struct Skeleton_blocker_simple_traits { return this->vertex < other.vertex; } - friend std::ostream& operator <<(std::ostream& o, const Vertex_handle & v) { + friend std::ostream& operator<<(std::ostream& o, const Vertex_handle & v) { o << v.vertex; return o; } @@ -105,21 +108,24 @@ struct Skeleton_blocker_simple_traits { Root_vertex_handle id_; public: - virtual ~Graph_vertex() { - } + virtual ~Graph_vertex() { } void activate() { is_active_ = true; } + void deactivate() { is_active_ = false; } + bool is_active() const { return is_active_; } + void set_id(Root_vertex_handle i) { id_ = i; } + Root_vertex_handle get_id() const { return id_; } @@ -130,7 +136,7 @@ struct Skeleton_blocker_simple_traits { return res.str(); } - friend std::ostream& operator <<(std::ostream& o, const Graph_vertex & v) { + friend std::ostream& operator<<(std::ostream& o, const Graph_vertex & v) { o << v.to_string(); return o; } @@ -144,13 +150,13 @@ struct Skeleton_blocker_simple_traits { public: Graph_edge() : a_(-1), - b_(-1), - index_(-1) { - } + b_(-1), + index_(-1) { } int& index() { return index_; } + int index() const { return index_; } @@ -168,14 +174,16 @@ struct Skeleton_blocker_simple_traits { return b_; } - friend std::ostream& operator <<(std::ostream& o, const Graph_edge & v) { + friend std::ostream& operator<<(std::ostream& o, const Graph_edge & v) { o << "(" << v.a_ << "," << v.b_ << " - id = " << v.index(); return o; } }; }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 0d838d50..aa6f2215 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -33,7 +33,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** *@brief Abstract simplex used in Skeleton blockers data-structure. @@ -63,7 +63,6 @@ class Skeleton_blocker_simplex { */ //@{ - // Skeleton_blocker_simplex():simplex_set() {} void clear() { simplex_set.clear(); } @@ -89,8 +88,7 @@ class Skeleton_blocker_simplex { add_vertex(v); } - void add_vertices() { - } + void add_vertices() { } /** * Initialize a simplex with a string such as {0,1,2} @@ -192,7 +190,6 @@ class Skeleton_blocker_simplex { return simplex_set.crend(); } - typename std::set<T>::iterator begin() { return simplex_set.begin(); } @@ -218,7 +215,7 @@ class Skeleton_blocker_simplex { } /** - * Returns the first vertex of the (oriented) simplex. + * Returns the first and smallest vertex of the simplex. * * Be careful : assumes the simplex is non-empty. */ @@ -228,7 +225,7 @@ class Skeleton_blocker_simplex { } /** - * Returns the last vertex of the (oriented) simplex. + * Returns the last and greatest vertex of the simplex. * * Be careful : assumes the simplex is non-empty. */ @@ -236,6 +233,7 @@ class Skeleton_blocker_simplex { assert(!empty()); return *(simplex_set.rbegin()); } + /** * @return true iff the simplex contains the simplex a. */ @@ -351,8 +349,8 @@ class Skeleton_blocker_simplex { //@} - friend std::ostream& operator <<(std::ostream& o, - const Skeleton_blocker_simplex & sigma) { + friend std::ostream& operator<<(std::ostream& o, + const Skeleton_blocker_simplex & sigma) { bool first = true; o << "{"; for (auto i : sigma) { @@ -367,7 +365,9 @@ class Skeleton_blocker_simplex { } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 b33b9606..fadf6619 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -25,14 +25,14 @@ #include <gudhi/Skeleton_blocker_complex.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> -#include <gudhi/Utils.h> +#include <gudhi/Debug_utils.h> #include <map> #include <vector> namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * @brief Simplicial subcomplex of a complex represented by a skeleton/blockers pair. @@ -66,12 +66,12 @@ class Skeleton_blocker_sub_complex : public ComplexType { public: using ComplexType::add_vertex; - using ComplexType::add_edge; + using ComplexType::add_edge_without_blockers; using ComplexType::add_blocker; typedef typename ComplexType::Vertex_handle Vertex_handle; typedef typename ComplexType::Root_vertex_handle Root_vertex_handle; - typedef typename ComplexType::Simplex_handle Simplex_handle; + typedef typename ComplexType::Simplex Simplex; typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; protected: @@ -109,11 +109,11 @@ class Skeleton_blocker_sub_complex : public ComplexType { * It assumes that both vertices corresponding to v1_root and v2_root are present * in the sub-complex. */ - void add_edge(Root_vertex_handle v1_root, Root_vertex_handle v2_root) { + void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root) { auto v1_sub(this->get_address(v1_root)); auto v2_sub(this->get_address(v2_root)); assert(v1_sub && v2_sub); - this->ComplexType::add_edge(*v1_sub, *v2_sub); + this->ComplexType::add_edge_without_blockers(*v1_sub, *v2_sub); } /** @@ -124,7 +124,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { void add_blocker(const Root_simplex_handle& blocker_root) { auto blocker_sub = this->get_address(blocker_root); assert(blocker_sub); - this->add_blocker(new Simplex_handle(*blocker_sub)); + this->add_blocker(new Simplex(*blocker_sub)); } public: @@ -133,7 +133,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { * vertices of 'simplex'. */ void make_restricted_complex(const ComplexType & parent_complex, - const Simplex_handle& simplex) { + const Simplex& simplex) { this->clear(); // add vertices to the sub complex for (auto x : simplex) { @@ -145,11 +145,11 @@ class Skeleton_blocker_sub_complex : public ComplexType { // add edges to the sub complex for (auto x : simplex) { // x_neigh is the neighbor of x intersected with vertices_simplex - Simplex_handle x_neigh; + Simplex x_neigh; parent_complex.add_neighbours(x, x_neigh, true); x_neigh.intersection(simplex); for (auto y : x_neigh) { - this->add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); + this->add_edge_without_blockers(parent_complex[x].get_id(), parent_complex[y].get_id()); } } @@ -158,9 +158,9 @@ class Skeleton_blocker_sub_complex : public ComplexType { // 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( - *(this->get_simplex_address(blocker_root))); - this->add_blocker(new Simplex_handle(blocker_restr)); + Simplex blocker_restr( + *(this->get_simplex_address(blocker_root))); + this->add_blocker(new Simplex(blocker_restr)); } } } @@ -188,16 +188,17 @@ class Skeleton_blocker_sub_complex : public ComplexType { // * Allocates a simplex in L corresponding to the simplex s in K // * with its local adresses and returns an AddressSimplex. // */ - // boost::optional<Simplex_handle> get_address(const Root_simplex_handle & s) const; + // boost::optional<Simplex> get_address(const Root_simplex_handle & s) const; -// private: + // private: /** * same as get_address except that it will return a simplex in any case. * The vertices that were not found are not added. */ // @remark should be private but problem with VS + std::vector<boost::optional<Vertex_handle> > get_addresses( - const Root_simplex_handle & s) const { + const Root_simplex_handle & s) const { std::vector < boost::optional<Vertex_handle> > res; for (auto i : s) { res.push_back(get_address(i)); @@ -214,14 +215,14 @@ class Skeleton_blocker_sub_complex : public ComplexType { */ template<typename ComplexType> bool proper_face_in_union( - Skeleton_blocker_sub_complex<ComplexType> & link, - std::vector<boost::optional<typename ComplexType::Vertex_handle> > & addresses_sigma_in_link, - int vertex_to_be_ignored) { + Skeleton_blocker_sub_complex<ComplexType> & link, + std::vector<boost::optional<typename ComplexType::Vertex_handle> > & addresses_sigma_in_link, + std::size_t vertex_to_be_ignored) { // we test that all vertices of 'addresses_sigma_in_link' but 'vertex_to_be_ignored' // are in link1 if it is the case we construct the corresponding simplex bool vertices_sigma_are_in_link = true; - typename ComplexType::Simplex_handle sigma_in_link; - for (int i = 0; i < addresses_sigma_in_link.size(); ++i) { + typename ComplexType::Simplex sigma_in_link; + for (std::size_t i = 0; i < addresses_sigma_in_link.size(); ++i) { if (i != vertex_to_be_ignored) { if (!addresses_sigma_in_link[i]) { vertices_sigma_are_in_link = false; @@ -236,43 +237,24 @@ bool proper_face_in_union( return vertices_sigma_are_in_link && link.contains(sigma_in_link); } -/* - template<typename ComplexType> - bool - proper_faces_in_union(Skeleton_blocker_simplex<typename ComplexType::Root_vertex_handle> & sigma, Skeleton_blocker_sub_complex<ComplexType> & link1, Skeleton_blocker_sub_complex<ComplexType> & link2) - { - typedef typename ComplexType::Vertex_handle Vertex_handle; - std::vector<boost::optional<Vertex_handle> > addresses_sigma_in_link1 = link1.get_addresses(sigma); - std::vector<boost::optional<Vertex_handle> > addresses_sigma_in_link2 = link2.get_addresses(sigma); - - for (int current_index = 0; current_index < addresses_sigma_in_link1.size(); ++current_index) - { - - if (!proper_face_in_union(link1, addresses_sigma_in_link1, current_index) - && !proper_face_in_union(link2, addresses_sigma_in_link2, current_index)){ - return false; - } - } - return true; - }*/ - // Remark: this function should be friend in order to leave get_adresses private // however doing so seemes currently not possible due to a visual studio bug c2668 // "the compiler does not support partial ordering of template functions as specified in the C++ Standard" // http://www.serkey.com/error-c2668-ambiguous-call-to-overloaded-function-bb45ft.html + template<typename ComplexType> bool proper_faces_in_union( - Skeleton_blocker_simplex<typename ComplexType::Root_vertex_handle> & sigma, - Skeleton_blocker_sub_complex<ComplexType> & link1, - Skeleton_blocker_sub_complex<ComplexType> & link2) { + Skeleton_blocker_simplex<typename ComplexType::Root_vertex_handle> & sigma, + Skeleton_blocker_sub_complex<ComplexType> & link1, + Skeleton_blocker_sub_complex<ComplexType> & link2) { typedef typename ComplexType::Vertex_handle Vertex_handle; std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link1 = link1.get_addresses(sigma); std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link2 = link2.get_addresses(sigma); - for (int current_index = 0; current_index < addresses_sigma_in_link1.size(); - ++current_index) { + for (std::size_t current_index = 0; current_index < addresses_sigma_in_link1.size(); + ++current_index) { if (!proper_face_in_union(link1, addresses_sigma_in_link1, current_index) && !proper_face_in_union(link2, addresses_sigma_in_link2, current_index)) { @@ -282,9 +264,10 @@ bool proper_faces_in_union( return true; } -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi #endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ - 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 eb970195..2b681752 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_INTERNAL_TOP_FACES_H_ #define SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ @@ -28,7 +29,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { template<typename SimplexHandle> std::list<SimplexHandle> subfaces(SimplexHandle top_face) { @@ -63,8 +64,10 @@ void register_faces(std::vector< std::set<SimplexHandle> >& simplices_per_dimens } } -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi -#endif // SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ +#endif // SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h index aa0416ef..2c9602fa 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * 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 @@ -21,7 +21,6 @@ * */ - #ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_ #define SKELETON_BLOCKER_INTERNAL_TRIE_H_ @@ -32,11 +31,11 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { template<typename SimplexHandle> struct Trie { - typedef SimplexHandle Simplex_handle; + typedef SimplexHandle Simplex; typedef typename SimplexHandle::Vertex_handle Vertex_handle; Vertex_handle v; @@ -64,7 +63,7 @@ struct Trie { } } - typedef typename Simplex_handle::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; + typedef typename Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; Trie* make_trie(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) { if (s_it == s_end) { @@ -97,7 +96,7 @@ struct Trie { return; } - void maximal_faces_helper(std::vector<Simplex_handle>& res) const { + void maximal_faces_helper(std::vector<Simplex>& res) const { if (is_leaf()) res.push_back(simplex()); else for (auto child : childs) @@ -108,14 +107,14 @@ struct Trie { /** * adds the simplex to the trie */ - void add_simplex(const Simplex_handle& s) { + void add_simplex(const Simplex& s) { if (s.empty()) return; assert(v == s.first_vertex()); add_simplex_helper(s.begin(), s.end()); } - std::vector<Simplex_handle> maximal_faces() const { - std::vector<Simplex_handle> res; + std::vector<Simplex> maximal_faces() const { + std::vector<Simplex> res; maximal_faces_helper(res); return res; } @@ -123,14 +122,14 @@ struct Trie { /** * Goes to the root in the trie to consitute simplex */ - void add_vertices_up_to_the_root(Simplex_handle& res) const { + void add_vertices_up_to_the_root(Simplex& res) const { res.add_vertex(v); if (parent_) parent_->add_vertices_up_to_the_root(res); } - Simplex_handle simplex() const { - Simplex_handle res; + Simplex simplex() const { + Simplex res; add_vertices_up_to_the_root(res); return res; } @@ -148,7 +147,7 @@ struct Trie { } void remove_leaf() { - assert(is_leaf); + assert(is_leaf()); if (!is_root()) parent_->childs.erase(this); } @@ -156,7 +155,7 @@ struct Trie { /** * true iff the simplex corresponds to one node in the trie */ - bool contains(const Simplex_handle& s) const { + bool contains(const Simplex& s) const { Trie const* current = this; if (s.empty()) return true; if (current->v != s.first_vertex()) return false; @@ -196,9 +195,9 @@ struct Trie { template<typename SimplexHandle> struct Tries { typedef typename SimplexHandle::Vertex_handle Vertex_handle; - typedef SimplexHandle Simplex_handle; + typedef SimplexHandle Simplex; - typedef Trie<Simplex_handle> STrie; + typedef Trie<Simplex> STrie; template<typename SimpleHandleOutputIterator> Tries(unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) : @@ -218,14 +217,14 @@ struct Tries { // return a simplex that consists in all u such uv is an edge and u>v - Simplex_handle positive_neighbors(Vertex_handle v) const { - Simplex_handle res; + Simplex positive_neighbors(Vertex_handle v) const { + Simplex res; for (auto child : cofaces_[v]->childs) res.add_vertex(child->v); return res; } - bool contains(const Simplex_handle& s) const { + bool contains(const Simplex& s) const { auto first_v = s.first_vertex(); return cofaces_[first_v]->contains(s); } @@ -238,9 +237,9 @@ struct Tries { // init_next_dimension must be called first - std::vector<Simplex_handle> next_dimension_simplices() const { - std::vector<Simplex_handle> res; - while (!to_see_.empty() && to_see_.front()->simplex().dimension() == current_dimension_) { + std::vector<Simplex> next_dimension_simplices() const { + std::vector<Simplex> res; + while (!(to_see_.empty()) && (to_see_.front()->simplex().dimension() == current_dimension_)) { res.emplace_back(to_see_.front()->simplex()); for (auto child : to_see_.front()->childs) to_see_.push_back(child.get()); @@ -257,11 +256,13 @@ struct Tries { private: mutable std::deque<STrie*> to_see_; - mutable unsigned current_dimension_ = 0; + mutable int current_dimension_ = 0; std::vector<STrie*> cofaces_; }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 56a20a24..d2fff960 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_ITERATORS_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ #define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ @@ -26,12 +27,12 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * @brief Iterator through the blockers of a vertex. */ -// ReturnType = const Simplex_handle* or Simplex_handle* +// ReturnType = const Simplex* or Simplex* // MapIteratorType = BlockerMapConstIterator or BlockerMapIterator template<typename MapIteratorType, typename ReturnType> @@ -83,7 +84,7 @@ ReturnType /** * @brief Iterator through the blockers of a vertex */ -// ReturnType = const Simplex_handle* or Simplex_handle* +// ReturnType = const Simplex* or Simplex* // MapIteratorType = BlockerMapConstIterator or BlockerMapIterator template<typename MapIteratorType, typename ReturnType> @@ -124,7 +125,9 @@ ReturnType } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 ef4c7970..b90dcf34 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_ITERATORS_SKELETON_BLOCKERS_EDGES_ITERATORS_H_ #define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_EDGES_ITERATORS_H_ @@ -29,7 +30,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { template<typename SkeletonBlockerComplex> class Edge_around_vertex_iterator : public boost::iterator_facade <Edge_around_vertex_iterator<SkeletonBlockerComplex> @@ -137,7 +138,9 @@ class Edge_iterator : public boost::iterator_facade <Edge_iterator<SkeletonBlock } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 cc3ed276..1351614f 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 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 4d71b3f5..2acdb555 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,13 +19,14 @@ * 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_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ #define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ #include <gudhi/Skeleton_blocker_link_complex.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h> #include <gudhi/Skeleton_blocker/internal/Trie.h> -#include <gudhi/Utils.h> +#include <gudhi/Debug_utils.h> #include <boost/iterator/iterator_facade.hpp> @@ -35,7 +36,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all @@ -48,30 +49,31 @@ namespace skbl { template<typename SkeletonBlockerComplex, typename Link> class Simplex_around_vertex_iterator : public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex > { friend class boost::iterator_core_access; typedef SkeletonBlockerComplex Complex; typedef typename Complex::Vertex_handle Vertex_handle; typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion typedef typename Link::Vertex_handle Link_vertex_handle; - typedef typename Gudhi::skbl::Trie<Simplex_handle> Trie; + typedef typename Gudhi::skeleton_blocker::Trie<Simplex> Trie; private: const Complex* complex; Vertex_handle v; std::shared_ptr<Link> link_v; std::shared_ptr<Trie> trie; - std::list<Trie*> nodes_to_be_seen; // todo deque + // TODO(DS): use a deque instead + std::list<Trie*> nodes_to_be_seen; public: - Simplex_around_vertex_iterator() : complex(0) {} + Simplex_around_vertex_iterator() : complex(0) { } Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) : complex(complex_), @@ -81,15 +83,16 @@ public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerCo compute_trie_and_nodes_to_be_seen(); } - // todo avoid useless copy - // todo currently just work if copy begin iterator + // TODO(DS): avoid useless copy + // TODO(DS): currently just work if copy begin iterator Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other) : complex(other.complex), v(other.v), link_v(other.link_v), trie(other.trie), nodes_to_be_seen(other.nodes_to_be_seen) { - if (!other.is_end()) {} + if (!other.is_end()) { + } } /** @@ -120,7 +123,7 @@ public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerCo Trie* res = new Trie(parent_vertex(link_vh), parent); for (Link_vertex_handle nv : link_v->vertex_range(link_vh)) { if (link_vh < nv) { - Simplex_handle simplex_node_plus_nv(res->simplex()); + Simplex simplex_node_plus_nv(res->simplex()); simplex_node_plus_nv.add_vertex(parent_vertex(nv)); if (complex->contains(simplex_node_plus_nv)) { res->add_child(build_trie(nv, res)); @@ -159,7 +162,8 @@ public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerCo bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); - if (!both_non_empty) return false; // one is empty the other is not + // one is empty the other is not + if (!both_non_empty) return false; bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); return same_node; @@ -176,13 +180,13 @@ public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerCo } } - Simplex_handle dereference() const { + Simplex dereference() const { assert(!nodes_to_be_seen.empty()); Trie* first_node = nodes_to_be_seen.front(); return first_node->simplex(); } - Simplex_handle get_trie_address() const { + Simplex get_trie_address() const { assert(!nodes_to_be_seen.empty()); return nodes_to_be_seen.front(); } @@ -200,9 +204,9 @@ public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerCo template<typename SkeletonBlockerComplex> class Simplex_iterator : public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex > { typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; @@ -213,7 +217,7 @@ public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> typedef SkeletonBlockerComplex Complex; typedef typename Complex::Vertex_handle Vertex_handle; typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; typedef typename Link::Vertex_handle Link_vertex_handle; @@ -238,7 +242,6 @@ public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> } private: - // todo return to private Simplex_iterator(const Complex* complex, bool end) : complex_(complex) { set_end(); @@ -290,7 +293,7 @@ public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> } } - Simplex_handle dereference() const { + Simplex dereference() const { return current_simplex_around_current_vertex_.dereference(); } @@ -304,7 +307,95 @@ public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> } }; -} // namespace skbl +/** + * Iterator through the maximal faces of the coboundary of a simplex. + */ +template<typename SkeletonBlockerComplex, typename Link> +class Simplex_coboundary_iterator : +public boost::iterator_facade < Simplex_coboundary_iterator<SkeletonBlockerComplex, Link> +, typename SkeletonBlockerComplex::Simplex, boost::forward_traversal_tag, typename SkeletonBlockerComplex::Simplex> { + friend class boost::iterator_core_access; + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex Simplex; + typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex; + const Simplex& sigma; + std::shared_ptr<Link> link; + Complex_vertex_iterator current_vertex; + Complex_vertex_iterator link_vertex_end; + + public: + Simplex_coboundary_iterator() : complex(0) { } + + Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_) : + complex(complex_), + sigma(sigma_), + // need only vertices of the link hence the true flag + link(new Link(*complex_, sigma_, false, true)) { + auto link_vertex_range = link->vertex_range(); + current_vertex = link_vertex_range.begin(); + link_vertex_end = link_vertex_range.end(); + } + + Simplex_coboundary_iterator(const Simplex_coboundary_iterator& other) : + complex(other.complex), + sigma(other.sigma), + link(other.link), + current_vertex(other.current_vertex), + link_vertex_end(other.link_vertex_end) { } + + // returns an iterator to the end + Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_, bool end) : + complex(complex_), + sigma(sigma_) { + // to represent an end iterator without having to build a useless link, we use + // the convection that link is not initialized. + } + + private: + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link, link_vh); + } + + public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_coboundary_iterator& sci) { + return stream; + } + + // assume that iterator points to the same complex and comes from the same simplex + bool equal(const Simplex_coboundary_iterator& other) const { + assert(complex == other.complex && sigma == other.sigma); + if (is_end()) return other.is_end(); + if (other.is_end()) return is_end(); + return *current_vertex == *(other.current_vertex); + } + + void increment() { + ++current_vertex; + } + + Simplex dereference() const { + Simplex res(sigma); + res.add_vertex(parent_vertex(*current_vertex)); + return res; + } + + private: + bool is_end() const { + return !link || current_vertex == link_vertex_end; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 28f5805d..736941dd 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_ITERATORS_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ #define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ @@ -27,7 +28,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * \brief Iterator over the triangles that are @@ -37,15 +38,15 @@ namespace skbl { template<typename Complex, typename LinkType> class Triangle_around_vertex_iterator : public boost::iterator_facade < Triangle_around_vertex_iterator <Complex, LinkType> -, typename Complex::Simplex_handle const +, typename Complex::Simplex const , boost::forward_traversal_tag -, typename Complex::Simplex_handle const> { +, typename Complex::Simplex const> { friend class boost::iterator_core_access; template<typename T> friend class Triangle_iterator; private: typedef typename LinkType::Vertex_handle Vertex_handle; typedef typename LinkType::Root_vertex_handle Root_vertex_handle; - typedef typename LinkType::Simplex_handle Simplex_handle; + typedef typename LinkType::Simplex Simplex; typedef typename Complex::Complex_edge_iterator Complex_edge_iterator_; const Complex* complex_; @@ -87,10 +88,10 @@ class Triangle_around_vertex_iterator : public boost::iterator_facade return (complex_ == other.complex_) && ((finished() && other.finished()) || current_edge_ == other.current_edge_); } - Simplex_handle dereference() const { + Simplex dereference() const { Root_vertex_handle v1 = (*link_)[*current_edge_].first(); Root_vertex_handle v2 = (*link_)[*current_edge_].second(); - return Simplex_handle(v_, *(complex_->get_address(v1)), *(complex_->get_address(v2))); + return Simplex(v_, *(complex_->get_address(v1)), *(complex_->get_address(v2))); } void increment() { @@ -112,14 +113,14 @@ class Triangle_around_vertex_iterator : public boost::iterator_facade template<typename SkeletonBlockerComplex> class Triangle_iterator : public boost::iterator_facade< Triangle_iterator <SkeletonBlockerComplex>, -typename SkeletonBlockerComplex::Simplex_handle const +typename SkeletonBlockerComplex::Simplex const , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle const> { +, typename SkeletonBlockerComplex::Simplex const> { friend class boost::iterator_core_access; private: typedef typename SkeletonBlockerComplex::Vertex_handle Vertex_handle; typedef typename SkeletonBlockerComplex::Root_vertex_handle Root_vertex_handle; - typedef typename SkeletonBlockerComplex::Simplex_handle Simplex_handle; + typedef typename SkeletonBlockerComplex::Simplex Simplex; typedef typename SkeletonBlockerComplex::Superior_triangle_around_vertex_iterator STAVI; typedef typename SkeletonBlockerComplex::Complex_vertex_iterator Complex_vertex_iterator; @@ -135,7 +136,7 @@ typename SkeletonBlockerComplex::Simplex_handle const Triangle_iterator(const SkeletonBlockerComplex* complex) : complex_(complex), current_vertex_(complex->vertex_range().begin()), - current_triangle_(complex, *current_vertex_), // xxx this line is problematic is the complex is empty + current_triangle_(complex, *current_vertex_), // this line is problematic is the complex is empty is_end_(false) { assert(!complex->empty()); gotoFirstTriangle(); @@ -172,10 +173,11 @@ typename SkeletonBlockerComplex::Simplex_handle const bool both_arent_finished = !is_finished() && !other.is_finished(); // if the two iterators are not finished, they must have the same state return (complex_ == other.complex_) && (both_are_finished || ((both_arent_finished) && - current_vertex_ == other.current_vertex_ && current_triangle_ == other.current_triangle_)); + current_vertex_ == other.current_vertex_ && + current_triangle_ == other.current_triangle_)); } - Simplex_handle dereference() const { + Simplex dereference() const { return *current_triangle_; } @@ -183,8 +185,10 @@ typename SkeletonBlockerComplex::Simplex_handle const // goto the next vertex that has a triangle pending or the // end vertex iterator if none exists void goto_next_vertex() { - assert(current_triangle_.finished()); // we mush have consume all triangles passing through the vertex - assert(!is_finished()); // we must not be done + // we must have consume all triangles passing through the vertex + assert(current_triangle_.finished()); + // we must not be done + assert(!is_finished()); ++current_vertex_; @@ -213,7 +217,9 @@ typename SkeletonBlockerComplex::Simplex_handle const } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 14ae136a..9e9ae961 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 @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ #define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ @@ -28,7 +29,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** *@brief Iterator on the vertices of a simplicial complex @@ -103,7 +104,7 @@ class Vertex_iterator : public boost::iterator_facade< Vertex_iterator <Skeleton }; template<typename SkeletonBlockerComplex> -class Neighbors_vertices_iterator: public boost::iterator_facade < Neighbors_vertices_iterator<SkeletonBlockerComplex> +class Neighbors_vertices_iterator : public boost::iterator_facade < Neighbors_vertices_iterator<SkeletonBlockerComplex> , typename SkeletonBlockerComplex::Vertex_handle const , boost::forward_traversal_tag , typename SkeletonBlockerComplex::Vertex_handle const> { @@ -122,9 +123,6 @@ class Neighbors_vertices_iterator: public boost::iterator_facade < Neighbors_ver boost_adjacency_iterator end_; public: - // boost_adjacency_iterator ai, ai_end; - // for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end; ++ai) { - Neighbors_vertices_iterator() : complex(NULL) { } Neighbors_vertices_iterator(const Complex* complex_, Vertex_handle v_) : @@ -157,16 +155,16 @@ class Neighbors_vertices_iterator: public boost::iterator_facade < Neighbors_ver } private: - // todo remove this ugly hack + // TODO(DS): remove this ugly hack void set_end() { current_ = end_; } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi #endif // SKELETON_BLOCKER_ITERATORS_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 07f371a2..4f052ba5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -28,12 +28,10 @@ #include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> - #include <gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h> #include <gudhi/Skeleton_blocker/internal/Top_faces.h> #include <gudhi/Skeleton_blocker/internal/Trie.h> - -#include <gudhi/Utils.h> +#include <gudhi/Debug_utils.h> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> @@ -54,7 +52,7 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** *@class Skeleton_blocker_complex @@ -94,16 +92,16 @@ class Skeleton_blocker_complex { /** * @brief A ordered set of integers that represents a simplex. */ - typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; + typedef Skeleton_blocker_simplex<Vertex_handle> Simplex; typedef Skeleton_blocker_simplex<Root_vertex_handle> Root_simplex_handle; /** * @brief Handle to a blocker of the complex. */ - typedef Simplex_handle* Blocker_handle; + typedef Simplex* Blocker_handle; typedef typename Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_iterator; - typedef typename Simplex_handle::Simplex_vertex_const_iterator Simplex_handle_iterator; + typedef typename Simplex::Simplex_vertex_const_iterator Simplex_handle_iterator; protected: typedef typename boost::adjacency_list<boost::setS, // edges @@ -128,14 +126,14 @@ class Skeleton_blocker_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; - typedef typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator BlockerMapConstIterator; + typedef std::multimap<Vertex_handle, Simplex *> BlockerMap; + typedef typename std::multimap<Vertex_handle, Simplex *>::value_type BlockerPair; + typedef typename std::multimap<Vertex_handle, Simplex *>::iterator BlockerMapIterator; + typedef typename std::multimap<Vertex_handle, Simplex *>::const_iterator BlockerMapConstIterator; protected: - int num_vertices_; - int num_blockers_; + size_t num_vertices_; + size_t num_blockers_; typedef Skeleton_blocker_complex_visitor<Vertex_handle> Visitor; // typedef Visitor* Visitor_ptr; @@ -164,17 +162,17 @@ class Skeleton_blocker_complex { /** *@brief constructs a simplicial complex with a given number of vertices and a visitor. */ - explicit Skeleton_blocker_complex(int num_vertices_ = 0, Visitor* visitor_ = NULL) + explicit Skeleton_blocker_complex(size_t num_vertices_ = 0, Visitor* visitor_ = NULL) : visitor(visitor_) { clear(); - for (int i = 0; i < num_vertices_; ++i) { + for (size_t i = 0; i < num_vertices_; ++i) { add_vertex(); } } private: // typedef Trie<Skeleton_blocker_complex<SkeletonBlockerDS>> STrie; - typedef Trie<Simplex_handle> STrie; + typedef Trie<Simplex> STrie; public: /** @@ -182,37 +180,40 @@ class Skeleton_blocker_complex { * @details is_flag_complex indicates if the complex is a flag complex or not (to know if blockers have to be computed or not). */ template<typename SimpleHandleOutputIterator> - Skeleton_blocker_complex(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end, + Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end, bool is_flag_complex = false, Visitor* visitor_ = NULL) : num_vertices_(0), num_blockers_(0), visitor(visitor_) { - add_vertex_and_edges(simplex_begin, simplex_end); + add_vertices_and_edges(simplices_begin, simplices_end); if (!is_flag_complex) // need to compute blockers - add_blockers(simplex_begin, simplex_end); + add_blockers(simplices_begin, simplices_end); } private: + /** + * Add vertices and edges of a simplex in one pass + */ template<typename SimpleHandleOutputIterator> - void add_vertex_and_edges(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) { + void add_vertices_and_edges(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) { std::vector<std::pair<Vertex_handle, Vertex_handle>> edges; // first pass to add vertices and edges int num_vertex = -1; - for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) { + for (auto s_it = simplices_begin; s_it != simplices_end; ++s_it) { if (s_it->dimension() == 0) num_vertex = (std::max)(num_vertex, s_it->first_vertex().vertex); if (s_it->dimension() == 1) edges.emplace_back(s_it->first_vertex(), s_it->last_vertex()); } while (num_vertex-- >= 0) add_vertex(); for (const auto& e : edges) - add_edge(e.first, e.second); + add_edge_without_blockers(e.first, e.second); } template<typename SimpleHandleOutputIterator> - void add_blockers(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) { - Tries<Simplex_handle> tries(num_vertices(), simplex_begin, simplex_end); + void add_blockers(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) { + Tries<Simplex> tries(num_vertices(), simplices_begin, simplices_end); tries.init_next_dimension(); auto simplices(tries.next_dimension_simplices()); @@ -221,7 +222,7 @@ class Skeleton_blocker_complex { for (auto& sigma : simplices) { // common_positive_neighbors is the set of vertices u such that // for all s in sigma, us is an edge and u>s - Simplex_handle common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex())); + Simplex common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex())); for (auto sigma_it = sigma.rbegin(); sigma_it != sigma.rend(); ++sigma_it) if (sigma_it != sigma.rbegin()) common_positive_neighbors.intersection(tries.positive_neighbors(*sigma_it)); @@ -378,6 +379,7 @@ class Skeleton_blocker_complex { /** * @brief Adds a vertex to the simplicial complex and returns its Vertex_handle. + * @remark Vertex representation is contiguous. */ Vertex_handle add_vertex() { Vertex_handle address(boost::add_vertex(skeleton)); @@ -411,7 +413,8 @@ class Skeleton_blocker_complex { /** */ bool contains_vertex(Vertex_handle u) const { - if (u.vertex < 0 || u.vertex >= boost::num_vertices(skeleton)) + Vertex_handle num_vertices(boost::num_vertices(skeleton)); + if (u.vertex < 0 || u.vertex >= num_vertices) return false; return (*this)[u].is_active(); } @@ -427,7 +430,7 @@ class Skeleton_blocker_complex { * @return true iff the simplicial complex contains all vertices * of simplex sigma */ - bool contains_vertices(const Simplex_handle & sigma) const { + bool contains_vertices(const Simplex & sigma) const { for (auto vertex : sigma) if (!contains_vertex(vertex)) return false; @@ -438,11 +441,11 @@ class Skeleton_blocker_complex { * @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 { + virtual boost::optional<Vertex_handle> get_address(Root_vertex_handle id) const { boost::optional<Vertex_handle> res; - if (id.vertex < boost::num_vertices(skeleton)) - res = Vertex_handle(id.vertex); // xxx + int num_vertices = boost::num_vertices(skeleton); + if (id.vertex < num_vertices) + res = Vertex_handle(id.vertex); return res; } @@ -535,41 +538,67 @@ class Skeleton_blocker_complex { * @details it assumes that the edge is present in the complex */ - Simplex_handle get_vertices(Edge_handle edge_handle) const { + Simplex get_vertices(Edge_handle edge_handle) const { auto edge((*this)[edge_handle]); - return Simplex_handle((*this)[edge.first()], (*this)[edge.second()]); + return Simplex((*this)[edge.first()], (*this)[edge.second()]); } /** - * @brief Adds an edge between vertices a and b and all its cofaces. + * @brief Adds an edge between vertices a and b. + * @details For instance, the complex contains edge 01 and 12, then calling + * add_edge with vertex 0 and 2 will create a complex containing + * the edges 01, 12, 20 but not the triangle 012 (and hence this complex + * will contains a blocker 012). */ Edge_handle add_edge(Vertex_handle a, Vertex_handle b) { + // if the edge is already there we musnt go further + // as we may add blockers that should not be here + if (contains_edge(a, b)) + return *((*this)[std::make_pair(a, b)]); + auto res = add_edge_without_blockers(a, b); + add_blockers_after_simplex_insertion(Simplex(a, b)); + return res; + } + + /** + * @brief Adds all edges of s in the complex. + */ + void add_edge(const Simplex& s) { + for (auto i = s.begin(); i != s.end(); ++i) + for (auto j = i; ++j != s.end(); /**/) + add_edge(*i, *j); + } + + /** + * @brief Adds an edge between vertices a and b without blockers. + * @details For instance, the complex contains edge 01 and 12, then calling + * add_edge with vertex 0 and 2 will create a complex containing + * the triangle 012. + */ + Edge_handle add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { assert(contains_vertex(a) && contains_vertex(b)); assert(a != b); auto edge_handle((*this)[std::make_pair(a, b)]); - // std::pair<Edge_handle,bool> pair_descr_bool = (*this)[std::make_pair(a,b)]; - // Edge_handle edge_descr; - // bool edge_present = pair_descr_bool.second; if (!edge_handle) { edge_handle = boost::add_edge(a.vertex, b.vertex, skeleton).first; (*this)[*edge_handle].setId(get_id(a), get_id(b)); degree_[a.vertex]++; degree_[b.vertex]++; if (visitor) - visitor->on_add_edge(a, b); + visitor->on_add_edge_without_blockers(a, b); } return *edge_handle; } /** - * @brief Adds all edges and their cofaces of a simplex to the simplicial complex. + * @brief Adds all edges of s in the complex without adding blockers. */ - void add_edges(const Simplex_handle & sigma) { - Simplex_handle_iterator i, j; - for (i = sigma.begin(); i != sigma.end(); ++i) - for (j = i, j++; j != sigma.end(); ++j) - add_edge(*i, *j); + void add_edge_without_blockers(Simplex s) { + for (auto i = s.begin(); i != s.end(); ++i) { + for (auto j = i; ++j != s.end(); /**/) + add_edge_without_blockers(*i, *j); + } } /** @@ -627,7 +656,7 @@ class Skeleton_blocker_complex { * @return true iff the simplicial complex contains all vertices * and all edges of simplex sigma */ - bool contains_edges(const Simplex_handle & sigma) const { + bool contains_edges(const Simplex & sigma) const { for (auto i = sigma.begin(); i != sigma.end(); ++i) { if (!contains_vertex(*i)) return false; @@ -649,15 +678,14 @@ class Skeleton_blocker_complex { * @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) { + Blocker_handle add_blocker(const Simplex& blocker) { assert(blocker.dimension() > 1); if (contains_blocker(blocker)) { - // std::cerr << "ATTEMPT TO ADD A BLOCKER ALREADY THERE ---> BLOCKER IGNORED" << endl; return 0; } else { if (visitor) visitor->on_add_blocker(blocker); - Blocker_handle blocker_pt = new Simplex_handle(blocker); + Blocker_handle blocker_pt = new Simplex(blocker); num_blockers_++; auto vertex = blocker_pt->begin(); while (vertex != blocker_pt->end()) { @@ -739,7 +767,7 @@ class Skeleton_blocker_complex { * * @remark contrarily to delete_blockers does not call the destructor */ - void remove_blocker(const Simplex_handle& sigma) { + void remove_blocker(const Simplex& sigma) { assert(contains_blocker(sigma)); for (auto vertex : sigma) remove_blocker(sigma, vertex); @@ -777,7 +805,7 @@ class Skeleton_blocker_complex { /** * @return true iff s is a blocker of the simplicial complex */ - bool contains_blocker(const Simplex_handle & s) const { + bool contains_blocker(const Simplex & s) const { if (s.dimension() < 2) return false; @@ -795,7 +823,7 @@ class Skeleton_blocker_complex { * @return true iff a blocker of the simplicial complex * is a face of sigma. */ - bool blocks(const Simplex_handle & sigma) const { + bool blocks(const Simplex & sigma) const { for (auto s : sigma) for (auto blocker : const_blocker_range(s)) if (sigma.contains(*blocker)) @@ -810,17 +838,18 @@ class Skeleton_blocker_complex { * @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, + virtual void add_neighbours(Vertex_handle v, Simplex & n, bool keep_only_superior = false) const { boost_adjacency_iterator ai, ai_end; for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end; ++ai) { + Vertex_handle value(*ai); if (keep_only_superior) { - if (*ai > v.vertex) { - n.add_vertex(Vertex_handle(*ai)); + if (value > v.vertex) { + n.add_vertex(value); } } else { - n.add_vertex(Vertex_handle(*ai)); + n.add_vertex(value); } } } @@ -833,7 +862,7 @@ class Skeleton_blocker_complex { * todo revoir * */ - virtual void add_neighbours(const Simplex_handle &alpha, Simplex_handle & res, + virtual void add_neighbours(const Simplex &alpha, Simplex & res, bool keep_only_superior = false) const { res.clear(); auto alpha_vertex = alpha.begin(); @@ -848,9 +877,9 @@ class Skeleton_blocker_complex { * 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, + virtual void keep_neighbours(Vertex_handle v, Simplex& res, bool keep_only_superior = false) const { - Simplex_handle nv; + Simplex nv; add_neighbours(v, nv, keep_only_superior); res.intersection(nv); } @@ -860,9 +889,9 @@ class Skeleton_blocker_complex { * 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, + virtual void remove_neighbours(Vertex_handle v, Simplex & res, bool keep_only_superior = false) const { - Simplex_handle nv; + Simplex nv; add_neighbours(v, nv, keep_only_superior); res.difference(nv); } @@ -874,7 +903,7 @@ class Skeleton_blocker_complex { * Constructs the link of 'simplex' with points coordinates. */ Link_complex link(Vertex_handle v) const { - return Link_complex(*this, Simplex_handle(v)); + return Link_complex(*this, Simplex(v)); } /** @@ -887,7 +916,7 @@ class Skeleton_blocker_complex { /** * Constructs the link of 'simplex' with points coordinates. */ - Link_complex link(const Simplex_handle& simplex) const { + Link_complex link(const Simplex& simplex) const { return Link_complex(*this, simplex); } @@ -899,11 +928,11 @@ class Skeleton_blocker_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; + boost::optional<Simplex> get_simplex_address( + const Root_simplex_handle& s) const { + boost::optional<Simplex> res; - Simplex_handle s_address; + Simplex s_address; // Root_simplex_const_iterator i; for (auto i = s.begin(); i != s.end(); ++i) { boost::optional<Vertex_handle> address = get_address(*i); @@ -920,7 +949,7 @@ class Skeleton_blocker_complex { * @brief returns a simplex with vertices which are the id of vertices of the * argument. */ - Root_simplex_handle get_id(const Simplex_handle& local_simplex) const { + Root_simplex_handle get_id(const Simplex& local_simplex) const { Root_simplex_handle global_simplex; for (auto x = local_simplex.begin(); x != local_simplex.end(); ++x) { global_simplex.add_vertex(get_id(*x)); @@ -932,7 +961,7 @@ class Skeleton_blocker_complex { * @brief returns true iff the simplex s belongs to the simplicial * complex. */ - virtual bool contains(const Simplex_handle & s) const { + virtual bool contains(const Simplex & s) const { if (s.dimension() == -1) { return false; } else if (s.dimension() == 0) { @@ -973,9 +1002,29 @@ class Skeleton_blocker_complex { } /* + * @brief returns the number of simplices of a given dimension in the complex. + */ + size_t num_simplices() const { + auto simplices = complex_simplex_range(); + return std::distance(simplices.begin(), simplices.end()); + } + + /* + * @brief returns the number of simplices of a given dimension in the complex. + */ + size_t num_simplices(int dimension) const { + // TODO(DS): iterator on k-simplices + size_t res = 0; + for (const auto& s : complex_simplex_range()) + if (s.dimension() == dimension) + ++res; + return res; + } + + /* * @brief returns the number of blockers in the complex. */ - int num_blockers() const { + size_t num_blockers() const { return num_blockers_; } @@ -1018,7 +1067,7 @@ class Skeleton_blocker_complex { } //@} - /** @Simplification operations + /** @name Simplification operations */ //@{ @@ -1061,7 +1110,7 @@ class Skeleton_blocker_complex { * Furthermore, all simplices tau of the form sigma \setminus simplex_to_be_removed must be added * whenever the dimension of tau is at least 2. */ - void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex_handle& simplex_to_be_removed); + void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed); public: /** @@ -1078,31 +1127,33 @@ class Skeleton_blocker_complex { /** * Remove the star of the simplex 'sigma' which needs to belong to the complex */ - void remove_star(const Simplex_handle& sigma); + void remove_star(const Simplex& sigma); /** - * @brief add a maximal simplex plus all its cofaces. - * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge). + * @brief add a simplex and all its faces. + * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge_without_blockers). */ - void add_simplex(const Simplex_handle& sigma); + void add_simplex(const Simplex& sigma); private: + void add_blockers_after_simplex_insertion(Simplex s); + /** * remove all blockers that contains sigma */ - void remove_blocker_containing_simplex(const Simplex_handle& sigma); + void remove_blocker_containing_simplex(const Simplex& sigma); /** * remove all blockers that contains sigma */ - void remove_blocker_include_in_simplex(const Simplex_handle& sigma); + void remove_blocker_include_in_simplex(const Simplex& sigma); public: enum simplifiable_status { NOT_HOMOTOPY_EQ, MAYBE_HOMOTOPY_EQ, HOMOTOPY_EQ }; - simplifiable_status is_remove_star_homotopy_preserving(const Simplex_handle& simplex) { + simplifiable_status is_remove_star_homotopy_preserving(const Simplex& simplex) { // todo write a virtual method 'link' in Skeleton_blocker_complex which will be overloaded by the current one of // Skeleton_blocker_geometric_complex // then call it there to build the link and return the value of link.is_contractible() @@ -1131,7 +1182,7 @@ class Skeleton_blocker_complex { } //@} - /** @Edge contraction operations + /** @name Edge contraction operations */ //@{ @@ -1174,7 +1225,7 @@ class Skeleton_blocker_complex { * that may be used to construct a new blocker after contracting ab. * It requires that the link condition is satisfied. */ - void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector<Simplex_handle> & buffer) const; + void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector<Simplex> & buffer) const; private: /** @@ -1217,7 +1268,7 @@ class Skeleton_blocker_complex { private: void get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set<Simplex_handle>& blockers_to_add); + std::set<Simplex>& blockers_to_add); /** * delete all blockers that passes through a or b */ @@ -1358,12 +1409,28 @@ class Skeleton_blocker_complex { /** * @brief Returns a Complex_simplex_around_vertex_range over all the simplices around a vertex of the complex */ - Complex_simplex_around_vertex_range simplex_range(Vertex_handle v) const { + Complex_simplex_around_vertex_range star_simplex_range(Vertex_handle v) const { assert(contains_vertex(v)); return Complex_simplex_around_vertex_range( Complex_simplex_around_vertex_iterator(this, v), Complex_simplex_around_vertex_iterator(this, v, true)); } + typedef Simplex_coboundary_iterator<Skeleton_blocker_complex, Link> Complex_simplex_coboundary_iterator; + + /** + * @brief Range over the simplices of the coboundary of a simplex. + * Methods .begin() and .end() return a Complex_simplex_coboundary_iterator. + */ + typedef boost::iterator_range < Complex_simplex_coboundary_iterator > Complex_coboundary_range; + + /** + * @brief Returns a Complex_simplex_coboundary_iterator over the simplices of the coboundary of a simplex. + */ + Complex_coboundary_range coboundary_range(const Simplex& s) const { + assert(contains(s)); + return Complex_coboundary_range(Complex_simplex_coboundary_iterator(this, s), + Complex_simplex_coboundary_iterator(this, s, true)); + } // typedef Simplex_iterator<Skeleton_blocker_complex,Superior_link> Complex_simplex_iterator; typedef Simplex_iterator<Skeleton_blocker_complex> Complex_simplex_iterator; @@ -1373,7 +1440,7 @@ class Skeleton_blocker_complex { /** * @brief Returns a Complex_simplex_range over all the simplices of the complex */ - Complex_simplex_range simplex_range() const { + Complex_simplex_range complex_simplex_range() const { Complex_simplex_iterator end(this, true); if (empty()) { return Complex_simplex_range(end, end); @@ -1393,7 +1460,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::iterator, + typename std::multimap<Vertex_handle, Simplex *>::iterator, Blocker_handle> Complex_blocker_around_vertex_iterator; @@ -1401,7 +1468,7 @@ class Skeleton_blocker_complex { * @brief Iterator over (constant) blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator, + typename std::multimap<Vertex_handle, Simplex *>::const_iterator, const Blocker_handle> Const_complex_blocker_around_vertex_iterator; @@ -1433,7 +1500,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers. */ typedef Blocker_iterator_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::iterator, + typename std::multimap<Vertex_handle, Simplex *>::iterator, Blocker_handle> Complex_blocker_iterator; @@ -1441,7 +1508,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the (constant) blockers. */ typedef Blocker_iterator_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator, + typename std::multimap<Vertex_handle, Simplex *>::const_iterator, const Blocker_handle> Const_complex_blocker_iterator; @@ -1515,18 +1582,21 @@ class Skeleton_blocker_complex { * return the total number of simplices */ template<typename Complex, typename SimplexHandleIterator> -Complex make_complex_from_top_faces(SimplexHandleIterator simplex_begin, SimplexHandleIterator simplex_end, +Complex make_complex_from_top_faces(SimplexHandleIterator simplices_begin, SimplexHandleIterator simplices_end, bool is_flag_complex = false) { - typedef typename Complex::Simplex_handle Simplex_handle; - std::vector<Simplex_handle> simplices; - for (auto top_face = simplex_begin; top_face != simplex_end; ++top_face) { + // TODO(DS): use add_simplex instead! should be more efficient and more elegant :) + typedef typename Complex::Simplex Simplex; + std::vector<Simplex> simplices; + for (auto top_face = simplices_begin; top_face != simplices_end; ++top_face) { auto subfaces_topface = subfaces(*top_face); simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end()); } return Complex(simplices.begin(), simplices.end(), is_flag_complex); } -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 b8395251..95331b7a 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,16 +19,17 @@ * 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_ -#include <gudhi/Utils.h> #include <gudhi/Skeleton_blocker_complex.h> #include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h> +#include <gudhi/Debug_utils.h> namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** * @brief Class that represents a geometric complex that can be simplified. @@ -46,7 +47,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { typedef typename SimplifiableSkeletonblocker::Vertex_handle Vertex_handle; typedef typename SimplifiableSkeletonblocker::Root_vertex_handle Root_vertex_handle; typedef typename SimplifiableSkeletonblocker::Edge_handle Edge_handle; - typedef typename SimplifiableSkeletonblocker::Simplex_handle Simplex_handle; + typedef typename SimplifiableSkeletonblocker::Simplex Simplex; typedef typename SimplifiableSkeletonblocker::Graph_vertex Graph_vertex; @@ -140,7 +141,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { * Constructs the link of 'simplex' with points coordinates. */ Geometric_link link(Vertex_handle v) const { - Geometric_link link(*this, Simplex_handle(v)); + Geometric_link link(*this, Simplex(v)); // we now add the point info add_points_to_link(link); return link; @@ -149,7 +150,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { /** * Constructs the link of 'simplex' with points coordinates. */ - Geometric_link link(const Simplex_handle& simplex) const { + Geometric_link link(const Simplex& simplex) const { Geometric_link link(*this, simplex); // we now add the point info add_points_to_link(link); @@ -172,13 +173,13 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { * Constructs the abstract link of v (without points coordinates). */ Abstract_link abstract_link(Vertex_handle v) const { - return Abstract_link(*this, Simplex_handle(v)); + return Abstract_link(*this, Simplex(v)); } /** * Constructs the link of 'simplex' with points coordinates. */ - Abstract_link abstract_link(const Simplex_handle& simplex) const { + Abstract_link abstract_link(const Simplex& simplex) const { return Abstract_link(*this, simplex); } @@ -217,7 +218,9 @@ SkeletonBlockerGeometricComplex make_complex_from_top_faces( return complex; } -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 95d8fa97..4db075b0 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,15 +19,16 @@ * 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_LINK_COMPLEX_H_ #define SKELETON_BLOCKER_LINK_COMPLEX_H_ -#include <gudhi/Utils.h> #include <gudhi/Skeleton_blocker_complex.h> +#include <gudhi/Debug_utils.h> namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { template<class ComplexType> class Skeleton_blocker_sub_complex; @@ -39,7 +40,7 @@ template<class ComplexType> class Skeleton_blocker_sub_complex; */ template<typename ComplexType> class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< - ComplexType> { +ComplexType> { template<typename T> friend class Skeleton_blocker_link_superior; typedef typename ComplexType::Edge_handle Edge_handle; @@ -52,28 +53,28 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< typedef typename ComplexType::Vertex_handle Vertex_handle; typedef typename ComplexType::Root_vertex_handle Root_vertex_handle; - typedef typename ComplexType::Simplex_handle Simplex_handle; + typedef typename ComplexType::Simplex Simplex; typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; typedef typename ComplexType::Blocker_handle Blocker_handle; - typedef typename ComplexType::Simplex_handle::Simplex_vertex_const_iterator Simplex_handle_iterator; typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_handle_iterator; explicit Skeleton_blocker_link_complex(bool only_superior_vertices = false) - : only_superior_vertices_(only_superior_vertices) { - } + : only_superior_vertices_(only_superior_vertices) { } /** * If the parameter only_superior_vertices is true, * only vertices greater than the one of alpha are added. + * Only vertices are computed if only_vertices is true. */ Skeleton_blocker_link_complex(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, - bool only_superior_vertices = false) + const Simplex& alpha_parent_adress, + bool only_superior_vertices = false, + bool only_vertices = false) : only_superior_vertices_(only_superior_vertices) { if (!alpha_parent_adress.empty()) - build_link(parent_complex, alpha_parent_adress); + build_link(parent_complex, alpha_parent_adress, only_vertices); } /** @@ -84,7 +85,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< Vertex_handle a_parent_adress, bool only_superior_vertices = false) : only_superior_vertices_(only_superior_vertices) { - Simplex_handle alpha_simplex(a_parent_adress); + Simplex alpha_simplex(a_parent_adress); build_link(parent_complex, alpha_simplex); } @@ -94,10 +95,10 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< */ Skeleton_blocker_link_complex(const ComplexType & parent_complex, Edge_handle edge, bool only_superior_vertices = - false) + false) : only_superior_vertices_(only_superior_vertices) { - Simplex_handle alpha_simplex(parent_complex.first_vertex(edge), - parent_complex.second_vertex(edge)); + Simplex alpha_simplex(parent_complex.first_vertex(edge), + parent_complex.second_vertex(edge)); build_link(parent_complex, alpha_simplex); } @@ -108,7 +109,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * are greater than vertices of alpha_parent_adress are added. */ void compute_link_vertices(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, + const Simplex& alpha_parent_adress, bool only_superior_vertices, bool is_alpha_blocker = false) { if (alpha_parent_adress.dimension() == 0) { @@ -119,7 +120,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< only_superior_vertices_); } else { // we compute the intersection of neighbors of alpha and store it in link_vertices - Simplex_handle link_vertices_parent; + Simplex link_vertices_parent; parent_complex.add_neighbours(alpha_parent_adress, link_vertices_parent, only_superior_vertices); // For all vertex 'v' in this intersection, we go through all its adjacent blockers. @@ -150,7 +151,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< bool only_superior_vertices) { // for a vertex we know exactly the number of vertices of the link (and the size of the corresponding vector this->skeleton.m_vertices.reserve( - parent_complex.degree(alpha_parent_adress)); + parent_complex.degree(alpha_parent_adress)); // For all vertex 'v' in this intersection, we go through all its adjacent blockers. // If one blocker minus 'v' is included in alpha then the vertex is not in the link complex. @@ -162,39 +163,34 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< } void compute_link_edges(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, + const Simplex& alpha_parent_adress, bool is_alpha_blocker = false) { - Simplex_handle_iterator y_link, x_parent, y_parent; - // ---------------------------- - // Compute edges in the link - // ------------------------- - if (this->num_vertices() <= 1) return; for (auto x_link = this->vertex_range().begin(); - x_link != this->vertex_range().end(); ++x_link) { + x_link != this->vertex_range().end(); ++x_link) { for (auto y_link = x_link; ++y_link != this->vertex_range().end();) { Vertex_handle x_parent = *parent_complex.get_address( - this->get_id(*x_link)); + this->get_id(*x_link)); Vertex_handle y_parent = *parent_complex.get_address( - this->get_id(*y_link)); + this->get_id(*y_link)); if (parent_complex.contains_edge(x_parent, y_parent)) { // we check that there is no blocker subset of alpha passing trough x and y bool new_edge = true; for (auto blocker_parent : parent_complex.const_blocker_range( - x_parent)) { + x_parent)) { if (!is_alpha_blocker || *blocker_parent != alpha_parent_adress) { if (blocker_parent->contains(y_parent)) { new_edge = !(alpha_parent_adress.contains_difference( - *blocker_parent, x_parent, y_parent)); + *blocker_parent, x_parent, y_parent)); if (!new_edge) break; } } } if (new_edge) - this->add_edge(*x_link, *y_link); + this->add_edge_without_blockers(*x_link, *y_link); } } } @@ -205,8 +201,8 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * corresponding address in 'other_complex'. * It assumes that other_complex have a vertex 'this.get_id(address)' */ - boost::optional<Vertex_handle> give_equivalent_vertex( - const ComplexType & other_complex, Vertex_handle address) const { + boost::optional<Vertex_handle> give_equivalent_vertex(const ComplexType & other_complex, + Vertex_handle address) const { Root_vertex_handle id((*this)[address].get_id()); return other_complex.get_address(id); } @@ -217,7 +213,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * the blocker is anticollapsed. */ void compute_link_blockers(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent, + const Simplex& alpha_parent, bool is_alpha_blocker = false) { for (auto x_link : this->vertex_range()) { Vertex_handle x_parent = *this->give_equivalent_vertex(parent_complex, @@ -225,7 +221,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< for (auto blocker_parent : parent_complex.const_blocker_range(x_parent)) { if (!is_alpha_blocker || *blocker_parent != alpha_parent) { - Simplex_handle sigma_parent(*blocker_parent); + Simplex sigma_parent(*blocker_parent); sigma_parent.difference(alpha_parent); @@ -239,7 +235,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< for (auto a : alpha_parent) { for (auto eta_parent : parent_complex.const_blocker_range(a)) { if (!is_alpha_blocker || *eta_parent != alpha_parent) { - Simplex_handle eta_minus_alpha(*eta_parent); + Simplex eta_minus_alpha(*eta_parent); eta_minus_alpha.difference(alpha_parent); if (eta_minus_alpha != sigma_parent && sigma_parent.contains_difference(*eta_parent, @@ -253,7 +249,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< break; } if (is_new_blocker) - this->add_blocker(new Simplex_handle(*sigma_link)); + this->add_blocker(new Simplex(*sigma_link)); } } } @@ -268,14 +264,15 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * with vertices that are greater than vertices of alpha_parent_adress. */ void build_link(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, - bool is_alpha_blocker = false) { + const Simplex& alpha_parent_adress, + bool is_alpha_blocker = false, + bool only_vertices = false) { assert(is_alpha_blocker || parent_complex.contains(alpha_parent_adress)); - compute_link_vertices(parent_complex, alpha_parent_adress, - only_superior_vertices_); - compute_link_edges(parent_complex, alpha_parent_adress, is_alpha_blocker); - compute_link_blockers(parent_complex, alpha_parent_adress, - is_alpha_blocker); + compute_link_vertices(parent_complex, alpha_parent_adress, only_superior_vertices_); + if (!only_vertices) { + compute_link_edges(parent_complex, alpha_parent_adress, is_alpha_blocker); + compute_link_blockers(parent_complex, alpha_parent_adress, is_alpha_blocker); + } } /** @@ -284,7 +281,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * removed from the blockers of the complex. */ friend void build_link_of_blocker(const ComplexType & parent_complex, - Simplex_handle& blocker, + Simplex& blocker, Skeleton_blocker_link_complex & result) { assert(blocker.dimension() >= 2); assert(parent_complex.contains_blocker(blocker)); @@ -293,7 +290,9 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< } }; -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi 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 17a237a7..544e02e8 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -4,7 +4,7 @@ * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * 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 @@ -19,6 +19,7 @@ * 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_SIMPLIFIABLE_COMPLEX_H_ #define SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ @@ -30,10 +31,10 @@ namespace Gudhi { -namespace skbl { +namespace skeleton_blocker { /** - * Returns true iff the blocker 'sigma' is popable. + * Returns true if the blocker 'sigma' is popable. * To define popable, let us call 'L' the complex that * consists in the current complex without the blocker 'sigma'. * A blocker 'sigma' is then "popable" if the link of 'sigma' @@ -45,9 +46,7 @@ bool Skeleton_blocker_complex<SkeletonBlockerDS>::is_popable_blocker(Blocker_han assert(this->contains_blocker(*sigma)); Skeleton_blocker_link_complex<Skeleton_blocker_complex> link_blocker_sigma; build_link_of_blocker(*this, *sigma, link_blocker_sigma); - - bool res = link_blocker_sigma.is_contractible() == CONTRACTIBLE; - return res; + return link_blocker_sigma.is_contractible() == CONTRACTIBLE; } /** @@ -133,7 +132,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_all_popable_blockers(Ve template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle v) { // we remove the blockers that are not consistent anymore - update_blockers_after_remove_star_of_vertex_or_edge(Simplex_handle(v)); + update_blockers_after_remove_star_of_vertex_or_edge(Simplex(v)); while (this->degree(v) > 0) { Vertex_handle w(* (adjacent_vertices(v.vertex, this->skeleton).first)); this->remove_edge(v, w); @@ -147,8 +146,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle v) { * whenever the dimension of tau is at least 2. */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_star_of_vertex_or_edge( - const Simplex_handle& simplex_to_be_removed) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed) { std::list <Blocker_handle> blockers_to_update; if (simplex_to_be_removed.empty()) return; @@ -159,7 +157,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_s } for (auto blocker_to_update : blockers_to_update) { - Simplex_handle sub_blocker_to_be_added; + Simplex sub_blocker_to_be_added; bool sub_blocker_need_to_be_added = (blocker_to_update->dimension() - simplex_to_be_removed.dimension()) >= 2; if (sub_blocker_need_to_be_added) { @@ -178,7 +176,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_s */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle a, Vertex_handle b) { - update_blockers_after_remove_star_of_vertex_or_edge(Simplex_handle(a, b)); + update_blockers_after_remove_star_of_vertex_or_edge(Simplex(a, b)); // we remove the edge this->remove_edge(a, b); } @@ -195,7 +193,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Edge_handle e) { * Remove the star of the simplex 'sigma' which needs to belong to the complex */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex& sigma) { assert(this->contains(sigma)); if (sigma.dimension() == 0) { remove_star(sigma.first_vertex()); @@ -207,34 +205,39 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex_hand } } -/** - * @brief add a maximal simplex plus all its cofaces. All vertices lower than the higher vertex of - * sigma must already be present. - * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge). - */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex& sigma) { + // to add a simplex s, all blockers included in s are first removed + // and then all simplex in the coboundary of s are added as blockers assert(!this->contains(sigma)); assert(sigma.dimension() > 1); + if (!contains_vertices(sigma)) { + std::cerr << "add_simplex: Some vertices were not present in the complex, adding them" << std::endl; + size_t num_vertices_to_add = sigma.last_vertex() - this->num_vertices() + 1; + for (size_t i = 0; i < num_vertices_to_add; ++i) + this->add_vertex(); + } + assert(contains_vertices(sigma)); + if (!contains_edges(sigma)) + add_edge(sigma); + remove_blocker_include_in_simplex(sigma); + add_blockers_after_simplex_insertion(sigma); +} - int num_vertex_to_add = 0; - for (auto v : sigma) - if (!contains_vertex(v)) ++num_vertex_to_add; - while (num_vertex_to_add--) add_vertex(); +template<typename SkeletonBlockerDS> +void Skeleton_blocker_complex<SkeletonBlockerDS>::add_blockers_after_simplex_insertion(Simplex sigma) { + if (sigma.dimension() < 1) return; - for (auto u_it = sigma.begin(); u_it != sigma.end(); ++u_it) - for (auto v_it = u_it; ++v_it != sigma.end(); /**/) { - // std::cout << "add edge" << *u_it << " " << *v_it << std::endl; - add_edge(*u_it, *v_it); - } - remove_blocker_include_in_simplex(sigma); + for (auto s : coboundary_range(sigma)) { + this->add_blocker(s); + } } /** * remove all blockers that contains sigma */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex& sigma) { std::vector <Blocker_handle> blockers_to_remove; for (auto blocker : this->blocker_range(sigma.first_vertex())) { if (blocker->contains(sigma)) @@ -248,14 +251,26 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simp * remove all blockers that contains sigma */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex_handle& sigma) { - std::vector <Blocker_handle> blockers_to_remove; - for (auto blocker : this->blocker_range(sigma.first_vertex())) { - if (sigma.contains(*blocker)) - blockers_to_remove.push_back(blocker); +void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex& sigma) { + // TODO(DS): write efficiently by using only superior blockers + // eg for all s, check blockers whose vertices are all greater than s + std::set <Blocker_handle> blockers_to_remove; + for (auto s : sigma) { + for (auto blocker : this->blocker_range(s)) { + if (sigma.contains(*blocker)) + blockers_to_remove.insert(blocker); + } } - for (auto blocker_to_update : blockers_to_remove) + for (auto blocker_to_update : blockers_to_remove) { + auto s = *blocker_to_update; this->delete_blocker(blocker_to_update); + // now if there is a vertex v in the link of s + // and v is not included in sigma then v.s is a blocker + // (all faces of v.s are there since v belongs to the link of s) + for (const auto& b : coboundary_range(s)) + if (!sigma.contains(b)) + this->add_blocker(b); + } } /** @@ -265,21 +280,21 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simp */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, Vertex_handle b, - std::vector<Simplex_handle> & buffer) const { + std::vector<Simplex> & buffer) const { for (auto const & blocker : this->const_blocker_range(a)) { - Simplex_handle beta = (*blocker); + Simplex beta = (*blocker); beta.remove_vertex(a); buffer.push_back(beta); } - Simplex_handle n; + Simplex n; this->add_neighbours(b, n); this->remove_neighbours(a, n); n.remove_vertex(a); for (Vertex_handle y : n) { - Simplex_handle beta; + Simplex beta; beta.add_vertex(y); buffer.push_back(beta); } @@ -296,7 +311,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { - this->add_edge(a, x); + this->add_edge_without_blockers(a, x); if (this->visitor) this->visitor->on_swaped_edge(a, b, x); this->remove_edge(b, x); } @@ -341,13 +356,13 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vert assert(this->contains_vertex(b)); if (this->contains_edge(a, b)) - this->add_edge(a, b); + this->add_edge_without_blockers(a, b); // if some blockers passes through 'ab', we need to remove them. if (!link_condition(a, b)) delete_blockers_around_edge(a, b); - std::set<Simplex_handle> blockers_to_add; + std::set<Simplex> blockers_to_add; get_blockers_to_be_added_after_contraction(a, b, blockers_to_add); @@ -367,9 +382,9 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vert } template<typename SkeletonBlockerDS> -void -Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set<Simplex_handle>& blockers_to_add) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_contraction(Vertex_handle a, + Vertex_handle b, + std::set<Simplex>& blockers_to_add) { blockers_to_add.clear(); typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex<SkeletonBlockerDS> > LinkComplexType; @@ -377,19 +392,19 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_cont LinkComplexType link_a(*this, a); LinkComplexType link_b(*this, b); - std::vector<Simplex_handle> vector_alpha, vector_beta; + std::vector<Simplex> vector_alpha, vector_beta; tip_blockers(a, b, vector_alpha); tip_blockers(b, a, vector_beta); for (auto alpha = vector_alpha.begin(); alpha != vector_alpha.end(); ++alpha) { for (auto beta = vector_beta.begin(); beta != vector_beta.end(); ++beta) { - Simplex_handle sigma = *alpha; + Simplex sigma = *alpha; sigma.union_vertices(*beta); Root_simplex_handle sigma_id = this->get_id(sigma); if (this->contains(sigma) && proper_faces_in_union<Skeleton_blocker_complex < SkeletonBlockerDS >> (sigma_id, link_a, link_b)) { - // Blocker_handle blocker = new Simplex_handle(sigma); + // Blocker_handle blocker = new Simplex(sigma); sigma.add_vertex(a); blockers_to_add.insert(sigma); } @@ -443,7 +458,9 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::notify_changed_edges(Vertex_handle } -} // namespace skbl +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; } // namespace Gudhi diff --git a/src/Skeleton_blocker/test/CMakeLists.txt b/src/Skeleton_blocker/test/CMakeLists.txt index 8b6fb672..f98517f0 100644 --- a/src/Skeleton_blocker/test/CMakeLists.txt +++ b/src/Skeleton_blocker/test/CMakeLists.txt @@ -1,28 +1,35 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHIskbl) +project(Skeleton_blocker_tests) if (GCOVR_PATH) # for gcovr to make coverage reports - Corbera Jenkins plugin set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fprofile-arcs -ftest-coverage") - set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -fprofile-arcs -ftest-coverage") endif() if (GPROF_PATH) # for gprof to make coverage reports - Jenkins set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg") - set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg") endif() -add_executable(TestSkeletonBlockerComplex TestSkeletonBlockerComplex.cpp) -add_executable(TestSimplifiable TestSimplifiable.cpp) -add_executable(TestGeometricComplex TestGeometricComplex.cpp) +add_executable ( test_skeleton_blocker_complex test_skeleton_blocker_complex.cpp ) +target_link_libraries(test_skeleton_blocker_complex ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +add_executable ( test_skeleton_blocker_geometric_complex test_skeleton_blocker_geometric_complex.cpp ) +target_link_libraries(test_skeleton_blocker_geometric_complex ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +add_executable ( test_skeleton_blocker_simplifiable test_skeleton_blocker_simplifiable.cpp ) +target_link_libraries(test_skeleton_blocker_simplifiable ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) # Do not forget to copy test files in current binary dir -file(COPY "test.off" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) file(COPY "test2.off" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) -add_test(TestSkeletonBlockerComplex ${CMAKE_CURRENT_BINARY_DIR}/TestSkeletonBlockerComplex) -add_test(TestSimplifiable ${CMAKE_CURRENT_BINARY_DIR}/TestSimplifiable) -add_test(TestGeometricComplex ${CMAKE_CURRENT_BINARY_DIR}/TestGeometricComplex) - +# Unitary tests +add_test(NAME test_skeleton_blocker_complex + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/test_skeleton_blocker_complex + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/skbl_complexUT.xml --log_level=test_suite --report_level=no) +add_test(NAME test_skeleton_blocker_geometric_complex + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/test_skeleton_blocker_geometric_complex + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/skbl_geometric_complexUT.xml --log_level=test_suite --report_level=no) +add_test(NAME test_skeleton_blocker_simplifiable + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/test_skeleton_blocker_simplifiable + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/skbl_simplifiableUT.xml --log_level=test_suite --report_level=no) diff --git a/src/Skeleton_blocker/test/TestGeometricComplex.cpp b/src/Skeleton_blocker/test/TestGeometricComplex.cpp deleted file mode 100644 index bd7af89b..00000000 --- a/src/Skeleton_blocker/test/TestGeometricComplex.cpp +++ /dev/null @@ -1,120 +0,0 @@ - /* 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 <stdio.h> -#include <stdlib.h> -#include <string> -#include <fstream> -#include <sstream> -#include "gudhi/Test.h" -#include "gudhi/Skeleton_blocker.h" - - -using namespace std; -using namespace Gudhi; -using namespace skbl; - -struct Geometry_trait{ - typedef std::vector<double> Point; -}; - -typedef Geometry_trait::Point Point; -typedef Skeleton_blocker_simple_geometric_traits<Geometry_trait> Complex_geometric_traits; -typedef Skeleton_blocker_geometric_complex< Complex_geometric_traits > Complex; -typedef Complex::Vertex_handle Vertex_handle; - - -bool test_constructor1(){ - Complex complex; - Skeleton_blocker_off_reader<Complex> off_reader("test2.off",complex); - if(!off_reader.is_valid()){ - std::cerr << "Unable to read file"<<std::endl; - return false; - } - - - std::cout << "complex has "<< - complex.num_vertices()<<" vertices, "<< - complex.num_blockers()<<" blockers, "<< - complex.num_edges()<<" edges and" << - complex.num_triangles()<<" triangles."; - - if(complex.num_vertices()!=7 || complex.num_edges()!=12 || complex.num_triangles() !=6) - return false; - - Skeleton_blocker_off_writer<Complex> off_writer("tmp.off",complex); - Complex same; - Skeleton_blocker_off_reader<Complex> off_reader2("tmp.off",same); - - std::cout<<"\ncomplex:"<<complex.to_string()<<endl; - std::cout<<"\nsame:"<<same.to_string()<<endl; - - return (complex==same); -} - -bool test_constructor2(){ - Complex complex; - Skeleton_blocker_off_reader<Complex> off_reader("test2.off",complex); - if(!off_reader.is_valid()){ - std::cerr << "Unable to read file"<<std::endl; - return false; - } - std::cout << "complex has "<< - complex.num_vertices()<<" vertices, "<< - complex.num_blockers()<<" blockers, "<< - complex.num_edges()<<" edges and" << - complex.num_triangles()<<" triangles."; - - if(complex.num_vertices()!=7 || complex.num_edges()!=12 || complex.num_triangles() !=6) - return false; - - auto link_0 = complex.abstract_link(Vertex_handle(0)); - - - std::cout<<"\n link(0):"<<link_0.to_string()<<endl; - - auto link_geometric_0 = complex.link(Vertex_handle(0)); - - auto print_point = [&](Vertex_handle v){for(auto x : link_geometric_0.point(v)) std::cout <<x<<" "; std::cout<<std::endl;}; - - std::for_each(link_geometric_0.vertex_range().begin(),link_geometric_0.vertex_range().end(),print_point); - -// for(auto v : link_geometric_0.vertex_range()) -// std::cout<<"point("<<v<<"):"<<link_geometric_0.point(v)<<std::endl; - - return link_0.num_vertices()==2; -} - - - - -int main (int argc, char *argv[]) -{ - Tests tests_geometric_complex; - tests_geometric_complex.add("Test constructor 1",test_constructor1); - tests_geometric_complex.add("Test constructor 2",test_constructor2); - - if(tests_geometric_complex.run()) - return EXIT_SUCCESS; - else - return EXIT_FAILURE; -} diff --git a/src/Skeleton_blocker/test/TestSimplifiable.cpp b/src/Skeleton_blocker/test/TestSimplifiable.cpp deleted file mode 100644 index 09176934..00000000 --- a/src/Skeleton_blocker/test/TestSimplifiable.cpp +++ /dev/null @@ -1,356 +0,0 @@ - /* 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 <stdio.h> -#include <stdlib.h> -#include <string> -#include <fstream> -#include <sstream> -#include "gudhi/Test.h" -//#include "Skeleton_blocker/Simplex.h" -#include "gudhi/Skeleton_blocker.h" - - -using namespace std; - -using namespace Gudhi; - -using namespace skbl; - -template<typename ComplexType> class Skeleton_blocker_sub_complex; -typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; -typedef Complex::Vertex_handle Vertex_handle; -typedef Complex::Root_vertex_handle Root_vertex_handle; -typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; -// true iff v \in complex -bool assert_vertex(Complex &complex,Vertex_handle v){ - Simplex_handle simplex(v); - bool test = complex.contains(simplex); - assert(test); - return test; -} - -// true iff the blocker (a,b,c) is in complex -bool assert_blocker(Complex &complex,Root_vertex_handle a,Root_vertex_handle b,Root_vertex_handle c){ - - return complex.contains_blocker(Simplex_handle(*complex.get_address(a),*complex.get_address(b),*complex.get_address(c))); - //return complex.contains_blocker((a),(b),(c)); -} - -void build_complete(int n,Complex& complex){ - complex.clear(); - 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(Vertex_handle(i),Vertex_handle(j)); -} - -bool test_contraction1(){ - enum { a, b, x, y, z, n }; - Complex complex(n); - build_complete(n,complex); - complex.remove_edge(static_cast<Vertex_handle>(b), static_cast<Vertex_handle>(z)); - complex.add_blocker(Simplex_handle(static_cast<Vertex_handle>(a), static_cast<Vertex_handle>(x), - static_cast<Vertex_handle>(y))); - complex.add_blocker(Simplex_handle(static_cast<Vertex_handle>(b), static_cast<Vertex_handle>(x), - static_cast<Vertex_handle>(y))); - - // Print result - cerr << "complex before complex"<< complex.to_string()<<endl; - - cerr <<endl<<endl; - complex.contract_edge(static_cast<Vertex_handle>(a),static_cast<Vertex_handle>(b)); - // Print result - cerr << "ContractEdge(0,1)\n"; - PRINT(complex.to_string()); - - // verification - for (int i=0;i<5;i++) - if (i!=1) assert_vertex(complex, static_cast<Vertex_handle>(i)); - bool test1 = !complex.contains_edge(static_cast<Vertex_handle>(a),static_cast<Vertex_handle>(b)); - bool test2 = assert_blocker(complex,Root_vertex_handle(a),Root_vertex_handle(x),Root_vertex_handle(y)); - bool test3 = complex.num_edges()==6; - bool test4 = complex.num_blockers()==1; - Simplex_handle sigma; - sigma.add_vertex(static_cast<Vertex_handle>(a)); - sigma.add_vertex(static_cast<Vertex_handle>(x)); - sigma.add_vertex(static_cast<Vertex_handle>(y)); - sigma.add_vertex(static_cast<Vertex_handle>(z)); - bool test5 = !(complex.contains(sigma)); - return test1&&test2&&test3&&test4&&test5; -} - - -bool test_contraction2(){ - enum { a, b, x, y, z, n }; - Complex complex(n); - build_complete(n,complex); - complex.remove_edge(static_cast<Vertex_handle>(b),static_cast<Vertex_handle>(x)); - Simplex_handle blocker; - blocker.add_vertex(static_cast<Vertex_handle>(a)); - blocker.add_vertex(static_cast<Vertex_handle>(y)); - blocker.add_vertex(static_cast<Vertex_handle>(z)); - - complex.add_blocker(blocker); - - // Print result - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - complex.contract_edge(static_cast<Vertex_handle>(a),static_cast<Vertex_handle>(b)); - - cerr << "complex.ContractEdge(a,b)"<< complex.to_string(); - - cerr <<endl<<endl; - - // there should be one blocker (a,c,d,e) in the complex - bool test ; - test = complex.contains_blocker(Simplex_handle(static_cast<Vertex_handle>(a), static_cast<Vertex_handle>(x), - static_cast<Vertex_handle>(y),static_cast<Vertex_handle>(z))); - test = test && complex.num_blockers()==1; - return test; -} - -bool test_link_condition1(){ - - Complex complex(0); - // Build the complexes - build_complete(4,complex); - complex.add_blocker(Simplex_handle(static_cast<Vertex_handle>(0), static_cast<Vertex_handle>(1), static_cast<Vertex_handle>(2))); - - - // Print result - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - - bool weak_link_condition = complex.link_condition(Vertex_handle(1),Vertex_handle(2),true); - - bool strong_link_condition = complex.link_condition(Vertex_handle(1),Vertex_handle(2),false); - - return weak_link_condition && !strong_link_condition; -} - - -bool test_collapse0(){ - Complex complex(5); - build_complete(4,complex); - complex.add_vertex(); - complex.add_edge(static_cast<Vertex_handle>(2), static_cast<Vertex_handle>(4)); - complex.add_edge(static_cast<Vertex_handle>(3), static_cast<Vertex_handle>(4)); - // Print result - cerr << "initial complex :\n"<< complex.to_string(); - cerr <<endl<<endl; - - Simplex_handle simplex_123(static_cast<Vertex_handle>(1), static_cast<Vertex_handle>(2), static_cast<Vertex_handle>(3)); - complex.remove_star(simplex_123); - cerr << "complex.remove_star(1,2,3):\n"<< complex.to_string(); - cerr <<endl<<endl; - - // verification - bool blocker123_here = complex.contains_blocker(simplex_123); - cerr <<"----> Ocomplex \n"; - return blocker123_here; -} - - -bool test_collapse1(){ - Complex complex(5); - build_complete(4,complex); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - // Print result - cerr << "initial complex :\n"<< complex.to_string(); - cerr <<endl<<endl; - - Simplex_handle simplex_123(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); - complex.remove_star(simplex_123); - cerr << "complex.remove_star(1,2,3):\n"<< complex.to_string(); - cerr <<endl<<endl; - - // verification - bool res = complex.contains_blocker(simplex_123); - res = res && complex.num_blockers()==1; - cerr <<"----> Ocomplex \n"; - return res; -} - -bool test_collapse2(){ - Complex complex(5); - build_complete(4,complex); - complex.add_vertex(); - complex.add_edge(Vertex_handle(1),Vertex_handle(4)); - complex.add_edge(Vertex_handle(2),Vertex_handle(4)); - complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); - // Print result - cerr << "initial complex :\n"<< complex.to_string(); - cerr <<endl<<endl; - - Simplex_handle sigma(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); - complex.remove_star(sigma); - cerr << "complex.remove_star(1,2,3):\n"<< complex.to_string(); - cerr <<endl<<endl; - - // verification - bool blocker_removed = !complex.contains_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); - bool blocker123_here = complex.contains_blocker(sigma); - return blocker_removed && blocker123_here; -} - -bool test_collapse3(){ - Complex complex(5); - build_complete(4,complex); - complex.add_vertex(); - complex.add_edge(Vertex_handle(1),Vertex_handle(4)); - complex.add_edge(Vertex_handle(2),Vertex_handle(4)); - complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); - // Print result - cerr << "initial complex:\n"<< complex.to_string(); - cerr <<endl<<endl; - - complex.remove_star(static_cast<Vertex_handle>(2)); - cerr << "complex after remove star of 2:\n"<< complex.to_string(); - - bool blocker134_here = complex.contains_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(3),Vertex_handle(4))); - bool blocker1234_here = complex.contains_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3),Vertex_handle(4))); - return blocker134_here && !blocker1234_here; -} - -bool test_add_simplex(){ - Complex complex(5); - build_complete(4,complex); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - // Print result - cerr << "initial complex:\n"<< complex.to_string(); - cerr <<endl<<endl; - - complex.add_simplex(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - cerr << "complex after add_simplex:\n"<< complex.to_string(); - - return complex.num_blockers()==0; -} - -bool test_add_simplex2(){ - Complex complex; - build_complete(4,complex); - // Print result - cerr << "initial complex:\n"<< complex.to_string(); - cerr <<endl<<endl; - - Complex copy(complex.num_vertices()); - - std::vector<Simplex_handle> simplices(complex.simplex_range().begin(),complex.simplex_range().end()); - sort(simplices.begin(),simplices.end(),[&](const Simplex_handle& s1,const Simplex_handle& s2){ - return s1.dimension()<s2.dimension(); - }); - for(const auto & simplex : simplices){ - if(!copy.contains(simplex) && simplex.dimension()==1) - copy.add_edge(simplex.first_vertex(),simplex.last_vertex()); - if(!copy.contains(simplex) && simplex.dimension()>1) - copy.add_simplex(simplex); - } - - - cerr << "complex after add_simplex:\n"<< copy.to_string(); - - - return complex.num_blockers()==copy.num_blockers() && - complex.num_edges()==copy.num_edges() && - complex.num_vertices()==copy.num_vertices(); -} - - - -bool test_remove_popable_blockers(){ - Complex complex; - build_complete(4,complex); - complex.add_vertex(); - complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_edge(Vertex_handle(2),Vertex_handle(4)); - Simplex_handle sigma1=Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); - Simplex_handle sigma2=Simplex_handle(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4)); - - complex.add_blocker(sigma1); - complex.add_blocker(sigma2); - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - cerr << "complex.RemovePopableBlockers();"<<endl; - complex.remove_popable_blockers(); - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - - bool test1 = (complex.num_blockers()==1); - - - // test 2 - complex.clear(); - build_complete(4,complex); - complex.add_vertex(); - complex.add_vertex(); - complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_edge(Vertex_handle(2),Vertex_handle(4)); - complex.add_edge(Vertex_handle(2),Vertex_handle(5)); - complex.add_edge(Vertex_handle(3),Vertex_handle(5)); - complex.add_edge(Vertex_handle(4),Vertex_handle(5)); - sigma1=Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); - sigma2=Simplex_handle(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4)); - - complex.add_blocker(sigma1); - complex.add_blocker(sigma2); - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; cerr << "complex.RemovePopableBlockers();"<<endl; - complex.remove_popable_blockers(); - cerr << "complex complex"<< complex.to_string(); - - cerr <<endl<<endl; - bool test2 = (complex.num_blockers()==0); - return test1&&test2; -} - - - -int main (int argc, char *argv[]) -{ - Tests tests_simplifiable_complex; - tests_simplifiable_complex.add("Test contraction 1",test_contraction1); - tests_simplifiable_complex.add("Test contraction 2",test_contraction2); - tests_simplifiable_complex.add("Test Link condition 1",test_link_condition1); - tests_simplifiable_complex.add("Test remove popable blockers",test_remove_popable_blockers); - - - tests_simplifiable_complex.add("Test collapse 0",test_collapse0); - tests_simplifiable_complex.add("Test collapse 1",test_collapse1); - tests_simplifiable_complex.add("Test collapse 2",test_collapse2); - tests_simplifiable_complex.add("Test collapse 3",test_collapse3); - - tests_simplifiable_complex.add("Test add simplex",test_add_simplex); - tests_simplifiable_complex.add("Test add simplex2",test_add_simplex2); - - - tests_simplifiable_complex.run(); - - if(tests_simplifiable_complex.run()) - return EXIT_SUCCESS; - else - return EXIT_FAILURE; -} diff --git a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp deleted file mode 100644 index 319e3c43..00000000 --- a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp +++ /dev/null @@ -1,952 +0,0 @@ -/* 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 <stdio.h> -#include <stdlib.h> -#include <string> -#include <fstream> -#include <sstream> -#include "gudhi/Utils.h" -#include "gudhi/Test.h" -#include "gudhi/Skeleton_blocker.h" -//#include "gudhi/Skeleton_blocker_link_complex.h" -//#include "gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h" -//#include "gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h" -//#include "gudhi/Skeleton_blocker/internal/Trie.h" - -using namespace std; - -using namespace Gudhi; - -using namespace skbl; - - -typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; -typedef Complex::Vertex_handle Vertex_handle; -typedef Complex::Root_vertex_handle Root_vertex_handle; -typedef Complex::Simplex_handle Simplex_handle; -typedef Complex::Root_simplex_handle Root_simplex_handle; -typedef Simplex_handle::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; -typedef Complex::Edge_handle Edge_handle; - -// true if v in complex -bool assert_vertex(Complex &complex,Vertex_handle v){ - //assert(complex.contains(v)); - return complex.contains(static_cast<Simplex_handle>(v)); -} - -bool assert_simplex(Complex &complex,Root_vertex_handle a,Root_vertex_handle b,Root_vertex_handle c){ - return true; - // AddressSimplex simplex((a),(b),(c)); - // return complex.contains(&simplex); -} - -// true iff the blocker (a,b,c) is in complex -bool assert_blocker(Complex &complex,Root_vertex_handle a,Root_vertex_handle b,Root_vertex_handle c){ - return true; - //return complex.contains_blocker((a),(b),(c)); -} - -// true iff the blocker (a,b,c,d) is in complex -bool assert_blocker(Complex &complex,Root_vertex_handle a,Root_vertex_handle b,Root_vertex_handle c,Root_vertex_handle d){ - return true; - //Simplex blocker (a,b,c,d); - //return complex.contains_blocker(&blocker); -} - - - -void build_complete(int n,Complex& complex){ - complex.clear(); - for(int i=0;i<n;i++) - complex.add_vertex(); - - // for(int i=n-1;i>=0;i--) - // for(int j=i-1;j>=0;j--) - // complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); -} - - -bool test_simplex(){ - // PRINT("test simplex"); - Simplex_handle simplex(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); - for (auto i = simplex.begin() ; i != simplex.end() ; ++i){ - PRINT(*i); - auto j = i; - for (++j ; - j != simplex.end() ; - ++j){ - PRINT(*j); - } - } - return simplex.dimension()==3; -} - - -bool test_iterator_vertices1(){ - int n = 10; - Complex complex(10); - cerr << "complex.num_vertices():"<<complex.num_vertices()<<endl; - int num_vertex_seen = 0; - for(auto vi :complex.vertex_range()){ - cerr << "vertex:"<<vi<<endl; - ++num_vertex_seen; - } - return num_vertex_seen == n; -} - -bool test_iterator_vertices2(){ - int n = 10; - Complex complex(10); - build_complete(10,complex); - cerr << "complex.num_vertices():"<<complex.num_vertices()<<endl; - cerr << "complex.num_edges():"<<complex.num_edges()<<endl; - int num_vertex_seen = 0; - for(auto vi :complex.vertex_range(Vertex_handle(2))){ - cerr << "vertex:"<<vi<<endl; - ++num_vertex_seen; - } - std::cerr<<"num_vertex_seen:"<<num_vertex_seen<<std::endl; - return num_vertex_seen == (n-1); -} - - - -bool test_iterator_edge(){ - const int n = 10; - Complex complex(n); - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - complex.remove_edge(Vertex_handle(2),Vertex_handle(3)); - complex.remove_edge(Vertex_handle(3),Vertex_handle(5)); - cerr << "complex.num_edges():"<<complex.num_edges()<<endl; - int num_edges_seen = 0; - for(auto edge : complex.edge_range()){ - cerr << "edge :"<<complex[edge]<<endl; - ++num_edges_seen; - } - - return num_edges_seen == n*(n-1)/2-2; -} - -bool test_iterator_edge2(){ - const int n = 10; - Complex complex(n); - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - complex.remove_edge(Vertex_handle(2),Vertex_handle(3)); - complex.remove_edge(Vertex_handle(3),Vertex_handle(5)); - cerr << "complex.num_edges():"<<complex.num_edges()<<endl; - int num_neigbors_seen = 0; - for(auto neighbor : complex.vertex_range(Vertex_handle(2))){ - cerr << "neighbor"<<neighbor<<endl; - ++num_neigbors_seen; - } - return num_neigbors_seen==8; -} - - - -bool test_iterator_edge3(){ - const int n = 10; - Complex complex(n); - for(int i=0;i<n;i++) - for(int j=0;j<i;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - complex.remove_edge(Vertex_handle(2),Vertex_handle(3)); - complex.remove_edge(Vertex_handle(3),Vertex_handle(5)); - cerr << "complex.num_edges():"<<complex.num_edges()<<endl; - int num_neigbors_seen = 0; - for(auto edge : complex.edge_range(Vertex_handle(2))){ - std::cerr << edge<< std::endl; - ++num_neigbors_seen; - } - return num_neigbors_seen==8; -} - - - -bool test_iterator_triangles(){ - const int n = 7; - Complex complex(n); - //create a "ring" around '0' - for(int i=1;i<n;i++) - complex.add_edge(Vertex_handle(0),Vertex_handle(i)); - for(int i=1;i<n-1;i++) - complex.add_edge(Vertex_handle(i),Vertex_handle(i+1)); - complex.add_edge(Vertex_handle(1),Vertex_handle(6)); - - PRINT(complex.to_string()); - - int num_triangles_seen=0; - //for (auto t : complex.triangle_range(5)){ - TEST("triangles around 5 (should be 2 of them):"); - for (auto t : complex.triangle_range(Vertex_handle(5))){ - PRINT(t); - ++num_triangles_seen; - } - bool test = (num_triangles_seen==2); - - num_triangles_seen=0; - TEST("triangles around 0 (should be 6 of them):"); - for (auto t : complex.triangle_range(Vertex_handle(0))){ - PRINT(t); - ++num_triangles_seen; - } - test = test&&(num_triangles_seen==6); - - // we now add another triangle - complex.add_vertex(); - complex.add_edge(Vertex_handle(4),Vertex_handle(7)); - complex.add_edge(Vertex_handle(3),Vertex_handle(7)); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(6))); - num_triangles_seen=0; - - TEST("triangles (should be 6 of them):"); - num_triangles_seen=0; - for (auto t : complex.triangle_range()){ - PRINT(t); - ++num_triangles_seen; - } - test = test&&(num_triangles_seen==6); - PRINT(num_triangles_seen); - - return test; -} - - -//#include "combinatorics/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h" - -bool test_iterator_simplices(){ - Complex complex(6); - complex.add_edge(Vertex_handle(0),Vertex_handle(1)); - complex.add_edge(Vertex_handle(1),Vertex_handle(2)); - complex.add_edge(Vertex_handle(2),Vertex_handle(0)); - complex.add_edge(Vertex_handle(1),Vertex_handle(3)); - complex.add_edge(Vertex_handle(2),Vertex_handle(3)); - complex.add_edge(Vertex_handle(2),Vertex_handle(5)); - complex.add_edge(Vertex_handle(3),Vertex_handle(5)); - complex.add_edge(Vertex_handle(2),Vertex_handle(4)); - complex.add_edge(Vertex_handle(4),Vertex_handle(5)); - complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - - complex.add_blocker(Simplex_handle(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4),Vertex_handle(5))); - - bool correct_number_simplices = true; - - std::map<Vertex_handle,unsigned> expected_num_simplices; - - expected_num_simplices[Vertex_handle(0)] = 4; - expected_num_simplices[Vertex_handle(1)] = 6; - expected_num_simplices[Vertex_handle(2)] = 11; - expected_num_simplices[Vertex_handle(3)] = 9; - expected_num_simplices[Vertex_handle(4)] = 7; - expected_num_simplices[Vertex_handle(5)] = 7; - - for(auto pair : expected_num_simplices){ - unsigned num_simplices_around = 0; - for(const auto& simplex : complex.simplex_range(pair.first)){ - simplex.dimension(); - DBGVALUE(simplex); - ++num_simplices_around; - } - - correct_number_simplices = correct_number_simplices && (num_simplices_around == pair.second); - - DBGMSG("current vertex:",pair.first); - DBGMSG("expected_num_simplices:",pair.second); - DBGMSG("found:",num_simplices_around); - } - return correct_number_simplices; -} - - - -bool test_iterator_simplices2(){ - Complex complex(2); - complex.add_edge(Vertex_handle(0),Vertex_handle(1)); - - for(const auto& s:complex.triangle_range()){ - s.dimension(); - return false; // there are no triangles - } - - unsigned num_simplices = 0 ; - - - DBGVALUE(complex.to_string()); - - for(const auto& simplex : complex.simplex_range(Vertex_handle(0))){ - simplex.dimension(); - DBGVALUE(simplex); - } - - - for(const auto& simplex : complex.simplex_range()){ - DBGVALUE(simplex); - simplex.dimension(); - ++num_simplices; - } - bool correct_number_simplices = (num_simplices == 3); - return correct_number_simplices; -} - - -bool test_iterator_simplices3(){ - Complex complex(3); - complex.add_edge(Vertex_handle(0),Vertex_handle(1)); - complex.add_edge(Vertex_handle(1),Vertex_handle(2)); - complex.add_edge(Vertex_handle(2),Vertex_handle(0)); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - - unsigned num_simplices = 0 ; - - for(const auto& simplex : complex.simplex_range(Vertex_handle(0))){ - simplex.dimension(); - DBGVALUE(simplex); - } - - - for(const auto& simplex : complex.simplex_range()){ - DBGVALUE(simplex); - simplex.dimension(); - ++num_simplices; - } - bool correct_number_simplices = (num_simplices == 6); - return correct_number_simplices; -} - -bool test_iterator_simplices4(){ - Complex empty_complex; - for(auto v : empty_complex.vertex_range()){ - (void) v; - } - for(auto e : empty_complex.edge_range()){ - empty_complex[e]; - } - for(auto t : empty_complex.triangle_range()){ - t.dimension(); - } - for(auto s : empty_complex.simplex_range()){ - s.dimension(); - } - return true; -} - - - - - -template<typename Map> -auto blocker_range(Map map) -> decltype( map | boost::adaptors::map_values){ - return map| boost::adaptors::map_values ; -} - - -bool test_iterator_blockers(){ - Complex complex; - Simplex_handle alpha; - Simplex_handle vertex_set_expected; - // Build the complexes - for (int i=0;i<20;i++){ - complex.add_vertex(); - } - for (int i=10;i<15;i++){ - for (int j=i+1;j<15;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - } - - complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12))); - complex.add_blocker(Simplex_handle(Vertex_handle(2),Vertex_handle(1),Vertex_handle(10))); - complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(9),Vertex_handle(15))); - complex.add_blocker(Simplex_handle(Vertex_handle(1),Vertex_handle(9),Vertex_handle(8))); - - // Print result - int num_blockers=0; - for(auto blockers : complex.blocker_range(Vertex_handle(10))){ - TESTVALUE(*blockers) ; - num_blockers++; - } - bool test = (num_blockers==3); - - num_blockers=0; - for (auto blockers : complex.blocker_range()){ - TESTVALUE(*blockers) ; - num_blockers++; - } - test = test && (num_blockers==4) ; - - return test; -} - - -bool test_link0(){ - - enum { a, b, c, d, n }; - Complex complex(n); - complex.add_edge(Vertex_handle(b),Vertex_handle(c));complex.add_edge(Vertex_handle(c),Vertex_handle(d)); - Simplex_handle alpha = Simplex_handle(Vertex_handle(c)); - Skeleton_blocker_link_complex<Complex> L(complex,alpha); - - auto L2 = complex.link(alpha); - if(L!=L2) return false; - - PRINT(L.num_vertices()); - PRINT(L.to_string()); - - bool test1 = L.contains_vertex(*L.get_address(Root_vertex_handle(b))); - bool test2 = L.contains_vertex(*L.get_address(Root_vertex_handle(d))); - bool test3 = L.num_edges()==0; - bool test4 = L.num_blockers()==0; - return test1&&test2&&test3&&test4; - -} - -bool test_link1(){ - Complex complex; - - - // Build the complexes - for (int i=0;i<20;i++){ - complex.add_vertex(); - } - for (int i=10;i<15;i++){ - for (int j=i+1;j<15;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - } - Simplex_handle alpha(Vertex_handle(12),Vertex_handle(14)); - Skeleton_blocker_link_complex<Complex> L(complex,alpha); - // Complexes built - - auto L2 = complex.link(alpha); - if(L!=L2) return false; - - // verification - bool test1 = L.contains_vertex(*L.get_address(Root_vertex_handle(10))); - bool test2 = L.contains_vertex(*L.get_address(Root_vertex_handle(11))); - bool test3 = L.contains_vertex(*L.get_address(Root_vertex_handle(13))); - bool test4 = L.num_edges()==3; - bool test5 = L.num_blockers()==0; - Root_simplex_handle simplex; - simplex.add_vertex(Root_vertex_handle(10)); - simplex.add_vertex(Root_vertex_handle(11)); - simplex.add_vertex(Root_vertex_handle(13)); - bool test6(L.get_simplex_address(simplex)); - bool test7 = L.contains(*(L.get_simplex_address(simplex))); - cerr <<"----> Ocomplex \n"; - return test1&&test2&&test3&&test4&&test5&&test6&&test7 ; - -} - - -bool test_link2(){ - Complex complex; - - Simplex_handle alpha; - Simplex_handle vertex_set_expected; - // Build the complexes - for (int i=0;i<20;i++){ - complex.add_vertex(); - } - for (int i=10;i<15;i++){ - for (int j=i+1;j<15;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - } - complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(13))); - alpha = Simplex_handle(Vertex_handle(12),Vertex_handle(14)); - Skeleton_blocker_link_complex<Complex> L(complex,alpha); - // Complexes built - - // Print result - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - cerr << "L= Link_complex("<<alpha<<") : \n"<<L.to_string(); - - auto L2 = complex.link(alpha); - if(L!=L2) return false; - - - // verification - bool test1 = L.contains_vertex(*L.get_address(Root_vertex_handle(10))); - bool test2 = L.contains_vertex(*L.get_address(Root_vertex_handle(11))); - bool test3 = L.contains_vertex(*L.get_address(Root_vertex_handle(13))); - bool test4 = L.num_edges()==3; - bool test5 = L.num_blockers()==1; - Root_simplex_handle simplex; - simplex.add_vertex(Root_vertex_handle(10)); - simplex.add_vertex(Root_vertex_handle(11)); - simplex.add_vertex(Root_vertex_handle(13)); - bool test6 = L.contains_blocker(*(L.get_simplex_address(simplex))); - cerr <<"----> Ocomplex \n"; - return test1&&test2&&test3&&test4&&test5&&test6 ; -} - -bool test_link3(){ - Complex complex; - - Simplex_handle alpha; - Simplex_handle vertex_set_expected; - // Build the complexes - for (int i=0;i<20;i++){ - complex.add_vertex(); - } - for (int i=10;i<15;i++){ - for (int j=i+1;j<15;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - } - complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12))); - alpha = Simplex_handle(Vertex_handle(12),Vertex_handle(14)); - Skeleton_blocker_link_complex<Complex> L(complex,alpha); - // Complexes built - - // Print result - cerr << "complex complex"<< complex.to_string(); - cerr <<endl<<endl; - cerr << "L= Link_complex("<<alpha<<") : \n"<<L.to_string(); - - auto L2 = complex.link(alpha); - if(L!=L2) return false; - - - // verification - bool test = assert_vertex(L,*L.get_address(Root_vertex_handle(10))); - test = test&& assert_vertex(L,*L.get_address(Root_vertex_handle(11))); - test = test&& assert_vertex(L,*L.get_address(Root_vertex_handle(13))); - test = test&& L.num_edges()==2; - test = test&&L.contains_edge(*L.get_address(Root_vertex_handle(10)),*L.get_address(Root_vertex_handle(13))); - test=test&&L.contains_edge(*L.get_address(Root_vertex_handle(13)),*L.get_address(Root_vertex_handle(11))); - test=test&&L.num_blockers()==0; - return test; -} - -bool test_link4(){ - Complex complex; - - // Build the complexes - for (int i=0;i<20;i++){ - complex.add_vertex(); - } - for (int i=10;i<15;i++){ - for (int j=i+1;j<15;j++) - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); - } - complex.add_blocker(Simplex_handle(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12),Vertex_handle(13))); - Simplex_handle alpha(Vertex_handle(12),Vertex_handle(14)); - Skeleton_blocker_link_complex<Complex> L(complex,alpha); - // Complexes built - - // verification - bool test1 = L.contains_vertex(*L.get_address(Root_vertex_handle(10))); - bool test2 = L.contains_vertex(*L.get_address(Root_vertex_handle(11))); - bool test3 = L.contains_vertex(*L.get_address(Root_vertex_handle(13))); - bool test4 = L.num_edges()==3; - bool test5 = L.num_blockers()==1; - Root_simplex_handle simplex; - simplex.add_vertex(Root_vertex_handle(10)); - simplex.add_vertex(Root_vertex_handle(11)); - simplex.add_vertex(Root_vertex_handle(13)); - bool test6 = L.contains_blocker(*(L.get_simplex_address(simplex))); - cerr <<"----> Ocomplex \n"; - return test1&&test2&&test3&&test4&&test5&&test6 ; - -} - -bool test_link5(){ - Complex complex(0,new Print_complex_visitor<Vertex_handle>()); - // Build the complexes - build_complete(4,complex); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - - Simplex_handle alpha(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); - - - Skeleton_blocker_link_complex<Complex> L(complex,alpha); // Complexes built - - // Print result - PRINT(complex.to_string()); - cerr <<endl<<endl; - PRINT(L.to_string()); - - // verification - return L.num_vertices()==0; -} - -bool test_link6(){ - Complex complex(0,new Print_complex_visitor<Vertex_handle>()); - // Build the complexes - build_complete(4,complex); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - - Simplex_handle alpha(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); - - Skeleton_blocker_link_complex<Complex> link_blocker_alpha; - - build_link_of_blocker(complex,alpha,link_blocker_alpha); - - // Print result - PRINT(complex.to_string()); - cerr <<endl<<endl; - PRINT(link_blocker_alpha.to_string()); - - // verification - return link_blocker_alpha.num_vertices()==1; -} - - -bool test_link7(){ - Complex complex(0,new Print_complex_visitor<Vertex_handle>()); - // Build the complexes - build_complete(6,complex); - complex.add_vertex(); - complex.add_vertex(); - for(int i = 3; i<6; ++i){ - complex.add_edge(Vertex_handle(i),Vertex_handle(6)); - complex.add_edge(Vertex_handle(i),Vertex_handle(7)); - } - complex.add_edge(Vertex_handle(6),Vertex_handle(7)); - complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - complex.add_blocker(Simplex_handle(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5))); - - Simplex_handle alpha(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); - - Skeleton_blocker_link_complex<Complex> link_blocker_alpha; - - build_link_of_blocker(complex,alpha,link_blocker_alpha); - - //the result should be the edge {6,7} plus the blocker {0,1,2} - - // Print result - PRINT(complex.to_string()); - cerr <<endl<<endl; - DBGVALUE(link_blocker_alpha.to_string()); - - Skeleton_blocker_link_complex<Complex> link_blocker_alpha_cpy = link_blocker_alpha; - - DBGVALUE(link_blocker_alpha_cpy.to_string()); - - bool equal_complexes = - (link_blocker_alpha.num_vertices() == link_blocker_alpha_cpy.num_vertices()) - &&(link_blocker_alpha.num_blockers() == link_blocker_alpha_cpy.num_blockers()) - &&(link_blocker_alpha.num_edges() == link_blocker_alpha_cpy.num_edges()) - ; - DBGVALUE((link_blocker_alpha.num_blockers() == link_blocker_alpha_cpy.num_blockers())); - DBGVALUE((link_blocker_alpha.num_blockers() )); - DBGVALUE(( link_blocker_alpha_cpy.num_blockers())); - - DBGVALUE(equal_complexes); - - // verification - return link_blocker_alpha.num_vertices()==5 && link_blocker_alpha.num_edges()==4 && link_blocker_alpha.num_blockers()==1 && equal_complexes; -} - - - - - - - - -template<typename SimplexHandle> -void add_triangle_edges(int a,int b,int c,list<SimplexHandle>& simplices){ - typedef SimplexHandle Simplex_handle; - typedef typename SimplexHandle::Vertex_handle Vertex_handle; - - simplices.push_back(Simplex_handle(Vertex_handle(a),Vertex_handle(b) )); - simplices.push_back(Simplex_handle(Vertex_handle(b),Vertex_handle(c) )); - simplices.push_back(Simplex_handle(Vertex_handle(c),Vertex_handle(a) )); -} - -template<typename SimplexHandle> -void add_triangle(int a,int b,int c,list<SimplexHandle>& simplices){ - typedef SimplexHandle Simplex_handle; - typedef typename SimplexHandle::Vertex_handle Vertex_handle; - simplices.push_back(Simplex_handle(Vertex_handle(a),Vertex_handle(b),Vertex_handle(c))); -} - -bool test_constructor(){ - list <Simplex_handle> simplices; - - simplices.push_back(Simplex_handle(Vertex_handle(0))); - simplices.push_back(Simplex_handle(Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(3))); - simplices.push_back(Simplex_handle(Vertex_handle(4))); - simplices.push_back(Simplex_handle(Vertex_handle(5))); - - simplices.push_back(Simplex_handle(Vertex_handle(3),Vertex_handle(5) )); - - add_triangle_edges(0,1,5,simplices); - add_triangle_edges(1,2,3,simplices); - add_triangle_edges(2,3,4,simplices); - add_triangle_edges(1,3,4,simplices); - add_triangle_edges(1,2,4,simplices); - - - add_triangle(0,1,5,simplices); - add_triangle(1,2,3,simplices); - add_triangle(1,3,4,simplices); - add_triangle(1,2,4,simplices); - add_triangle(2,3,4,simplices); - - Complex complex(simplices.begin(),simplices.end()); - - PRINT(complex.to_string()); - - return ( complex.num_vertices()==6&&complex.num_edges()==10&& complex.num_blockers()==2); -} - - -list<Simplex_handle> subfaces(Simplex_handle top_face){ - list<Simplex_handle> res; - if(top_face.dimension()==-1) return res; - if(top_face.dimension()==0) { - res.push_back(top_face); - return res; - } - else{ - Vertex_handle first_vertex = top_face.first_vertex(); - top_face.remove_vertex(first_vertex); - res = subfaces(top_face); - list<Simplex_handle> copy = res; - for(auto& simplex : copy){ - simplex.add_vertex(first_vertex); - } - res.push_back(Simplex_handle(first_vertex)); - res.splice(res.end(),copy); - return res; - } -} - - -bool test_constructor2(){ - Simplex_handle simplex; - for(int i =0 ; i < 5;++i) - simplex.add_vertex(static_cast<Vertex_handle>(i)); - - list <Simplex_handle> simplices(subfaces(simplex)); - simplices.remove(simplex); - - Complex complex(simplices.begin(),simplices.end()); - - PRINT(complex.to_string()); - - for(auto b : complex.const_blocker_range()){ - cout << "b:"<<b<<endl; - } - - return ( complex.num_vertices()==5&&complex.num_edges()==10&& complex.num_blockers()==1); -} - - -bool test_constructor3(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - auto subf(subfaces(Sh(Vh(0),Vh(1),Vh(2)))); - subf.pop_back(); //remove max face -> now a blocker 012 - simplices.insert(simplices.begin(),subf.begin(),subf.end()); - DBGCONT(simplices); - Complex complex(simplices.begin(),simplices.end()); - - DBGVALUE(complex.to_string()); - - if(complex.num_blockers()!=1) return false; - Sh expected_blocker(Vh(0),Vh(1),Vh(2)); - for(auto b : complex.const_blocker_range()) - if(*b!=expected_blocker) return false; - - - return complex.num_vertices()==3 && complex.num_blockers()==1; -} - -bool test_constructor4(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - auto subf(subfaces(Sh(Vh(0),Vh(1),Vh(2),Vh(3)))); - simplices.insert(simplices.begin(),subf.begin(),subf.end()); - - simplices.push_back(Sh(Vh(4))); - simplices.push_back(Sh(Vh(4),Vh(1))); - simplices.push_back(Sh(Vh(4),Vh(0))); - - DBGCONT(simplices); - Complex complex(simplices.begin(),simplices.end()); - - DBGVALUE(complex.to_string()); - if(complex.num_blockers()!=1) return false; - Sh expected_blocker(Vh(0),Vh(1),Vh(4)); - for(auto b : complex.const_blocker_range()) - if(*b!=expected_blocker) return false; - - return complex.num_vertices()==5 && complex.num_blockers()==1 && complex.num_edges()==8; -} - - - -bool test_constructor5(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - auto subf(subfaces(Sh(Vh(0),Vh(1),Vh(2)))); - simplices.insert(simplices.begin(),subf.begin(),subf.end()); - - simplices.push_back(Sh(Vh(3))); - simplices.push_back(Sh(Vh(3),Vh(1))); - simplices.push_back(Sh(Vh(3),Vh(2))); - simplices.push_back(Sh(Vh(4))); - simplices.push_back(Sh(Vh(4),Vh(1))); - simplices.push_back(Sh(Vh(4),Vh(0))); - simplices.push_back(Sh(Vh(5))); - simplices.push_back(Sh(Vh(5),Vh(2))); - simplices.push_back(Sh(Vh(5),Vh(0))); - - DBGCONT(simplices); - Complex complex(simplices.begin(),simplices.end()); - - DBGVALUE(complex.to_string()); - - return complex.num_vertices()==6 && complex.num_blockers()==3 && complex.num_edges()==9; -} - - -bool test_constructor6(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - auto subf(subfaces(Sh(Vh(0),Vh(1),Vh(2),Vh(3)))); - for(auto s:subf){ - Sh s1(Vh(0),Vh(1),Vh(2),Vh(3)); - Sh s2(Vh(1),Vh(2),Vh(3)); - if(s!=s1 && s!=s2) simplices.push_back(s); - } - - DBGCONT(simplices); - Complex complex(simplices.begin(),simplices.end()); - - DBGVALUE(complex.to_string()); - - if(complex.num_blockers()!=1) return false; - Sh expected_blocker(Vh(1),Vh(2),Vh(3)); - for(auto b : complex.const_blocker_range()) - if(*b!=expected_blocker) return false; - return complex.num_vertices()==4 && complex.num_blockers()==1 && complex.num_edges()==6; -} - - -bool test_constructor7(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - simplices.push_back(Sh(Vh(0),Vh(1),Vh(2))); - simplices.push_back(Sh(Vh(1),Vh(2),Vh(3))); - simplices.push_back(Sh(Vh(3),Vh(0),Vh(2))); - simplices.push_back(Sh(Vh(3),Vh(0),Vh(1))); - - //get complex from top faces - Complex complex(make_complex_from_top_faces<Complex>(simplices.begin(),simplices.end())); - - DBGVALUE(complex.to_string()); - - if(complex.num_blockers()!=1) return false; - Sh expected_blocker(Vh(0),Vh(1),Vh(2),Vh(3)); - for(auto b : complex.const_blocker_range()) - if(*b!=expected_blocker) return false; - return complex.num_vertices()==4 && complex.num_blockers()==1 && complex.num_edges()==6; -} - - -bool test_constructor8(){ - typedef Vertex_handle Vh; - typedef Simplex_handle Sh; - std::vector<Simplex_handle> simplices; - simplices.push_back(Sh(Vh(0),Vh(1))); - simplices.push_back(Sh(Vh(2),Vh(1))); - simplices.push_back(Sh(Vh(0),Vh(2))); - simplices.push_back(Sh(Vh(3),Vh(1))); - simplices.push_back(Sh(Vh(2),Vh(3))); - - //get complex from top faces - Complex complex(make_complex_from_top_faces<Complex>(simplices.begin(),simplices.end())); - - DBGVALUE(complex.to_string()); - - return complex.num_vertices()==4 && complex.num_blockers()==2 && complex.num_edges()==5; -} - - - - - -int main (int argc, char *argv[]) -{ - Tests tests_complex; - tests_complex.add("test simplex",test_simplex); - tests_complex.add("test_link0",test_link0); - tests_complex.add("test_link1",test_link1); - tests_complex.add("test_link2",test_link2); - tests_complex.add("test_link3",test_link3); - tests_complex.add("test_link4",test_link4); - tests_complex.add("test_link5",test_link5); - tests_complex.add("test_link6",test_link6); - tests_complex.add("test_link7",test_link7); - - tests_complex.add("test iterator vertices 1",test_iterator_vertices1); - tests_complex.add("test iterator vertices 2",test_iterator_vertices2); - tests_complex.add("test iterator edges",test_iterator_edge); - tests_complex.add("test iterator edges 2",test_iterator_edge2); - tests_complex.add("test iterator edges 3",test_iterator_edge3); - - tests_complex.add("test iterator simplices",test_iterator_simplices); - tests_complex.add("test iterator simplices2",test_iterator_simplices2); - tests_complex.add("test iterator simplices3",test_iterator_simplices3); - tests_complex.add("test iterator simplices4",test_iterator_simplices4); - - - tests_complex.add("test iterator blockers",test_iterator_blockers); - tests_complex.add("test_iterator_triangles",test_iterator_triangles); - - tests_complex.add("test_constructor_list_simplices",test_constructor); - tests_complex.add("test_constructor_list_simplices2",test_constructor2); - tests_complex.add("test_constructor_list_simplices3",test_constructor3); - tests_complex.add("test_constructor_list_simplices4",test_constructor4); - tests_complex.add("test_constructor_list_simplices5",test_constructor5); - tests_complex.add("test_constructor_list_simplices6",test_constructor6); - tests_complex.add("test_constructor_list_simplices7",test_constructor7); - tests_complex.add("test_constructor_list_simplices8",test_constructor8); - - - if(tests_complex.run()){ - return EXIT_SUCCESS; - } - else{ - return EXIT_FAILURE; - } - - // test_iterator_simplices(); -} - diff --git a/src/Skeleton_blocker/test/test_skeleton_blocker_complex.cpp b/src/Skeleton_blocker/test/test_skeleton_blocker_complex.cpp new file mode 100644 index 00000000..4f9888ba --- /dev/null +++ b/src/Skeleton_blocker/test/test_skeleton_blocker_complex.cpp @@ -0,0 +1,837 @@ +/* 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/>. + */ +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "skeleton_blocker_complex" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +#include <gudhi/Skeleton_blocker.h> + +template<typename ComplexType> class Skeleton_blocker_sub_complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_traits Traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_complex<Traits> Complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_link_complex<Complex> Skeleton_blocker_link_complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex::Root_vertex_handle Root_vertex_handle; +typedef Complex::Simplex Simplex; +typedef Complex::Root_simplex_handle Root_simplex_handle; +typedef Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; +typedef Complex::Edge_handle Edge_handle; + +bool assert_vertex(Complex &complex, Vertex_handle v) { + //assert(complex.contains(v)); + return complex.contains(static_cast<Simplex> (v)); +} + +bool assert_simplex(Complex &complex, Root_vertex_handle a, Root_vertex_handle b, Root_vertex_handle c) { + return true; + // AddressSimplex simplex((a),(b),(c)); + // return complex.contains(&simplex); +} + +// true iff the blocker (a,b,c) is in complex + +bool assert_blocker(Complex &complex, Root_vertex_handle a, Root_vertex_handle b, Root_vertex_handle c) { + return true; + //return complex.contains_blocker((a),(b),(c)); +} + +// true iff the blocker (a,b,c,d) is in complex + +bool assert_blocker(Complex &complex, Root_vertex_handle a, Root_vertex_handle b, Root_vertex_handle c, Root_vertex_handle d) { + return true; + //Simplex blocker (a,b,c,d); + //return complex.contains_blocker(&blocker); +} + +void build_complete(int n, Complex& complex) { + complex.clear(); + 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)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplex) { + Simplex simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + BOOST_CHECK(simplex.dimension() == 3); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_num_simplices) { + int n = 4; + Complex complex; + build_complete(n, complex); + size_t sum = 0; + for (int i = 0; i < n; i++) { + sum += complex.num_simplices(i); + } + BOOST_CHECK(complex.num_vertices() == n); + BOOST_CHECK(complex.num_edges() == 6); + BOOST_CHECK(sum == 15); + BOOST_CHECK(complex.num_simplices() == 15); +} + + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_vertices1) { + int n = 10; + Complex complex(10); + std::cout << "complex.num_vertices():" << complex.num_vertices() << std::endl; + int num_vertex_seen = 0; + for (auto vi : complex.vertex_range()) { + std::cout << "vertex:" << vi << std::endl; + ++num_vertex_seen; + } + BOOST_CHECK(num_vertex_seen == n); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_vertices2) { + int n = 10; + Complex complex; + build_complete(10, complex); + std::cout << "complex.num_vertices():" << complex.num_vertices() << std::endl; + std::cout << "complex.num_edges():" << complex.num_edges() << std::endl; + int num_vertex_seen = 0; + for (auto vi : complex.vertex_range(Vertex_handle(2))) { + std::cout << "vertex:" << vi << std::endl; + ++num_vertex_seen; + } + std::cout << "num_vertex_seen:" << num_vertex_seen << std::endl; + BOOST_CHECK(num_vertex_seen == (n -1)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_edge) { + const int n = 10; + Complex complex(n); + 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)); + complex.remove_edge(Vertex_handle(2), Vertex_handle(3)); + complex.remove_edge(Vertex_handle(3), Vertex_handle(5)); + std::cout << "complex.num_edges():" << complex.num_edges() << std::endl; + int num_edges_seen = 0; + for (auto edge : complex.edge_range()) { + std::cout << "edge :" << complex[edge] << std::endl; + ++num_edges_seen; + } + + BOOST_CHECK(num_edges_seen == n * (n - 1) / 2 - 2); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_edge2) { + const int n = 10; + Complex complex(n); + 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)); + complex.remove_edge(Vertex_handle(2), Vertex_handle(3)); + complex.remove_edge(Vertex_handle(3), Vertex_handle(5)); + std::cout << "complex.num_edges():" << complex.num_edges() << std::endl; + int num_neigbors_seen = 0; + for (auto neighbor : complex.vertex_range(Vertex_handle(2))) { + std::cout << "neighbor" << neighbor << std::endl; + ++num_neigbors_seen; + } + BOOST_CHECK(num_neigbors_seen == 8); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_triangles) { + const int n = 7; + Complex complex(n); + //create a "ring" around '0' + for (int i = 1; i < n; i++) + complex.add_edge_without_blockers(Vertex_handle(0), Vertex_handle(i)); + for (int i = 1; i < n - 1; i++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(i + 1)); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(6)); + + std::cout << complex.to_string() << std::endl; + + int num_triangles_seen = 0; + //for (auto t : complex.triangle_range(5)){ + for (auto t : complex.triangle_range(Vertex_handle(5))) { + ++num_triangles_seen; + } + BOOST_CHECK(num_triangles_seen == 2); + + num_triangles_seen = 0; + for (auto t : complex.triangle_range(Vertex_handle(0))) { + ++num_triangles_seen; + } + BOOST_CHECK(num_triangles_seen == 6); + + // we now add another triangle + complex.add_vertex(); + complex.add_edge_without_blockers(Vertex_handle(4), Vertex_handle(7)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(7)); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(6))); + num_triangles_seen = 0; + + num_triangles_seen = 0; + for (auto t : complex.triangle_range()) { + ++num_triangles_seen; + } + BOOST_CHECK(num_triangles_seen == 6); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_simplices) { + Complex complex(6); + complex.add_edge_without_blockers(Vertex_handle(0), Vertex_handle(1)); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(2)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(0)); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(3)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(3)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(5)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(5)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(4), Vertex_handle(5)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(4)); + + complex.add_blocker(Simplex(Vertex_handle(2), Vertex_handle(3), Vertex_handle(4), Vertex_handle(5))); + + std::map<Vertex_handle, unsigned> expected_num_simplices; + + expected_num_simplices[Vertex_handle(0)] = 4; + expected_num_simplices[Vertex_handle(1)] = 6; + expected_num_simplices[Vertex_handle(2)] = 11; + expected_num_simplices[Vertex_handle(3)] = 9; + expected_num_simplices[Vertex_handle(4)] = 7; + expected_num_simplices[Vertex_handle(5)] = 7; + + for (auto pair : expected_num_simplices) { + std::cout << "found list: "; + unsigned num_simplices_around = 0; + for (const auto& simplex : complex.star_simplex_range(pair.first)) { + simplex.dimension(); + std::cout << simplex << " - "; + ++num_simplices_around; + } + + BOOST_CHECK(num_simplices_around == pair.second); + + std::cout << std::endl << "current vertex:" << pair.first << " - "; + std::cout << "expected_num_simplices:" << pair.second << " - "; + std::cout << "found:" << num_simplices_around << std::endl; + } +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_simplices2) { + Complex complex(2); + complex.add_edge_without_blockers(Vertex_handle(0), Vertex_handle(1)); + + // Check there is no triangle + BOOST_CHECK(std::distance(complex.triangle_range().begin(), complex.triangle_range().end()) == 0); + + // Star(0) is [{0},{0,1}] + BOOST_CHECK(std::distance(complex.star_simplex_range(Vertex_handle(0)).begin(), + complex.star_simplex_range(Vertex_handle(0)).end()) == 2); + + // No blocker + BOOST_CHECK(std::distance(complex.blocker_range(Vertex_handle(0)).begin(), + complex.blocker_range(Vertex_handle(0)).end()) == 0); + + // Complex is [{0},{0,1},{1}] + BOOST_CHECK(std::distance(complex.complex_simplex_range().begin(), + complex.complex_simplex_range().end()) == 3); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_simplices3) { + Complex complex(3); + complex.add_edge_without_blockers(Vertex_handle(0), Vertex_handle(1)); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(2)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(0)); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); + + // Check there is no triangle + BOOST_CHECK(std::distance(complex.triangle_range().begin(), complex.triangle_range().end()) == 0); + + // Star(0) is [{0},{0,1},{0,2}] + BOOST_CHECK(std::distance(complex.star_simplex_range(Vertex_handle(0)).begin(), + complex.star_simplex_range(Vertex_handle(0)).end()) == 3); + + // blocker(0) is [{0,1,2}] + BOOST_CHECK(std::distance(complex.blocker_range(Vertex_handle(0)).begin(), + complex.blocker_range(Vertex_handle(0)).end()) == 1); + + // Complex is [{0},{0,1},{0,2},{1},{1,2},{2}] + BOOST_CHECK(std::distance(complex.complex_simplex_range().begin(), + complex.complex_simplex_range().end()) == 6); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_simplices4) { + Complex empty_complex; + for (auto v : empty_complex.vertex_range()) { + std::cout << v; + BOOST_CHECK(false); + } + for (auto e : empty_complex.edge_range()) { + std::cout << e; + BOOST_CHECK(false); + } + for (auto t : empty_complex.triangle_range()) { + std::cout << t; + BOOST_CHECK(false); + } + for (auto s : empty_complex.complex_simplex_range()) { + std::cout << s; + BOOST_CHECK(false); + } +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_coboundary) { + Complex c; + build_complete(4, c); + c.remove_edge(Vertex_handle(1), Vertex_handle(3)); + std::cout << c.to_string(); + Simplex s02(Vertex_handle(0), Vertex_handle(2)); + int n = 0; + std::set<Simplex> expected; + expected.insert(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); + expected.insert(Simplex(Vertex_handle(0), Vertex_handle(2), Vertex_handle(3))); + for (const auto & s : c.coboundary_range(s02)) { + BOOST_CHECK(expected.find(s) != expected.end()); + ++n; + } + BOOST_CHECK(n == 2); +} + +template<typename Map> +auto blocker_range(Map map) -> decltype(map | boost::adaptors::map_values) { + return map | boost::adaptors::map_values; +} + +BOOST_AUTO_TEST_CASE(test_skeleton_iterator_blockers) { + Complex complex; + Simplex alpha; + Simplex vertex_set_expected; + // Build the complexes + for (int i = 0; i < 20; i++) { + complex.add_vertex(); + } + for (int i = 10; i < 15; i++) { + for (int j = i + 1; j < 15; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + } + + std::vector<Simplex> myBlockers; + myBlockers.push_back(Simplex(Vertex_handle(10), Vertex_handle(11), Vertex_handle(12))); + myBlockers.push_back(Simplex(Vertex_handle(2), Vertex_handle(1), Vertex_handle(10))); + myBlockers.push_back(Simplex(Vertex_handle(10), Vertex_handle(9), Vertex_handle(15))); + myBlockers.push_back(Simplex(Vertex_handle(1), Vertex_handle(9), Vertex_handle(8))); + + for (auto blocker : myBlockers) + complex.add_blocker(blocker); + + int num_blockers = 0; + for (auto blockers : complex.blocker_range(Vertex_handle(10))) { + // Only the first 3 blockers contain vertex 10 + BOOST_CHECK(*blockers == myBlockers[num_blockers]); + num_blockers++; + } + BOOST_CHECK(num_blockers == 3); + + num_blockers = 0; + for (auto blockers : complex.blocker_range()) { +// If not windows - _WIN32 is for windows 32 and 64 bits +#ifndef _WIN32 + for (auto block_ptr = myBlockers.begin(); block_ptr < myBlockers.end(); block_ptr++) + if (*block_ptr == *blockers) + myBlockers.erase(block_ptr); +#endif + num_blockers++; + } + BOOST_CHECK(num_blockers == 4); +// If not windows - _WIN32 is for windows 32 and 64 bits +#ifndef _WIN32 + BOOST_CHECK(myBlockers.empty()); +#endif +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link0) { + enum { a, b, c, d, n }; + Complex complex(n); + complex.add_edge_without_blockers(Vertex_handle(b), Vertex_handle(c)); + complex.add_edge_without_blockers(Vertex_handle(c), Vertex_handle(d)); + Simplex alpha = Simplex(Vertex_handle(c)); + Skeleton_blocker_link_complex L(complex, alpha); + + auto L2 = complex.link(alpha); + BOOST_CHECK(L == L2); + + std::cout << L.to_string(); + + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(b)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(d)))); + BOOST_CHECK(L.num_edges() == 0); + BOOST_CHECK(L.num_blockers() == 0); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link1) { + Complex complex; + + // Build the complexes + for (int i = 0; i < 20; i++) { + complex.add_vertex(); + } + for (int i = 10; i < 15; i++) { + for (int j = i + 1; j < 15; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + } + Simplex alpha(Vertex_handle(12), Vertex_handle(14)); + Skeleton_blocker_link_complex L(complex, alpha); + // Complexes built + + auto L2 = complex.link(alpha); + BOOST_CHECK(L == L2); + + // verification + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(10)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(11)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(13)))); + BOOST_CHECK(L.num_edges() == 3); + BOOST_CHECK(L.num_blockers() == 0); + Root_simplex_handle simplex; + simplex.add_vertex(Root_vertex_handle(10)); + simplex.add_vertex(Root_vertex_handle(11)); + simplex.add_vertex(Root_vertex_handle(13)); + BOOST_CHECK(L.get_simplex_address(simplex)); + BOOST_CHECK(L.contains(*(L.get_simplex_address(simplex)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link2) { + Complex complex; + + Simplex alpha; + Simplex vertex_set_expected; + // Build the complexes + for (int i = 0; i < 20; i++) { + complex.add_vertex(); + } + for (int i = 10; i < 15; i++) { + for (int j = i + 1; j < 15; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + } + complex.add_blocker(Simplex(Vertex_handle(10), Vertex_handle(11), Vertex_handle(13))); + alpha = Simplex(Vertex_handle(12), Vertex_handle(14)); + Skeleton_blocker_link_complex L(complex, alpha); + // Complexes built + + // Print result + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + std::cout << "L= Link_complex(" << alpha << ") : \n" << L.to_string(); + + auto L2 = complex.link(alpha); + BOOST_CHECK(L == L2); + + + // verification + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(10)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(11)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(13)))); + BOOST_CHECK(L.num_edges() == 3); + BOOST_CHECK(L.num_blockers() == 1); + Root_simplex_handle simplex; + simplex.add_vertex(Root_vertex_handle(10)); + simplex.add_vertex(Root_vertex_handle(11)); + simplex.add_vertex(Root_vertex_handle(13)); + BOOST_CHECK(L.contains_blocker(*(L.get_simplex_address(simplex)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link3) { + Complex complex; + + Simplex alpha; + Simplex vertex_set_expected; + // Build the complexes + for (int i = 0; i < 20; i++) { + complex.add_vertex(); + } + for (int i = 10; i < 15; i++) { + for (int j = i + 1; j < 15; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + } + complex.add_blocker(Simplex(Vertex_handle(10), Vertex_handle(11), Vertex_handle(12))); + alpha = Simplex(Vertex_handle(12), Vertex_handle(14)); + Skeleton_blocker_link_complex L(complex, alpha); + // Complexes built + + // Print result + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + std::cout << "L= Link_complex(" << alpha << ") : \n" << L.to_string(); + + auto L2 = complex.link(alpha); + BOOST_CHECK(L == L2); + + // verification + BOOST_CHECK(L.contains(static_cast<Simplex> (*L.get_address(Root_vertex_handle(10))))); + BOOST_CHECK(L.contains(static_cast<Simplex> (*L.get_address(Root_vertex_handle(11))))); + BOOST_CHECK(L.contains(static_cast<Simplex> (*L.get_address(Root_vertex_handle(13))))); + BOOST_CHECK(L.num_edges() == 2); + BOOST_CHECK(L.contains_edge(*L.get_address(Root_vertex_handle(10)), *L.get_address(Root_vertex_handle(13)))); + BOOST_CHECK(L.contains_edge(*L.get_address(Root_vertex_handle(13)), *L.get_address(Root_vertex_handle(11)))); + BOOST_CHECK(L.num_blockers() == 0); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link4) { + Complex complex; + + // Build the complexes + for (int i = 0; i < 20; i++) { + complex.add_vertex(); + } + for (int i = 10; i < 15; i++) { + for (int j = i + 1; j < 15; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + } + complex.add_blocker(Simplex(Vertex_handle(10), Vertex_handle(11), Vertex_handle(12), Vertex_handle(13))); + Simplex alpha(Vertex_handle(12), Vertex_handle(14)); + Skeleton_blocker_link_complex L(complex, alpha); + // Complexes built + + // verification + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(10)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(11)))); + BOOST_CHECK(L.contains_vertex(*L.get_address(Root_vertex_handle(13)))); + BOOST_CHECK(L.num_edges() == 3); + BOOST_CHECK(L.num_blockers() == 1); + Root_simplex_handle simplex; + simplex.add_vertex(Root_vertex_handle(10)); + simplex.add_vertex(Root_vertex_handle(11)); + simplex.add_vertex(Root_vertex_handle(13)); + BOOST_CHECK(L.contains_blocker(*(L.get_simplex_address(simplex)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link5) { + Complex complex(0); + // Build the complexes + build_complete(4, complex); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3))); + + Simplex alpha(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2)); + Skeleton_blocker_link_complex L(complex, alpha); + // Complexes built + + // Print result + std::cout << "Complex: " << complex.to_string()<< std::endl << std::endl; + std::cout << "Link: " << L.to_string() << std::endl; + + // verification + BOOST_CHECK(L.num_vertices() == 0); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link6) { + Complex complex(0); + // Build the complexes + build_complete(4, complex); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); + + Simplex alpha(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2)); + + Skeleton_blocker_link_complex link_blocker_alpha; + + build_link_of_blocker(complex, alpha, link_blocker_alpha); + + // Print result + std::cout << "Complex: " << complex.to_string()<< std::endl << std::endl; + std::cout << "Link: " << link_blocker_alpha.to_string() << std::endl; + + // verification + BOOST_CHECK(link_blocker_alpha.num_vertices() == 1); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_link7) { + Complex complex(0); + // Build the complexes + build_complete(6, complex); + complex.add_vertex(); + complex.add_vertex(); + for (int i = 3; i < 6; ++i) { + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(6)); + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(7)); + } + complex.add_edge_without_blockers(Vertex_handle(6), Vertex_handle(7)); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); + complex.add_blocker(Simplex(Vertex_handle(3), Vertex_handle(4), Vertex_handle(5))); + + Simplex alpha(Vertex_handle(3), Vertex_handle(4), Vertex_handle(5)); + + Skeleton_blocker_link_complex link_blocker_alpha; + + build_link_of_blocker(complex, alpha, link_blocker_alpha); + + //the result should be the edge {6,7} plus the blocker {0,1,2} + + // Print result + std::cout << "Complex: " << complex.to_string()<< std::endl << std::endl; + std::cout << "Link: " << link_blocker_alpha.to_string() << std::endl; + + Skeleton_blocker_link_complex link_blocker_alpha_cpy = link_blocker_alpha; + + std::cout << "Link copy: " << link_blocker_alpha_cpy.to_string() << std::endl; + + BOOST_CHECK(link_blocker_alpha.num_vertices() == link_blocker_alpha_cpy.num_vertices()); + BOOST_CHECK(link_blocker_alpha.num_blockers() == link_blocker_alpha_cpy.num_blockers()); + BOOST_CHECK(link_blocker_alpha.num_edges() == link_blocker_alpha_cpy.num_edges()); + BOOST_CHECK((link_blocker_alpha.num_blockers() == link_blocker_alpha_cpy.num_blockers())); + + // verification + BOOST_CHECK(link_blocker_alpha.num_vertices() == 5); + BOOST_CHECK(link_blocker_alpha.num_edges() == 4); + BOOST_CHECK(link_blocker_alpha.num_blockers() == 1); +} + +template<typename SimplexHandle> +void add_triangle_edges(int a, int b, int c, std::list<SimplexHandle>& simplices) { + typedef SimplexHandle Simplex; + typedef typename SimplexHandle::Vertex_handle Vertex_handle; + + simplices.push_back(Simplex(Vertex_handle(a), Vertex_handle(b))); + simplices.push_back(Simplex(Vertex_handle(b), Vertex_handle(c))); + simplices.push_back(Simplex(Vertex_handle(c), Vertex_handle(a))); +} + +template<typename SimplexHandle> +void add_triangle(int a, int b, int c, std::list<SimplexHandle>& simplices) { + typedef SimplexHandle Simplex; + typedef typename SimplexHandle::Vertex_handle Vertex_handle; + simplices.push_back(Simplex(Vertex_handle(a), Vertex_handle(b), Vertex_handle(c))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor) { + std::list <Simplex> simplices; + + 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(3))); + simplices.push_back(Simplex(Vertex_handle(4))); + simplices.push_back(Simplex(Vertex_handle(5))); + + simplices.push_back(Simplex(Vertex_handle(3), Vertex_handle(5))); + + add_triangle_edges(0, 1, 5, simplices); + add_triangle_edges(1, 2, 3, simplices); + add_triangle_edges(2, 3, 4, simplices); + add_triangle_edges(1, 3, 4, simplices); + add_triangle_edges(1, 2, 4, simplices); + + add_triangle(0, 1, 5, simplices); + add_triangle(1, 2, 3, simplices); + add_triangle(1, 3, 4, simplices); + add_triangle(1, 2, 4, simplices); + add_triangle(2, 3, 4, simplices); + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 1:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_vertices() == 6); + BOOST_CHECK(complex.num_edges() == 10); + BOOST_CHECK(complex.num_blockers() == 2); +} + +std::list<Simplex> subfaces(Simplex top_face) { + std::list<Simplex> res; + if (top_face.dimension() == -1) return res; + if (top_face.dimension() == 0) { + res.push_back(top_face); + return res; + } else { + Vertex_handle first_vertex = top_face.first_vertex(); + top_face.remove_vertex(first_vertex); + res = subfaces(top_face); + std::list<Simplex> copy = res; + for (auto& simplex : copy) { + simplex.add_vertex(first_vertex); + } + res.push_back(Simplex(first_vertex)); + res.splice(res.end(), copy); + return res; + } +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor2) { + Simplex simplex; + for (int i = 0; i < 5; ++i) + simplex.add_vertex(static_cast<Vertex_handle> (i)); + + std::list <Simplex> simplices(subfaces(simplex)); + simplices.remove(simplex); + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 2:\n" << complex.to_string(); + + for (auto b : complex.const_blocker_range()) { + std::cout << "b:" << b << std::endl; + } + + BOOST_CHECK(complex.num_vertices() == 5); + BOOST_CHECK(complex.num_edges() == 10); + BOOST_CHECK(complex.num_blockers() == 1); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor3) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + auto subf(subfaces(Sh(Vh(0), Vh(1), Vh(2)))); + subf.pop_back(); //remove max face -> now a blocker 012 + simplices.insert(simplices.begin(), subf.begin(), subf.end()); + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 3:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_blockers() == 1); + Sh expected_blocker(Vh(0), Vh(1), Vh(2)); + for (auto b : complex.const_blocker_range()) + BOOST_CHECK(*b == expected_blocker); + + + BOOST_CHECK(complex.num_vertices() == 3); + BOOST_CHECK(complex.num_blockers() == 1); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor4) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + auto subf(subfaces(Sh(Vh(0), Vh(1), Vh(2), Vh(3)))); + simplices.insert(simplices.begin(), subf.begin(), subf.end()); + + simplices.push_back(Sh(Vh(4))); + simplices.push_back(Sh(Vh(4), Vh(1))); + simplices.push_back(Sh(Vh(4), Vh(0))); + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 4:\n" << complex.to_string(); + BOOST_CHECK(complex.num_blockers() == 1); + Sh expected_blocker(Vh(0), Vh(1), Vh(4)); + for (auto b : complex.const_blocker_range()) + BOOST_CHECK(*b == expected_blocker); + + BOOST_CHECK(complex.num_vertices() == 5); + BOOST_CHECK(complex.num_blockers() == 1); + BOOST_CHECK(complex.num_edges() == 8); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor5) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + auto subf(subfaces(Sh(Vh(0), Vh(1), Vh(2)))); + simplices.insert(simplices.begin(), subf.begin(), subf.end()); + + simplices.push_back(Sh(Vh(3))); + simplices.push_back(Sh(Vh(3), Vh(1))); + simplices.push_back(Sh(Vh(3), Vh(2))); + simplices.push_back(Sh(Vh(4))); + simplices.push_back(Sh(Vh(4), Vh(1))); + simplices.push_back(Sh(Vh(4), Vh(0))); + simplices.push_back(Sh(Vh(5))); + simplices.push_back(Sh(Vh(5), Vh(2))); + simplices.push_back(Sh(Vh(5), Vh(0))); + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 5:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_vertices() == 6); + BOOST_CHECK(complex.num_blockers() == 3); + BOOST_CHECK(complex.num_edges() == 9); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor6) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + auto subf(subfaces(Sh(Vh(0), Vh(1), Vh(2), Vh(3)))); + for (auto s : subf) { + Sh s1(Vh(0), Vh(1), Vh(2), Vh(3)); + Sh s2(Vh(1), Vh(2), Vh(3)); + if (s != s1 && s != s2) simplices.push_back(s); + } + + Complex complex(simplices.begin(), simplices.end()); + + std::cout << "Constructor 6:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_vertices() == 4); + BOOST_CHECK(complex.num_blockers() == 1); + BOOST_CHECK(complex.num_edges() == 6); + Sh expected_blocker(Vh(1), Vh(2), Vh(3)); + for (auto b : complex.const_blocker_range()) + BOOST_CHECK(*b == expected_blocker); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor7) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + simplices.push_back(Sh(Vh(0), Vh(1), Vh(2))); + simplices.push_back(Sh(Vh(1), Vh(2), Vh(3))); + simplices.push_back(Sh(Vh(3), Vh(0), Vh(2))); + simplices.push_back(Sh(Vh(3), Vh(0), Vh(1))); + + //get complex from top faces + Complex complex(Gudhi::skeleton_blocker::make_complex_from_top_faces<Complex>(simplices.begin(), simplices.end())); + + std::cout << "Constructor 7:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_vertices() == 4); + BOOST_CHECK(complex.num_blockers() == 1); + BOOST_CHECK(complex.num_edges() == 6); + Sh expected_blocker(Vh(0), Vh(1), Vh(2), Vh(3)); + for (auto b : complex.const_blocker_range()) + BOOST_CHECK(*b == expected_blocker); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_complex_constructor8) { + typedef Vertex_handle Vh; + typedef Simplex Sh; + std::vector<Simplex> simplices; + simplices.push_back(Sh(Vh(0), Vh(1))); + simplices.push_back(Sh(Vh(2), Vh(1))); + simplices.push_back(Sh(Vh(0), Vh(2))); + simplices.push_back(Sh(Vh(3), Vh(1))); + simplices.push_back(Sh(Vh(2), Vh(3))); + + //get complex from top faces + Complex complex(Gudhi::skeleton_blocker::make_complex_from_top_faces<Complex>(simplices.begin(), simplices.end())); + + std::cout << "Constructor 8:\n" << complex.to_string(); + + BOOST_CHECK(complex.num_vertices() == 4); + BOOST_CHECK(complex.num_blockers() == 2); + BOOST_CHECK(complex.num_edges() == 5); +} diff --git a/src/Skeleton_blocker/test/test_skeleton_blocker_geometric_complex.cpp b/src/Skeleton_blocker/test/test_skeleton_blocker_geometric_complex.cpp new file mode 100644 index 00000000..d035b2c3 --- /dev/null +++ b/src/Skeleton_blocker/test/test_skeleton_blocker_geometric_complex.cpp @@ -0,0 +1,125 @@ +/* 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/>. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "skeleton_blocker_geometric_complex" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +#include <gudhi/Skeleton_blocker.h> + +struct Geometry_trait { + typedef std::vector<double> Point; +}; + +typedef Geometry_trait::Point Point; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_geometric_traits<Geometry_trait> Complex_geometric_traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_geometric_complex< Complex_geometric_traits > Complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex_geometric_traits::Root_vertex_handle Root_vertex_handle; + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_off_reader_writer) { + Complex complex; + Gudhi::skeleton_blocker::Skeleton_blocker_off_reader<Complex> off_reader("test2.off", complex); + BOOST_CHECK(off_reader.is_valid()); + + std::cout << "complex has " << + complex.num_vertices() << " vertices, " << + complex.num_blockers() << " blockers, " << + complex.num_edges() << " edges and " << + complex.num_triangles() << " triangles."; + + BOOST_CHECK(complex.num_vertices() == 7); + BOOST_CHECK(complex.num_edges() == 12); + BOOST_CHECK(complex.num_triangles() == 6); + + Gudhi::skeleton_blocker::Skeleton_blocker_off_writer<Complex> off_writer("tmp.off", complex); + Complex same; + Gudhi::skeleton_blocker::Skeleton_blocker_off_reader<Complex> off_reader2("tmp.off", same); + + std::cout << "\ncomplex:" << complex.to_string() << std::endl; + std::cout << "\nsame:" << same.to_string() << std::endl; + + BOOST_CHECK(complex == same); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_abstract_link) { + Complex complex; + Gudhi::skeleton_blocker::Skeleton_blocker_off_reader<Complex> off_reader("test2.off", complex); + BOOST_CHECK(off_reader.is_valid()); + + std::cout << "complex has " << + complex.num_vertices() << " vertices, " << + complex.num_blockers() << " blockers, " << + complex.num_edges() << " edges and " << + complex.num_triangles() << " triangles."; + + BOOST_CHECK(complex.num_vertices() == 7); + BOOST_CHECK(complex.num_edges() == 12); + BOOST_CHECK(complex.num_triangles() == 6); + + auto link_0 = complex.abstract_link(Vertex_handle(0)); + + std::cout << "\n link(0):" << link_0.to_string() << std::endl; + + BOOST_CHECK(link_0.num_vertices() == 2); + BOOST_CHECK(link_0.num_edges() == 1); + BOOST_CHECK(link_0.num_blockers() == 0); + + // Check the 2 link vertices + auto vertex_handle = link_0.vertex_range().begin(); + BOOST_CHECK(link_0[*vertex_handle].get_id() == Root_vertex_handle(1)); + vertex_handle++; + BOOST_CHECK(link_0[*(vertex_handle)].get_id() == Root_vertex_handle(4)); + + // Check the lonely link edge + auto edge_handle = link_0.edge_range().begin(); + BOOST_CHECK(link_0[*edge_handle].first() == Root_vertex_handle(1)); + BOOST_CHECK(link_0[*(edge_handle)].second() == Root_vertex_handle(4)); + + auto link_geometric_0 = complex.link(Vertex_handle(0)); + std::cout << "\n link_geometric(0):" << link_geometric_0.to_string() << std::endl; + + BOOST_CHECK(link_0 == link_geometric_0); + + auto print_point = [&](Vertex_handle v) { + for (auto x : link_geometric_0.point(v)) std::cout << x << " "; + std::cout << std::endl; + }; + + std::for_each(link_geometric_0.vertex_range().begin(), link_geometric_0.vertex_range().end(), print_point); + + // Check the 2 link vertices + vertex_handle = link_geometric_0.vertex_range().begin(); + std::vector<double> point_1 = {0,2,0}; + std::vector<double> point_4 = {-1,1,0}; + BOOST_CHECK(link_geometric_0.point(*vertex_handle) == point_1); + vertex_handle++; + BOOST_CHECK(link_geometric_0.point(*vertex_handle) == point_4); + +} diff --git a/src/Skeleton_blocker/test/test_skeleton_blocker_simplifiable.cpp b/src/Skeleton_blocker/test/test_skeleton_blocker_simplifiable.cpp new file mode 100644 index 00000000..360b91db --- /dev/null +++ b/src/Skeleton_blocker/test/test_skeleton_blocker_simplifiable.cpp @@ -0,0 +1,360 @@ +/* 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/>. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "skeleton_blocker_simplifiable" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + +#include <gudhi/Skeleton_blocker.h> + +template<typename ComplexType> class Skeleton_blocker_sub_complex; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simple_traits Traits; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_complex<Traits> Complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex::Root_vertex_handle Root_vertex_handle; +typedef Gudhi::skeleton_blocker::Skeleton_blocker_simplex<Vertex_handle> Simplex; + + +void build_complete(int n, Complex& complex) { + complex.clear(); + 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)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_contraction1) { + enum { a, b, x, y, z, n }; + Complex complex(n); + build_complete(n, complex); + complex.remove_edge(static_cast<Vertex_handle> (b), static_cast<Vertex_handle> (z)); + complex.add_blocker(Simplex(static_cast<Vertex_handle> (a), static_cast<Vertex_handle> (x), + static_cast<Vertex_handle> (y))); + complex.add_blocker(Simplex(static_cast<Vertex_handle> (b), static_cast<Vertex_handle> (x), + static_cast<Vertex_handle> (y))); + + // Print result + std::cout << "complex before complex" << complex.to_string() << std::endl; + + std::cout << std::endl << std::endl; + complex.contract_edge(static_cast<Vertex_handle> (a), static_cast<Vertex_handle> (b)); + // Print result + std::cout << "ContractEdge(0,1)\n"; + PRINT(complex.to_string()); + + // verification + for (int i = 0; i < 5; i++) + if (i != 1) BOOST_CHECK(complex.contains(Simplex(static_cast<Vertex_handle> (i)))); + BOOST_CHECK(!complex.contains_edge(static_cast<Vertex_handle> (a), static_cast<Vertex_handle> (b))); + + BOOST_CHECK(complex.contains_blocker(Simplex(*complex.get_address(Root_vertex_handle(a)), + *complex.get_address(Root_vertex_handle(x)), + *complex.get_address(Root_vertex_handle(y))))); + + BOOST_CHECK(complex.num_edges() == 6); + BOOST_CHECK(complex.num_blockers() == 1); + Simplex sigma; + sigma.add_vertex(static_cast<Vertex_handle> (a)); + sigma.add_vertex(static_cast<Vertex_handle> (x)); + sigma.add_vertex(static_cast<Vertex_handle> (y)); + sigma.add_vertex(static_cast<Vertex_handle> (z)); + BOOST_CHECK(!(complex.contains(sigma))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_contraction2) { + enum { a, b, x, y, z, n }; + Complex complex(n); + build_complete(n, complex); + complex.remove_edge(static_cast<Vertex_handle> (b), static_cast<Vertex_handle> (x)); + Simplex blocker; + blocker.add_vertex(static_cast<Vertex_handle> (a)); + blocker.add_vertex(static_cast<Vertex_handle> (y)); + blocker.add_vertex(static_cast<Vertex_handle> (z)); + + complex.add_blocker(blocker); + + // Print result + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + complex.contract_edge(static_cast<Vertex_handle> (a), static_cast<Vertex_handle> (b)); + + std::cout << "complex.ContractEdge(a,b)" << complex.to_string(); + + std::cout << std::endl << std::endl; + + // there should be one blocker (a,c,d,e) in the complex + BOOST_CHECK(complex.contains_blocker(Simplex(static_cast<Vertex_handle> (a), static_cast<Vertex_handle> (x), + static_cast<Vertex_handle> (y), static_cast<Vertex_handle> (z)))); + BOOST_CHECK(complex.num_blockers() == 1); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_link_condition1) { + Complex complex(0); + // Build the complexes + build_complete(4, complex); + complex.add_blocker(Simplex(static_cast<Vertex_handle> (0), static_cast<Vertex_handle> (1), static_cast<Vertex_handle> (2))); + + // Print result + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + + BOOST_CHECK(complex.link_condition(Vertex_handle(1), Vertex_handle(2), true)); + + BOOST_CHECK(!complex.link_condition(Vertex_handle(1), Vertex_handle(2), false)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_collapse0) { + Complex complex(5); + build_complete(4, complex); + complex.add_vertex(); + complex.add_edge_without_blockers(static_cast<Vertex_handle> (2), static_cast<Vertex_handle> (4)); + complex.add_edge_without_blockers(static_cast<Vertex_handle> (3), static_cast<Vertex_handle> (4)); + // Print result + std::cout << "initial complex :\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + Simplex simplex_123(static_cast<Vertex_handle> (1), static_cast<Vertex_handle> (2), static_cast<Vertex_handle> (3)); + complex.remove_star(simplex_123); + std::cout << "complex.remove_star(1,2,3):\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + // verification + BOOST_CHECK(complex.contains_blocker(simplex_123)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_collapse1) { + Complex complex(5); + build_complete(4, complex); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3))); + // Print result + std::cout << "initial complex :\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + Simplex simplex_123(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + complex.remove_star(simplex_123); + std::cout << "complex.remove_star(1,2,3):\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + // verification + BOOST_CHECK(complex.contains_blocker(simplex_123)); + BOOST_CHECK(complex.num_blockers() == 1); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_collapse2) { + Complex complex(5); + build_complete(4, complex); + complex.add_vertex(); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(4)); + complex.add_blocker(Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3), Vertex_handle(4))); + // Print result + std::cout << "initial complex :\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + Simplex sigma(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + complex.remove_star(sigma); + std::cout << "complex.remove_star(1,2,3):\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + // verification + BOOST_CHECK(!complex.contains_blocker(Simplex(Vertex_handle(1), Vertex_handle(2), + Vertex_handle(3), Vertex_handle(4)))); + BOOST_CHECK(complex.contains_blocker(sigma)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_collapse3) { + Complex complex(5); + build_complete(4, complex); + complex.add_vertex(); + complex.add_edge_without_blockers(Vertex_handle(1), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(4)); + complex.add_blocker(Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3), Vertex_handle(4))); + // Print result + std::cout << "initial complex:\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + complex.remove_star(static_cast<Vertex_handle> (2)); + std::cout << "complex after remove star of 2:\n" << complex.to_string(); + + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(1), Vertex_handle(3), Vertex_handle(4)))); + BOOST_CHECK(!complex.contains_blocker(Simplex(Vertex_handle(1), Vertex_handle(2), + Vertex_handle(3), Vertex_handle(4)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_add_simplex) { + Complex complex(4); + build_complete(4, complex); + complex.add_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(3))); + std::cout << "initial complex:\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + complex.add_simplex(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(3))); + std::cout << "complex after add_simplex:\n" << complex.to_string(); + BOOST_CHECK(complex.num_blockers() == 1); + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), + Vertex_handle(2), Vertex_handle(3)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_add_simplex2) { + Complex complex; + build_complete(4, complex); + // Print result + std::cout << "initial complex:\n" << complex.to_string(); + std::cout << std::endl << std::endl; + + Complex copy(complex.num_vertices()); + + std::vector<Simplex> simplices(complex.complex_simplex_range().begin(), complex.complex_simplex_range().end()); + sort(simplices.begin(), simplices.end(), [&](const Simplex& s1, const Simplex & s2) { + return s1.dimension() < s2.dimension(); + }); + for (const auto & simplex : simplices) { + if (!copy.contains(simplex) && simplex.dimension() == 1) + copy.add_edge_without_blockers(simplex.first_vertex(), simplex.last_vertex()); + if (!copy.contains(simplex) && simplex.dimension() > 1) + copy.add_simplex(simplex); + } + + std::cout << "complex after add_simplex:\n" << copy.to_string(); + + BOOST_CHECK(complex.num_blockers() == copy.num_blockers()); + BOOST_CHECK(complex.num_edges() == copy.num_edges()); + BOOST_CHECK(complex.num_vertices() == copy.num_vertices()); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_add_simplex3) { + Complex complex(5); + build_complete(5, complex); + complex.remove_edge(Vertex_handle(3), Vertex_handle(4)); + Simplex sigma(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2)); + complex.add_blocker(sigma); + // Print result + std::cout << "initial complex:\n" << complex.to_string(); + std::cout << std::endl << std::endl; + complex.add_simplex(sigma); + //should create two blockers 0123 and 0124 + std::cout << "complex after adding simplex 012:\n" << complex.to_string(); + BOOST_CHECK(complex.num_blockers() == 2); + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), + Vertex_handle(2), Vertex_handle(3)))); + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), + Vertex_handle(2), Vertex_handle(4)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_add_simplex4) { + int n = 6; + Complex complex(n); + + // add all simplex 0..n without i + for (int i = 0; i < n; i++) { + Simplex s; + for (int k = 0; k < n; k++) + s.add_vertex(Vertex_handle(k)); + s.remove_vertex(Vertex_handle(i)); + complex.add_simplex(s); + + //at step i there is only blocker 0..i + BOOST_CHECK(!(i < 2 && complex.num_blockers() > 0)); + if (i >= 2 && complex.num_blockers() != 1) { + Simplex b; + for (int k = 0; k < i; k++) + b.add_vertex(Vertex_handle(i)); + BOOST_CHECK(complex.contains_blocker(b)); + } + } + Simplex s; + for (int k = 0; k < n; k++) + s.add_vertex(Vertex_handle(k)); + BOOST_CHECK(complex.num_blockers() == 1); + BOOST_CHECK(complex.contains_blocker(s)); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_add_edge) { + Complex complex(4); + for (unsigned i = 0u; i < 4; i++) + complex.add_edge(Vertex_handle(i), Vertex_handle((i + 1) % 4)); + + // Print result + std::cout << "initial complex:\n" << complex.to_string(); + std::cout << std::endl << std::endl; + complex.add_edge(Vertex_handle(1), Vertex_handle(3)); + //should create two blockers 013 and 012 + std::cout << "complex after adding edge 13:\n" << complex.to_string(); + BOOST_CHECK(complex.num_blockers() == 2); + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(3)))); + BOOST_CHECK(complex.contains_blocker(Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)))); +} + +BOOST_AUTO_TEST_CASE(test_skeleton_blocker_simplifiable_remove_popable_blockers) { + Complex complex; + build_complete(4, complex); + complex.add_vertex(); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(4)); + Simplex sigma1 = Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + Simplex sigma2 = Simplex(Vertex_handle(2), Vertex_handle(3), Vertex_handle(4)); + + complex.add_blocker(sigma1); + complex.add_blocker(sigma2); + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + std::cout << "complex.RemovePopableBlockers();" << std::endl; + complex.remove_popable_blockers(); + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + + BOOST_CHECK(complex.num_blockers() == 1); + + // test 2 + complex.clear(); + build_complete(4, complex); + complex.add_vertex(); + complex.add_vertex(); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(4)); + complex.add_edge_without_blockers(Vertex_handle(2), Vertex_handle(5)); + complex.add_edge_without_blockers(Vertex_handle(3), Vertex_handle(5)); + complex.add_edge_without_blockers(Vertex_handle(4), Vertex_handle(5)); + sigma1 = Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + sigma2 = Simplex(Vertex_handle(2), Vertex_handle(3), Vertex_handle(4)); + + complex.add_blocker(sigma1); + complex.add_blocker(sigma2); + std::cout << "complex complex" << complex.to_string(); + std::cout << std::endl << std::endl; + std::cout << "complex.RemovePopableBlockers();" << std::endl; + complex.remove_popable_blockers(); + std::cout << "complex complex" << complex.to_string(); + + std::cout << std::endl << std::endl; + BOOST_CHECK(complex.num_blockers() == 0); +} |