| 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_ |