Debian Codegraph @

src/Collapse/doc/intro_edge_collapse.h

raw
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Siddharth Pritam
4 *
5 * Copyright (C) 2020 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11 #ifndef DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_
12 #define DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_
13
14 namespace Gudhi {
15
16 namespace collapse {
17
18 /** \defgroup edge_collapse Edge collapse
19 *
20 * \author Siddharth Pritam and Marc Glisse
21 *
22 * @{
23 *
24 * This module implements edge collapse of a filtered flag complex as described in \cite edgecollapsearxiv, in
25 * particular it reduces a filtration of Vietoris-Rips complex represented by a graph to a smaller flag filtration with
26 * the same persistent homology.
27 *
28 * \section edge_collapse_definition Edge collapse definition
29 *
30 * An edge \f$e\f$ in a simplicial complex \f$K\f$ is called a <b>dominated edge</b> if the link of \f$e\f$ in
31 * \f$K\f$, \f$lk_K(e)\f$ is a simplicial cone, that is, there exists a vertex \f$v^{\prime} \notin e\f$ and a
32 * subcomplex \f$L\f$ in \f$K\f$, such that \f$lk_K(e) = v^{\prime}L\f$. We say that the vertex \f$v^{\prime}\f$
33 * \e dominates \f$e\f$ and \f$e\f$ is \e dominated by \f$v^{\prime}\f$.
34 * An <b> elementary edge collapse </b> is the removal of a dominated edge \f$e\f$ from \f$K\f$ (the cofaces of \f$e\f$
35 * are implicitly removed as well).
36 * Domination is used as a simple sufficient condition that ensures that this removal is a homotopy preserving
37 * operation.
38 *
39 * The dominated edges can be easily characterized as follows:
40 *
41 * -- For a general simplicial complex: an edge \f$e \in K\f$ is dominated by another vertex \f$v^{\prime} \in K\f$,
42 * if and only if all the maximal simplices of \f$K\f$ that contain \f$e\f$ also contain \f$v^{\prime}\f$.
43 *
44 * -- For a flag complex: an edge \f$e \in K\f$ is dominated by another vertex \f$v^{\prime} \in K\f$, if and only
45 * if all the vertices in \f$K\f$ that have an edge with both vertices of \f$e\f$ also have an edge with
46 * \f$v^{\prime}\f$. Notice that this only depends on the graph.
47 *
48 * In the context of a filtration, an edge collapse may translate into an increase of the filtration value of an edge,
49 * or its removal if it already had the largest filtration value.
50 * The algorithm to compute the smaller induced filtration is described in \cite edgecollapsearxiv.
51 * Edge collapse can be successfully employed to reduce any input filtration of flag complexes to a smaller induced
52 * filtration which preserves the persistent homology of the original filtration and is a flag complex as well.
53 *
54 * The algorithm implemented here does not produce a minimal filtration. Taking its output and applying the algorithm a
55 * second time may further simplify the filtration.
56 *
57 * \subsection edgecollapseexample Basic edge collapse
58 *
59 * This example calls `Gudhi::collapse::flag_complex_collapse_edges()` from a proximity graph represented as a list of
60 * `Filtered_edge`.
61 * Then it collapses edges and displays a new list of `Filtered_edge` (with fewer edges)
62 * that will preserve the persistence homology computation.
63 *
64 * \include edge_collapse_basic_example.cpp
65 *
66 * When launching the example:
67 *
68 * \code $> ./Edge_collapse_example_basic
69 * \endcode
70 *
71 * the program output could be:
72 *
73 * \include edge_collapse_example_basic.txt
74 */
75 /** @} */ // end defgroup strong_collapse
76
77 } // namespace collapse
78
79 } // namespace Gudhi
80
81 #endif // DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_