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]

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