/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
* See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
* 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
* (Wikipedia)
* 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
*
* rips_persistence_step_by_step.cpp 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
* ε 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 ε, 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 ε 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 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 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 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 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 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 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 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 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 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 example_one_skeleton_rips_from_correlation_matrix.cpp
*
* When launching:
*
* \code $> ./example_one_skeleton_from_correlation_matrix
* \endcode
*
* the program output is:
*
* \include 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_