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

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

## ◆ 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] edges Range of Filtered edges.There is no need the range to be sorted, as it will be performed.
Template Parameters
 FilteredEdgeRange furnishes std::begin and std::end methods and returns an iterator on a FilteredEdge of type std::tuple 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