Functions | |
template<class FilteredEdgeRange > | |
auto | Gudhi::collapse::flag_complex_collapse_edges (const FilteredEdgeRange &edges) |
Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent homology and returns the remaining edges as a range. More... | |
This module implements edge collapse of a filtered flag complex, in particular it reduces a filtration of Vietoris-Rips complex from its graph to another smaller flag filtration with same persistence. Where a filtration is a sequence of simplicial (here Rips) complexes connected with inclusions.
An edge \(e\) in a simplicial complex \(K\) is called a dominated edge if the link of \(e\) in \(K\), \(lk_K(e)\) is a simplicial cone, that is, there exists a vertex \(v^{\prime} \notin e\) and a subcomplex \(L\) in \(K\), such that \(lk_K(e) = v^{\prime}L\). We say that the vertex \(v^{\prime}\) is {dominating} \(e\) and \(e\) is {dominated} by \(v^{\prime}\). An elementary egde collapse is the removal of a dominated edge \(e\) from \(K\), which we denote with \(K\) \({\searrow\searrow}^1 \) \(K\setminus e\). The symbol \(\mathbf{K\setminus e}\) (deletion of \(e\) from \(K\)) refers to the subcomplex of \(K\) which has all simplices of \(K\) except \(e\) and the ones containing \(e\). There is an edge collapse from a simplicial complex \(K\) to its subcomplex \(L\), if there exists a series of elementary edge collapses from \(K\) to \(L\), denoted as \(K\) \({\searrow\searrow}\) \(L\).
An edge collapse is a homotopy preserving operation, and it can be further expressed as sequence of the classical elementary simple collapse. A complex without any dominated edge is called a \(1\)- minimal complex and the core \(K^1\) of simplicial complex is a minimal complex such that \(K\) \({\searrow\searrow}\) \(K^1\). Computation of a core (not unique) involves computation of dominated edges and the dominated edges can be easily characterized as follows:
– For general simplicial complex: An edge \(e \in K\) is dominated by another vertex \(v^{\prime} \in K\), if and only if all the maximal simplices of \(K\) that contain \(e\) also contain \(v^{\prime}\)
– For a flag complex: An edge \(e \in K\) is dominated by another vertex \(v^{\prime} \in K\), if and only if all the vertices in \(K\) that has an edge with both vertices of \(e\) also has an edge with \(v^{\prime}\).
The algorithm to compute the smaller induced filtration is described in Section 5 [8]. Edge collapse can be successfully employed to reduce any given filtration of flag complexes to a smaller induced filtration which preserves the persistent homology of the original filtration and is a flag complex as well.
The general idea is that we consider edges in the filtered graph and sort them according to their filtration value giving them a total order. Each edge gets a unique index denoted as \(i\) in this order. To reduce the filtration, we move forward with increasing filtration value in the graph and check if the current edge \(e_i\) is dominated in the current graph \(G_i := \{e_1, .. e_i\} \) or not. If the edge \(e_i\) is dominated we remove it from the filtration and move forward to the next edge \(e_{i+1}\). If \(e_i\) is non-dominated then we keep it in the reduced filtration and then go backward in the current graph \(G_i\) to look for new non-dominated edges that was dominated before but might become non-dominated at this point. If an edge \(e_j, j < i \) during the backward search is found to be non-dominated, we include \(e_j\) in to the reduced filtration and we set its new filtration value to be \(i\) that is the index of \(e_i\). The precise mechanism for this reduction has been described in Section 5 [8]. Here we implement this mechanism for a filtration of Rips complex. After perfoming the reduction the filtration reduces to a flag-filtration with the same persistence as the original filtration.
This example calls Gudhi::collapse::flag_complex_collapse_edges()
from a proximity graph represented as a list of Filtered_edge
. Then it collapses edges and displays a new list of Filtered_edge
(with less edges) that will preserve the persistence homology computation.
When launching the example:
the program output is:
auto Gudhi::collapse::flag_complex_collapse_edges | ( | const FilteredEdgeRange & | edges | ) |
Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent homology and returns the remaining edges as a range.
[in] | edges | Range of Filtered edges.There is no need the range to be sorted, as it will be performed. |
FilteredEdgeRange | furnishes std::begin and std::end methods and returns an iterator on a FilteredEdge of type std::tuple<Vertex_handle, Vertex_handle, Filtration_value> where Vertex_handle is the type of a vertex index and Filtration_value is the type of an edge filtration value. |
std::tuple<Vertex_handle, Vertex_handle, Filtration_value>
. GUDHI Version 3.4.1 - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding. - Copyright : MIT | Generated on Fri Jan 22 2021 09:41:16 for GUDHI by Doxygen 1.8.13 |