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. The filtration value of vertices is irrelevant to this function. More... | |
This module implements edge collapse of a filtered flag complex as described in [32], in particular it reduces a filtration of Vietoris-Rips complex represented by a graph to a smaller flag filtration with the same persistent homology.
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}\) dominates \(e\) and \(e\) is dominated by \(v^{\prime}\). An elementary edge collapse is the removal of a dominated edge \(e\) from \(K\) (the cofaces of \(e\) are implicitly removed as well). Domination is used as a simple sufficient condition that ensures that this removal is a homotopy preserving operation.
The dominated edges can be easily characterized as follows:
– For a 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 have an edge with both vertices of \(e\) also have an edge with \(v^{\prime}\). Notice that this only depends on the graph.
In the context of a filtration, an edge collapse may translate into an increase of the filtration value of an edge, or its removal if it already had the largest filtration value. The algorithm to compute the smaller induced filtration is described in [32]. Edge collapse can be successfully employed to reduce any input 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 algorithm implemented here does not produce a minimal filtration. Taking its output and applying the algorithm a second time may further simplify the 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 fewer edges) that will preserve the persistence homology computation.
When launching the example:
the program output could be:
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. The filtration value of vertices is irrelevant to this function.
[in] | edges | Range of Filtered edges. There is no need for the range to be sorted, as it will be done internally. |
FilteredEdgeRange | Range of std::tuple<Vertex_handle, Vertex_handle, Filtration_value> where Vertex_handle is the type of a vertex index. |
std::tuple<Vertex_handle, Vertex_handle, Filtration_value>
.