diff options
Diffstat (limited to 'src/Skeleton_blocker')
11 files changed, 93 insertions, 38 deletions
diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h index 5cd3a22c..c0386590 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h @@ -16,9 +16,11 @@ namespace skbl { -/** \brief Concept that must be passed to - * the template class Skeleton_blockers_complex - * +/** \brief Concept for the template class passed for Skeleton_blocker_complex. + * Most importantly, it contains the nodes for vertices and edges + * (Graph_vertex and Graph_edge) that are stored in the simplicial + * complex. The user can redefine these classes to attach + * additional information to vertices and edges. */ struct SkeletonBlockerDS { diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h index 23edaaef..fad680d0 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerGeometricDS.h @@ -9,10 +9,15 @@ #ifndef GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ #define GUDHI_SKELETONBLOCKERGEOMETRICDS_H_ -/** \brief Concept that must be passed to - * the template class Skeleton_blocker_geometric_complex - * +/** + * \brief Concept for template class of Skeleton_blocker_geometric_complex . + * It must specify a GeometryTrait which contains a Point definition. + * + * Graph_vertex must specify how to access to a point. + * 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 { @@ -35,11 +40,11 @@ struct SkeletonBlockerGeometricDS : public SkeletonBlockerDS /** * @brief Access to the point. */ - Point& point(){ return point_; } + Point& point(); /** * @brief Access to the point. */ - const Point& point() const { return point_; } + const Point& point(); }; /** diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index d05bdc19..eff37a18 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -41,7 +41,7 @@ \section Introduction The Skeleton-Blocker data-structure had been introduced in the two papers -\cite socg_blockers_2011,\cite blockers2012\cite blockers2012. +\cite socg_blockers_2011,\cite blockers2012. It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its simplices. Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that @@ -53,7 +53,8 @@ This data-structure handles all simplicial complexes operations such as \section Definitions -We recall briefly classical definitions of simplicial complexes \cite Munkres-elementsalgtop1984. +We recall briefly classical definitions of simplicial complexes + \cite Munkres-elementsalgtop1984. An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of \f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, @@ -91,22 +92,24 @@ in figure X. \subsection Overview -Four classes define a simplicial complex namely : +Four classes are implemented for simplicial complex in this representation namely : \li Skeleton_blocker_complex : a simplicial complex with basic operations such as vertex/edge/simplex enumeration and construction \li Skeleton_blocker_link_complex : the link of a simplex in a parent complex. It is represented as a sub complex of the parent complex \li Skeleton_blocker_simplifiable_complex : a simplicial complex with simplification operations such as edge contraction or simplex collapse -\li Skeleton_blocker_geometric_complex : a simplicial complex who has access to geometric points in \f$R^d\f$ +\li Skeleton_blocker_geometric_complex : a simplifiable simplicial complex who has access to geometric points in \f$R^d\f$ The two last classes are derived classes from the <Code>Skeleton_blocker_complex</Code> class. The class <Code>Skeleton_blocker_link_complex</Code> inheritates from a template passed parameter that may be either <Code>Skeleton_blocker_complex</Code> or <Code>Skeleton_blocker_geometric_complex</Code> (a link may store points coordinates or not). +Most user will just need to use Skeleton_blocker_geometric_complex. \subsection Visitor The class <Code>Skeleton_blocker_complex</Code> has a visitor that is called when usual operations such as adding an edge or remove a vertex are called. You may want to use this visitor to compute statistics or to update another data-structure (for instance this visitor is heavily used in the -<Code>Contraction</Code> package). +<Code>Contraction</Code> package). + 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 a02dfe29..fd44fba5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -28,6 +28,9 @@ namespace Gudhi { namespace skbl { +/** + *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. + */ template<typename Complex> class Skeleton_blocker_off_visitor_reader{ Complex& complex_; @@ -65,6 +68,9 @@ public: } }; +/** +*@brief Class that allows to load a Skeleton_blocker_complex from an off file. +*/ template<typename Complex> class Skeleton_blocker_off_reader{ public: diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h index bb48cd8e..a24bea25 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h @@ -30,8 +30,12 @@ namespace Gudhi{ namespace skbl{ + /** * @extends SkeletonBlockerGeometricDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerGeometricDS and + * can be passed as a template argument to Skeleton_blocker_geometric_complex */ template<typename GeometryTrait> struct Skeleton_blocker_simple_geometric_traits : public skbl::Skeleton_blocker_simple_traits { @@ -49,6 +53,7 @@ public: template<class ComplexGeometricTraits> friend class Skeleton_blocker_geometric_complex; private: Point point_; + Point& point(){ return point_; } const Point& point() const { return point_; } }; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h index 9d945d46..e17ea9b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -32,11 +32,14 @@ namespace skbl { /** * @extends SkeletonBlockerDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerDS and + * can be passed as a template argument to Skeleton_blocker_complex */ struct Skeleton_blocker_simple_traits{ /** - * @brief global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. - * In gross, vertices are stored in a vector. + * @brief Global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. + * Vertices are stored in a vector. * For the root simplicial complex, the local and global descriptors are the same. * For a subcomplex L and one of its vertices 'v', the local descriptor of 'v' is its position in * the vertex vector of the subcomplex L whereas its global descriptor is the position of 'v' diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index 97cadfc9..9b4253d1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -33,7 +33,7 @@ namespace skbl { /** * @brief Simplicial subcomplex of a complex represented by a skeleton/blockers pair. - * + * @extends Skeleton_blocker_complex * @details Stores a subcomplex of a simplicial complex. * To simplify explanations below, we will suppose that : * - K is the root simplicial complex diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index c0a0a2eb..81ff0231 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -74,19 +74,35 @@ class Skeleton_blocker_complex public: - + /** + * @brief The type of stored vertex node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_vertex Graph_vertex; + + /** + * @brief The type of stored edge node, specified by the template SkeletonBlockerDS + */ typedef typename SkeletonBlockerDS::Graph_edge Graph_edge; typedef typename SkeletonBlockerDS::Root_vertex_handle Root_vertex_handle; + + /** + * @brief The type of an handle to a vertex of the complex. + */ typedef typename SkeletonBlockerDS::Vertex_handle Vertex_handle; typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle; + /** + * @brief A ordered set of integers that represents a simplex. + */ typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; typedef Skeleton_blocker_simplex<Root_vertex_handle> Root_simplex_handle; + /** + * @brief Handle to a blocker of the complex. + */ typedef Simplex_handle* Blocker_handle; @@ -118,12 +134,12 @@ protected: public: /** - * Handle to an edge of the complex. + * @brief Handle to an edge of the complex. */ typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle; - +protected: typedef std::multimap<Vertex_handle,Simplex_handle *> BlockerMap; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::value_type BlockerPair; typedef typename std::multimap<Vertex_handle,Simplex_handle *>::iterator BlockerMapIterator; @@ -166,6 +182,9 @@ public: /** @name Constructors, Destructors */ //@{ + /** + *@brief constructs a simplicial complex with a given number of vertices and a visitor. + */ Skeleton_blocker_complex(int num_vertices_ = 0,Visitor* visitor_=NULL):visitor(visitor_){ clear(); for (int i=0; i<num_vertices_; ++i){ @@ -277,10 +296,9 @@ private: public: /** - * @brief Constructor with a list of simplices + * @brief Constructor with a list of simplices. * @details The list of simplices must be the list - * of simplices of a simplicial complex. - * + * of simplices of a simplicial complex. */ Skeleton_blocker_complex(std::list<Simplex_handle>& simplices,Visitor* visitor_=NULL): num_vertices_(0),num_blockers_(0), @@ -330,6 +348,8 @@ public: } } +/** +*/ Skeleton_blocker_complex& operator=(const Skeleton_blocker_complex& copy){ clear(); visitor = NULL; @@ -370,6 +390,9 @@ public: skeleton.clear(); } +/** +*@brief allows to change the visitor. +*/ void set_visitor(Visitor* other_visitor){ visitor = other_visitor; } @@ -445,11 +468,15 @@ public: if (visitor) visitor->on_remove_vertex(address); } +/** +*/ bool contains_vertex(Vertex_handle u) const{ if (u.vertex<0 || u.vertex>=boost::num_vertices(skeleton)) return false; return (*this)[u].is_active(); } +/** +*/ bool contains_vertex(Root_vertex_handle u) const{ boost::optional<Vertex_handle> address = get_address(u); return address && (*this)[*address].is_active(); @@ -923,8 +950,9 @@ public: * @brief Compute the local vertices of 's' in the current complex * If one of them is not present in the complex then the return value is uninitialized. * - * xxx rename get_address et place un using dans sub_complex + * */ + //xxx rename get_address et place un using dans sub_complex boost::optional<Simplex_handle> get_simplex_address(const Root_simplex_handle& s) const { boost::optional<Simplex_handle> res; @@ -1126,6 +1154,7 @@ private: public: typedef Triangle_around_vertex_iterator<Skeleton_blocker_complex,Superior_link> Superior_triangle_around_vertex_iterator; + typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex,Link> > Complex_triangle_around_vertex_range; /** @@ -1320,6 +1349,7 @@ public: */ //@{ public: + std::string to_string() const{ std::ostringstream stream; stream<<num_vertices()<<" vertices:\n"<<vertices_to_string()<<std::endl; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 968e8be4..1a51e709 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -32,6 +32,7 @@ namespace skbl { * \brief Class that allows simplification operation on a simplicial complex represented * by a skeleton/blockers pair. * \ingroup skbl + * @extends Skeleton_blocker_complex */ template<typename SkeletonBlockerDS> class Skeleton_blocker_simplifiable_complex : public Skeleton_blocker_complex<SkeletonBlockerDS> diff --git a/src/Skeleton_blocker/test/TestSimplifiable.cpp b/src/Skeleton_blocker/test/TestSimplifiable.cpp index 8df4dade..2dafda52 100644 --- a/src/Skeleton_blocker/test/TestSimplifiable.cpp +++ b/src/Skeleton_blocker/test/TestSimplifiable.cpp @@ -74,8 +74,8 @@ bool test_contraction1(){ Complex complex(n); build_complete(n,complex); complex.remove_edge(Vertex_handle(b),Vertex_handle(z)); - complex.add_blocker(Vertex_handle(a),Vertex_handle(x),Vertex_handle(y)); - complex.add_blocker(Vertex_handle(b),Vertex_handle(x),Vertex_handle(y)); + complex.add_blocker(Simplex_handle(Vertex_handle(a),Vertex_handle(x),Vertex_handle(y))); + complex.add_blocker(Simplex_handle(Vertex_handle(b),Vertex_handle(x),Vertex_handle(y))); // Print result cerr << "complex before complex"<< complex.to_string()<<endl; @@ -136,7 +136,7 @@ bool test_link_condition1(){ Complex complex(0); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); // Print result @@ -183,7 +183,7 @@ bool test_collapse2(){ 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(Vertex_handle(1),Vertex_handle(2),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; @@ -206,7 +206,7 @@ bool test_collapse3(){ 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(Vertex_handle(1),Vertex_handle(2),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; diff --git a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp index 1ebb7f6d..f7bf289a 100644 --- a/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp +++ b/src/Skeleton_blocker/test/TestSkeletonBlockerComplex.cpp @@ -224,7 +224,7 @@ bool test_iterator_triangles(){ complex.add_vertex(); complex.add_edge(Vertex_handle(4),Vertex_handle(7)); complex.add_edge(Vertex_handle(3),Vertex_handle(7)); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(6)); + 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):"); @@ -255,7 +255,7 @@ bool test_iterator_simplices(){ complex.add_edge(Vertex_handle(4),Vertex_handle(5)); complex.add_edge(Vertex_handle(3),Vertex_handle(4)); - complex.add_blocker(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); + complex.add_blocker(Simplex_handle(Vertex_handle(2),Vertex_handle(3),Vertex_handle(4),Vertex_handle(5))); bool correct_number_simplices = true; @@ -322,7 +322,7 @@ bool test_iterator_simplices3(){ 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(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + complex.add_blocker(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); unsigned num_simplices = 0 ; @@ -470,7 +470,7 @@ bool test_link2(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(13)); + 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 @@ -508,7 +508,7 @@ bool test_link3(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12)); + 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 @@ -540,7 +540,7 @@ bool test_link4(){ for (int j=i+1;j<15;j++) complex.add_edge(Vertex_handle(i),Vertex_handle(j)); } - complex.add_blocker(Vertex_handle(10),Vertex_handle(11),Vertex_handle(12),Vertex_handle(13)); + 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 @@ -565,7 +565,7 @@ bool test_link5(){ Complex complex(0,new Print_complex_visitor<Vertex_handle>()); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2),Vertex_handle(3)); + 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)); @@ -585,7 +585,7 @@ bool test_link6(){ Complex complex(0,new Print_complex_visitor<Vertex_handle>()); // Build the complexes build_complete(4,complex); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); + 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)); @@ -614,8 +614,8 @@ bool test_link7(){ complex.add_edge(Vertex_handle(i),Vertex_handle(7)); } complex.add_edge(Vertex_handle(6),Vertex_handle(7)); - complex.add_blocker(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2)); - complex.add_blocker(Vertex_handle(3),Vertex_handle(4),Vertex_handle(5)); + 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)); |