From 03275635bf6f01eab4f5df469fef8e6c5eed7ee7 Mon Sep 17 00:00:00 2001 From: salinasd Date: Mon, 15 Dec 2014 11:50:46 +0000 Subject: skbl doc git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@351 636b058d-ea47-450e-bf9e-a15bfbe3eedb --- src/Doxyfile | 2 +- src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h | 156 -- src/Skeleton_blocker/doc/blocker_curve.svg | 2177 ++++++++++++++++++++ src/Skeleton_blocker/doc/blockers_curve.png | Bin 0 -> 38135 bytes src/Skeleton_blocker/doc/ds_representation.png | Bin 0 -> 42558 bytes src/Skeleton_blocker/doc/ds_scheme.svg | 477 +++++ .../include/gudhi/Skeleton_blocker.h | 158 ++ .../include/gudhi/Skeleton_blocker_complex.h | 21 +- src/common/include/gudhi/Off_reader.h | 13 + 9 files changed, 2829 insertions(+), 175 deletions(-) delete mode 100644 src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h create mode 100644 src/Skeleton_blocker/doc/blocker_curve.svg create mode 100644 src/Skeleton_blocker/doc/blockers_curve.png create mode 100644 src/Skeleton_blocker/doc/ds_representation.png create mode 100644 src/Skeleton_blocker/doc/ds_scheme.svg diff --git a/src/Doxyfile b/src/Doxyfile index 3493d7c6..bda1bdc8 100644 --- a/src/Doxyfile +++ b/src/Doxyfile @@ -831,7 +831,7 @@ EXAMPLE_RECURSIVE = NO # that contain images that are to be included in the documentation (see the # \image command). -IMAGE_PATH = doc/ +IMAGE_PATH = Skeleton_blocker/doc/ # The INPUT_FILTER tag can be used to specify a program that doxygen should # invoke to filter for each input file. Doxygen will invoke the filter program diff --git a/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h b/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h deleted file mode 100644 index 5a80bc8d..00000000 --- a/src/Skeleton_blocker/doc/SkeletonBlockerMainPage.h +++ /dev/null @@ -1,156 +0,0 @@ - -/*! \mainpage Skeleton blockers data-structure - -\author David Salinas - -\section Introduction -The Skeleton-blocker data-structure had been introduced in the two papers -\cite skbl_socg2011 \cite skbl_ijcga2012. -It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its -simplices. -Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that -is very small in practice (see next section for a formal definition). -This data-structure handles every classical operations used for simplicial complexes such as - as simplex enumeration or simplex removal but operations that are particularly efficient - are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. - - -\todo{image wont include} - -\section Definitions - -We recall briefly classical definitions of simplicial complexes \cite Munkres. -An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. -Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of -\f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, -when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \sigma\f$. -An abstract simplicial complex is a set of simplices that contains all the faces of its simplices. -The 1-skeleton of a simplicial complex (or its graph) consists of its elements of dimension lower than 2. - - -\image latex "images/ds_representation.eps" "My application" width=10cm - - -To encode, a simplicial complex, one can encodes all its simplices. -In case when this number gets too large, -a lighter and implicit version consists of encoding only its graph plus some elements called missing faces or blockers. -A blocker is a simplex of dimension greater than 1 -that does not belong to the complex but whose all proper faces does. - - -Remark that for a clique complex (i.e. a simplicial complex whose simplices are cliques of its graph), the set of blockers -is empty and the data-structure is then particularly sparse. -One famous example of clique-complex is the Rips complex which is intensively used -in topological data-analysis. -In practice, the set of blockers of a simplicial complex -remains also small when simplifying a Rips complex with edge contractions -but also for most of the simplicial complexes used in topological data-analysis such as Delaunay, Cech or Witness complexes. -For instance, the numbers of blockers is depicted for a random 3 dimensional sphere embedded into \f$R^4\f$ -in figure X. - - -\image latex "images/blockers_curve.eps" "My application" width=10cm - - - - -\section API - -\subsection Overview - -Four classes define a simplicial complex 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$ - -The two last classes are derived classes from the Skeleton_blocker_complex class. The class Skeleton_blocker_link_complex inheritates from a template passed parameter -that may be either Skeleton_blocker_complex or Skeleton_blocker_geometric_complex (a link may store points coordinates or not). - -\todo{include links} - -\subsection 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 -Contraction package). - - - -\section Example - - -\subsection s Iterating through vertices, edges, blockers and simplices - -Iteration through vertices, edges, simplices or blockers is straightforward with c++11 for range loops. -Note that simplex iteration with this implicit data-structure just takes -a few more time compared to iteration via an explicit representation -such as the Simplex Tree. The following example computes the Euler Characteristic -of a simplicial complex. - - \code{.cpp} - typedef Skeleton_blocker_complex 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 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 0 + + + + + + + + + + + + 1000 + + + + + + + + + + + + 2000 + + + + + + + + + + + + 3000 + + + + + + + + + + + + 4000 + + + + + + + + + + + + 5000 + Number of vertices + + + + + + + + + + + + 0 + + + + + + + + + + + + + + + + 20000 + + + + + + + + + + + + + + + + 40000 + + + + + + + + + + + + + + + + 60000 + + + + + + + + + + + + + + + + 80000 + + + + + + + + + + + + + + + + 100000 + + + + + + + + + + + + + + + + 120000 + + + + + + + + + + + + + + + + 140000 + + + + + + + + + + + + 160000 + + + Size + + + + + + + + + + + + + + + + + + + + + + + + + + + + + numsimplices + + + + + + + + + + num blockers + + + + + + + + + + num non popable blockers + + + + size of the graph + + + + + diff --git a/src/Skeleton_blocker/doc/blockers_curve.png b/src/Skeleton_blocker/doc/blockers_curve.png new file mode 100644 index 00000000..58863ece Binary files /dev/null and b/src/Skeleton_blocker/doc/blockers_curve.png differ diff --git a/src/Skeleton_blocker/doc/ds_representation.png b/src/Skeleton_blocker/doc/ds_representation.png new file mode 100644 index 00000000..bb224038 Binary files /dev/null and b/src/Skeleton_blocker/doc/ds_representation.png differ diff --git a/src/Skeleton_blocker/doc/ds_scheme.svg b/src/Skeleton_blocker/doc/ds_scheme.svg new file mode 100644 index 00000000..f13a6213 --- /dev/null +++ b/src/Skeleton_blocker/doc/ds_scheme.svg @@ -0,0 +1,477 @@ + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Simplicial complex + Encoding + Graph + Blockers + + + + diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 48e311cb..3d3910bf 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -34,5 +34,163 @@ #include "gudhi/Utils.h" //xxx + +/** \defgroup skbl Skeleton-blocker Package + +\author David Salinas + +\section Introduction +The Skeleton-blocker data-structure had been introduced in the two papers +[\cite skbl_socg2011,\cite skbl_ijcga2012]. +It proposes a light encoding for simplicial complexes by storing only an *implicit* representation of its +simplices. +Intuitively, it just stores the 1-skeleton of a simplicial complex with a graph and the set of its "missing faces" that +is very small in practice (see next section for a formal definition). +This data-structure handles every classical operations used for simplicial complexes such as + as simplex enumeration or simplex removal but operations that are particularly efficient + are operations that do not require simplex enumeration such as edge iteration, link computation or simplex contraction. + + +\section Definitions + +We recall briefly classical definitions of simplicial complexes [\cite Munkres]. +An abstract simplex is a finite non-empty set and its dimension is its number of elements minus 1. +Whenever \f$\tau \subset \sigma\f$ and \f$\tau \neq \emptyset \f$, \f$ \tau \f$ is called a face of +\f$ \sigma\f$ and \f$ \sigma\f$ is called a coface of \f$ \tau \f$ . Furthermore, +when \f$ \tau \neq \sigma\f$ we say that \f$ \tau\f$ is a proper-face of \f$ \sigma\f$. +An abstract simplicial complex is a set of simplices that contains all the faces of 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 + + +To encode, a simplicial complex, one can encodes all its simplices. +In case when this number gets too large, +a lighter and implicit version consists of encoding only its graph plus some elements called missing faces or blockers. +A blocker is a simplex of dimension greater than 1 +that does not belong to the complex but whose all proper faces does. + + +Remark that for a clique complex (i.e. a simplicial complex whose simplices are cliques of its graph), the set of blockers +is empty and the data-structure is then particularly sparse. +One famous example of clique-complex is the Rips complex which is intensively used +in topological data-analysis. +In practice, the set of blockers of a simplicial complex +remains also small when simplifying a Rips complex with edge contractions +but also for most of the simplicial complexes used in topological data-analysis such as Delaunay, Cech or Witness complexes. +For instance, the numbers of blockers is depicted for a random 3 dimensional sphere embedded into \f$R^4\f$ +in figure X. + + +*\image html "blockers_curve.png" "Number of blockers of random triangulations of 3-spheres" width=10cm + + + + +\section API + +\subsection Overview + +Four classes define a simplicial complex 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$ + +The two last classes are derived classes from the Skeleton_blocker_complex class. The class Skeleton_blocker_link_complex inheritates from a template passed parameter +that may be either Skeleton_blocker_complex or Skeleton_blocker_geometric_complex (a link may store points coordinates or not). + +\todo{include links} + +\subsection 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 +Contraction package). + + + +\section Example + + +\subsection s Iterating through vertices, edges, blockers and simplices + +Iteration through vertices, edges, simplices or blockers is straightforward with c++11 for range loops. +Note that simplex iteration with this implicit data-structure just takes +a few more time compared to iteration via an explicit representation +such as the Simplex Tree. The following example computes the Euler Characteristic +of a simplicial complex. + + \code{.cpp} + typedef Skeleton_blocker_complex 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. - * - * The SkeletonBlockerDS::Root_vertex_handle serves in the case of a subcomplex (see class Skeleton_blocker_sub_complex) - * to access to the address of one vertex in the parent complex. - * - * @todo TODO Simplex_handle are not classic handle - * */ template class Skeleton_blocker_complex @@ -566,7 +551,7 @@ public: } /** - * @brief Adds an edge between vertices a and b + * @brief Adds an edge between vertices a and b and all its cofaces. */ Edge_handle add_edge(Vertex_handle a, Vertex_handle b){ assert(contains_vertex(a) && contains_vertex(b)); @@ -598,7 +583,7 @@ public: } /** - * @brief Removes edge ab from the simplicial complex. + * @brief Removes edge ab from the simplicial complex and all its cofaces. */ virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b){ bool found; @@ -617,7 +602,7 @@ public: /** - * @brief Removes edge from the simplicial complex. + * @brief Removes edge and its cofaces from the simplicial complex. */ void remove_edge(Edge_handle edge){ assert(contains_vertex(first_vertex(edge))); diff --git a/src/common/include/gudhi/Off_reader.h b/src/common/include/gudhi/Off_reader.h index 1c99a90a..e29218d8 100644 --- a/src/common/include/gudhi/Off_reader.h +++ b/src/common/include/gudhi/Off_reader.h @@ -179,6 +179,19 @@ private: }; +template +void read_off(const std::string& name_file_off,OFFVisitor& vis){ + std::ifstream stream(name_file_off); + if(!stream.is_open()) + std::cerr <<"could not open file \n"; + else{ + Off_reader off_reader(stream); + off_reader.read(vis); + } +} + + + } // namespace Gudhi -- cgit v1.2.3