Edge collapse

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

Detailed Description

Author
Siddharth Pritam

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.

Edge collapse definition

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.

Basic edge collapse

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.

#include <gudhi/Flag_complex_edge_collapser.h>
#include <iostream>
#include <vector>
#include <tuple>
int main() {
// Type definitions
using Filtration_value = float;
using Vertex_handle = short;
using Filtered_edge = std::tuple<Vertex_handle, Vertex_handle, Filtration_value>;
using Filtered_edge_list = std::vector<Filtered_edge>;
// 1 2
// o---o
// |\ /|
// | x |
// |/ \|
// o---o
// 0 3
Filtered_edge_list graph = {{0, 1, 1.},
{1, 2, 1.},
{2, 3, 1.},
{3, 0, 1.},
{0, 2, 2.},
{1, 3, 2.}};
auto remaining_edges = Gudhi::collapse::flag_complex_collapse_edges(graph);
for (auto filtered_edge_from_collapse : remaining_edges) {
std::cout << "fn[" << std::get<0>(filtered_edge_from_collapse) << ", " << std::get<1>(filtered_edge_from_collapse)
<< "] = " << std::get<2>(filtered_edge_from_collapse) << std::endl;
}
return 0;
}

When launching the example:

$> ./Edge_collapse_example_basic

the program output is:

fn[0, 1] = 1
fn[1, 2] = 1
fn[2, 3] = 1
fn[3, 0] = 1
fn[0, 2] = 2

Function Documentation

◆ flag_complex_collapse_edges()

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.

Parameters
[in]edgesRange of Filtered edges.There is no need the range to be sorted, as it will be performed.
Template Parameters
FilteredEdgeRangefurnishes 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.
Returns
Remaining edges after collapse as a range of std::tuple<Vertex_handle, Vertex_handle, Filtration_value>.
GUDHI  Version 3.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Aug 11 2020 11:09:13 for GUDHI by Doxygen 1.8.13