From 8d7329f3e5ad843e553c3c5503cecc28ef2eead6 Mon Sep 17 00:00:00 2001 From: Gard Spreemann Date: Thu, 20 Apr 2017 11:10:45 +0200 Subject: GUDHI 2.0.0 as released by upstream in a tarball. --- doc/Witness_complex/COPYRIGHT | 19 + doc/Witness_complex/Witness_complex_doc.h | 105 +- .../Witness_complex_representation.ipe | 280 +++++ .../Witness_complex_representation.png | Bin 48899 -> 21202 bytes doc/Witness_complex/swit.svg | 1303 ++++++++++++++++++++ 5 files changed, 1692 insertions(+), 15 deletions(-) create mode 100644 doc/Witness_complex/COPYRIGHT create mode 100644 doc/Witness_complex/Witness_complex_representation.ipe create mode 100644 doc/Witness_complex/swit.svg (limited to 'doc/Witness_complex') diff --git a/doc/Witness_complex/COPYRIGHT b/doc/Witness_complex/COPYRIGHT new file mode 100644 index 00000000..7d032c87 --- /dev/null +++ b/doc/Witness_complex/COPYRIGHT @@ -0,0 +1,19 @@ +The files of this directory are part of the Gudhi Library. The Gudhi library +(Geometric Understanding in Higher Dimensions) is a generic C++ library for +computational topology. + +Author(s): Siargey Kachanovich + +Copyright (C) 2015 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 . diff --git a/doc/Witness_complex/Witness_complex_doc.h b/doc/Witness_complex/Witness_complex_doc.h index 60dfd27b..171a185f 100644 --- a/doc/Witness_complex/Witness_complex_doc.h +++ b/doc/Witness_complex/Witness_complex_doc.h @@ -8,31 +8,106 @@ \image html "Witness_complex_representation.png" "Witness complex representation" - \section Definitions + \section witnessdefinitions Definitions - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: + Witness complex is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$: \li \f$W\f$ set of **witnesses** and - \li \f$L \subseteq W\f$ set of **landmarks**. + \li \f$L\f$ set of **landmarks**. - The simplices are based on landmarks - and a simplex belongs to the witness complex if and only if it is witnessed, that is: + Even though often the set of landmarks \f$L\f$ is a subset of the set of witnesses \f$ W\f$, it is not a requirement for the current implementation. - \f$ \sigma \subset L \f$ is witnessed if there exists a point \f$w \in W\f$ such that - w is closer to the vertices of \f$ \sigma \f$ than other points in \f$ L \f$ and all of its faces are witnessed as well. - - The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + Landmarks are the vertices of the simplicial complex + and witnesses help to decide on which simplices are inserted via a predicate "is witnessed". - \section Implementation + De Silva and Carlsson in their paper \cite de2004topological differentiate **weak witnessing** and **strong witnessing**: - The principal class of this module is Gudhi::Witness_complex. + - *weak*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l') \f$ + - *strong*: \f$ \sigma \subset L \f$ is witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l') \f$ - In both cases, the constructor for this class takes a {witness}x{closest_landmarks} table, where each row represents a witness and consists of landmarks sorted by distance to this witness. - This table can be constructed by two additional classes Landmark_choice_by_furthest_point and Landmark_choice_by_random_point also included in the module. + where \f$ d(.,.) \f$ is a distance function. - *\image html "bench_Cy8.png" "Running time as function on number of landmarks" width=10cm - *\image html "bench_sphere.png" "Running time as function on number of witnesses for |L|=300" width=10cm + Both definitions can be relaxed by a real value \f$\alpha\f$: + + - *weak*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + - *strong*: \f$ \sigma \subset L \f$ is \f$\alpha\f$-witnessed by \f$ w \in W\f$ if \f$ \forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2 \f$ + + which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and **strong relaxed witness complex** respectively. + + \image html "swit.svg" "Strongly witnessed simplex" + + In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in \cite de2004topological, whereas 0-relaxed strong witness complex consists of just vertices and is not very interesting. + Hence for small relaxation weak version is preferable. + However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute and offers similar results. + + \section witnessimplementation Implementation + The two complexes described above are implemented in the corresponding classes + - Gudhi::witness_complex::Witness_complex + - Gudhi::witness_complex::Euclidean_witness_complex + - Gudhi::witness_complex::Strong_witness_complex + - Gudhi::witness_complex::Euclidean_strong_witness_complex + + The construction of the Euclidean versions of complexes follow the same scheme: + 1. Construct a search tree on landmarks (for that Gudhi::spatial_searching::Kd_tree_search is used internally). + 2. Construct lists of nearest landmarks for each witness (special structure Gudhi::witness_complex::Active_witness is used internally). + 3. Construct the witness complex for nearest landmark lists. + + In the non-Euclidean classes, the lists of nearest landmarks are supposed to be given as input. + + The constructors take on the steps 1 and 2, while the function 'create_complex' executes the step 3. + + \section witnessexample1 Example 1: Constructing weak relaxed witness complex from an off file + + Let's start with a simple example, which reads an off point file and computes a weak witness complex. + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp} + +#include +#include +#include +#include + +#include + +#include +#include + +typedef CGAL::Epick_d K; +typedef typename K::Point_d Point_d; +typedef typename Gudhi::witness_complex::Euclidean_witness_complex Witness_complex; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::vector< Point_d > Point_vector; + +int main(int argc, char * const argv[]) { + std::string file_name = argv[1]; + int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); + double alpha2 = atof(argv[3]); + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_vector point_vector, landmarks; + Gudhi::Points_off_reader off_reader(file_name); + point_vector = Point_vector(off_reader.get_point_cloud()); + + // Choose landmarks + Gudhi::subsampling::pick_n_random_points(point_vector, nbL, std::back_inserter(landmarks)); + + // Compute witness complex + Witness_complex witness_complex(landmarks, + point_vector); + + witness_complex.create_complex(simplex_tree, alpha2, lim_dim); +} + + + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + \section witnessexample2 Example2: Computing persistence using strong relaxed witness complex + + Here is an example of constructing a strong witness complex filtration and computing persistence on it: + + \include Witness_complex/example_strong_witness_persistence.cpp \copyright GNU General Public License v3. diff --git a/doc/Witness_complex/Witness_complex_representation.ipe b/doc/Witness_complex/Witness_complex_representation.ipe new file mode 100644 index 00000000..f9c45d5d --- /dev/null +++ b/doc/Witness_complex/Witness_complex_representation.ipe @@ -0,0 +1,280 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +48.8262 0 0 48.8262 288 672 e + +$\omega$ + +284 720 m +280 624 l +268 648 l +h + + + + +$\sigma$ + + + + + + + + + diff --git a/doc/Witness_complex/Witness_complex_representation.png b/doc/Witness_complex/Witness_complex_representation.png index 1d31a490..16e0504e 100644 Binary files a/doc/Witness_complex/Witness_complex_representation.png and b/doc/Witness_complex/Witness_complex_representation.png differ diff --git a/doc/Witness_complex/swit.svg b/doc/Witness_complex/swit.svg new file mode 100644 index 00000000..6ffb5fff --- /dev/null +++ b/doc/Witness_complex/swit.svg @@ -0,0 +1,1303 @@ + + + + + + + + + + + + + + + + + image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + -- cgit v1.2.3