path: root/src/Rips_complex/doc/Intro_rips_complex.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.
 *
 *    Author(s):       Clément Maria, Pawel Dlotko, Vincent Rouvreau
 *
 *    Copyright (C) 2016 Inria
 *
 *    Modification(s):
 *      - YYYY/MM Author: Description of the modification
 */

#ifndef DOC_RIPS_COMPLEX_INTRO_RIPS_COMPLEX_H_
#define DOC_RIPS_COMPLEX_INTRO_RIPS_COMPLEX_H_

namespace Gudhi {

namespace rips_complex {

/**  \defgroup rips_complex Rips complex
 * 
 * \author    Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse
 * 
 * @{
 * 
 * \section ripsdefinition Rips complex definition
 * 
 * The Vietoris-Rips complex
 * <a target="_blank" href="https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex">(Wikipedia)</a>
 * is an abstract simplicial complex
 * defined on a finite metric space, where each simplex corresponds to a subset
 * of points whose diameter is smaller that some given threshold.
 * Varying the threshold, we can also see the Rips complex as a filtration of
 * the \f$(n-1)-\f$dimensional simplex, where the filtration value of each
 * simplex is the diameter of the corresponding subset of points.
 *
 * This filtered complex is most often used as an approximation of the
 * Čech complex. After rescaling (Rips using the length of the edges and Čech
 * the half-length), they share the same 1-skeleton and are multiplicatively
 * 2-interleaved or better. While it is slightly bigger, it is also much
 * easier to compute.
 *
 * The number of simplices in the full Rips complex is exponential in the
 * number of vertices, it is thus usually restricted, by excluding all the
 * simplices with filtration value larger than some threshold, and keeping only
 * the dim_max-skeleton. It may also be a good idea to start by making the
 * point set sparser, for instance with
 * `Gudhi::subsampling::sparsify_point_set()`, since small clusters of points
 * have a disproportionate cost without affecting the persistence diagram much.
 *
 * In order to build this complex, the algorithm first builds the graph.
 * The filtration value of each edge is computed from a user-given distance
 * function, or directly read from the distance matrix.
 * In a second step, this graph is inserted in a simplicial complex, which then
 * gets expanded to a flag complex.
 * 
 * The input can be given as a range of points and a distance function, or as a
 * distance matrix.
 * 
 * Vertex name correspond to the index of the point in the given range (aka. the point cloud).
 * 
 * \image html "rips_complex_representation.png" "Rips-complex one skeleton graph representation"
 * 
 * On this example, as edges (4,5), (4,6) and (5,6) are in the complex, simplex (4,5,6) is added with the filtration
 * value set with \f$max(filtration(4,5), filtration(4,6), filtration(5,6))\f$.
 * And so on for simplex (0,1,2,3).
 * 
 * If the Rips_complex interfaces are not detailed enough for your need, please refer to
 * <a href="_persistent_cohomology_2rips_persistence_step_by_step_8cpp-example.html">
 * rips_persistence_step_by_step.cpp</a> example, where the constructions of the graph and
 * the Simplex_tree are more detailed.
 *
 * \section sparserips Sparse Rips complex
 *
 * Even truncated in filtration value and dimension, the Rips complex remains
 * quite large. However, it is possible to approximate it by a much smaller
 * filtered simplicial complex (linear size, with constants that depend on
 * &epsilon; and the doubling dimension of the space) that is
 * \f$(1+O(\epsilon))-\f$interleaved with it (in particular, their persistence
 * diagrams are at log-bottleneck distance at most \f$O(\epsilon)\f$).
 *
 * The sparse Rips filtration was introduced by Don Sheehy
 * \cite sheehy13linear. We are using the version described in
 * \cite buchet16efficient (except that we multiply all filtration values
 * by 2, to match the usual Rips complex), for which \cite cavanna15geometric proves a
 * \f$(1,\frac{1}{1-\epsilon})\f$-interleaving, although in practice the
 * error is usually smaller.
 * A more intuitive presentation of the idea is available in
 * \cite cavanna15geometric, and in a video \cite cavanna15visualizing.
 *
 * The interface of `Sparse_rips_complex` is similar to the one for the usual
 * `Rips_complex`, except that one has to specify the approximation factor.
 * There is an option to limit the minimum and maximum filtration values, but
 * they are not recommended: the way the approximation is done means that
 * larger filtration values are much cheaper to handle than low filtration
 * values, so the gain in ignoring the large ones is small, and
 * `Gudhi::subsampling::sparsify_point_set()` is a more efficient way of
 * ignoring small filtration values.
 *
 * Theoretical guarantees are only available for \f$\epsilon<1\f$. The
 * construction accepts larger values of &epsilon;, and the size of the complex
 * keeps decreasing, but there is no guarantee on the quality of the result.
 * Note that while the number of edges decreases when &epsilon; increases, the
 * number of higher-dimensional simplices may not be monotonous when
 * \f$\frac12\leq\epsilon\leq 1\f$.
 *
 * \section ripspointsdistance Point cloud and distance function
 * 
 * \subsection ripspointscloudexample Example from a point cloud and a distance function
 * 
 * This example builds the one skeleton graph from the given points, threshold value, and distance function.
 * Then it creates a `Simplex_tree` with it.
 * 
 * Then, it is asked to display information about the simplicial complex.
 * 
 * \include Rips_complex/example_one_skeleton_rips_from_points.cpp
 * 
 * When launching (Rips maximal distance between 2 points is 12.0, is expanded
 * until dimension 1 - one skeleton graph in other words):
 * 
 * \code $> ./Rips_complex_example_one_skeleton_from_points
 * \endcode
 *
 * the program output is:
 * 
 * \include Rips_complex/one_skeleton_rips_for_doc.txt
 * 
 * \subsection ripsoffexample Example from OFF file
 * 
 * This example builds the Rips_complex from the given points in an OFF file, threshold value, and distance
 * function.
 * Then it creates a `Simplex_tree` with it.
 * 
 * 
 * Then, it is asked to display information about the Rips complex.
 * 
 * \include Rips_complex/example_rips_complex_from_off_file.cpp
 * 
 * When launching:
 * 
 * \code $> ./Rips_complex_example_from_off ../../data/points/alphacomplexdoc.off 12.0 3
 * \endcode
 *
 * the program output is:
 * 
 * \include Rips_complex/full_skeleton_rips_for_doc.txt
 * 
 *
 * \subsection sparseripspointscloudexample Example of a sparse Rips from a point cloud
 * 
 * This example builds the full sparse Rips of a set of 2D Euclidean points, then prints some minimal
 * information about the complex.
 * 
 * \include Rips_complex/example_sparse_rips.cpp
 * 
 * When launching:
 * 
 * \code $> ./Rips_complex_example_sparse
 * \endcode
 *
 * the program output may be (the exact output varies from one run to the next):
 *
 * \code Sparse Rips complex is of dimension 2 - 19 simplices - 7 vertices.
 * \endcode
 * 
 * 
 * 
 * \section ripsdistancematrix Distance matrix
 * 
 * \subsection ripsdistancematrixexample Example from a distance matrix
 * 
 * This example builds the one skeleton graph from the given distance matrix and threshold value.
 * Then it creates a `Simplex_tree` with it.
 * 
 * Then, it is asked to display information about the simplicial complex.
 * 
 * \include Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp
 * 
 * When launching (Rips maximal distance between 2 points is 1.0, is expanded until dimension 1 - one skeleton graph
 * with other words):
 * 
 * \code $> ./Rips_complex_example_one_skeleton_from_distance_matrix
 * \endcode
 *
 * the program output is:
 * 
 * \include Rips_complex/one_skeleton_rips_for_doc.txt
 * 
 * \subsection ripscsvdistanceexample Example from a distance matrix read in a csv file
 * 
 * This example builds the one skeleton graph from the given distance matrix read in a csv file and threshold value.
 * Then it creates a `Simplex_tree` with it.
 * 
 * 
 * Then, it is asked to display information about the Rips complex.
 * 
 * \include Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp
 * 
 * When launching:
 * 
 * \code $> ./Rips_complex_example_from_csv_distance_matrix ../../data/distance_matrix/full_square_distance_matrix.csv 1.0 3
 * \endcode
 *
 * the program output is:
 * 
 * \include Rips_complex/full_skeleton_rips_for_doc.txt
 * 
 * 
 * \section ripscorrelationematrix Correlation matrix
 * 
 * Analogously to the case of distance matrix, Rips complexes can be also constructed based on correlation matrix. 
 * Given a correlation matrix M, comportment-wise 1-M is a distance matrix.
 * This example builds the one skeleton graph from the given corelation matrix and threshold value.
 * Then it creates a `Simplex_tree` with it.
 * 
 * Then, it is asked to display information about the simplicial complex.
 * 
 * \include Rips_complex/example_one_skeleton_rips_from_correlation_matrix.cpp
 * 
 * When launching:
 * 
 * \code $> ./example_one_skeleton_from_correlation_matrix
 * \endcode
 *
 * the program output is:
 * 
 * \include Rips_complex/one_skeleton_rips_from_correlation_matrix_for_doc.txt
 * 
 * All the other constructions discussed for Rips complex for distance matrix can be also performed for Rips complexes
 * construction from correlation matrices.
 * 
 * @warning As persistence diagrams points will be under the diagonal, bottleneck distance and persistence graphical
 * tool will not work properly, this is a known issue.
 *
 */
/** @} */  // end defgroup rips_complex

}  // namespace rips_complex

}  // namespace Gudhi

#endif  // DOC_RIPS_COMPLEX_INTRO_RIPS_COMPLEX_H_