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. The filtration value of vertices is irrelevant to this function. More...

Detailed Description

Author

Siddharth Pritam and Marc Glisse

This module implements edge collapse of a filtered flag complex as described in [34], in particular it reduces a filtration of Vietoris-Rips complex represented by a graph to a smaller flag filtration with the same persistent homology.

Edge collapse definition

An edge $e$ in a simplicial complex $K$ is called a dominated edge if the link of $e$ in $K$, $l{k}_K(e)$ is a simplicial cone, that is, there exists a vertex $v^{\prime }\notin e$ and a subcomplex $L$ in $K$, such that $l{k}_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 [34]. 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.

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 fewer 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 could be:

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. The filtration value of vertices is irrelevant to this function.

Parameters

[in]

edges

Range of Filtered edges. There is no need for the range to be sorted, as it will be done internally.

Template Parameters

FilteredEdgeRange

Range of std::tuple<Vertex_handle, Vertex_handle, Filtration_value> where Vertex_handle is the type of a vertex index.

Returns

Remaining edges after collapse as a range of std::tuple<Vertex_handle, Vertex_handle, Filtration_value>.

Note

Advanced: Defining the macro GUDHI_COLLAPSE_USE_DENSE_ARRAY tells gudhi to allocate a square table of size the maximum vertex index. This usually speeds up the computation for dense graphs. However, for sparse graphs, the memory use may be problematic and initializing this large table may be slow.

Examples

distance_matrix_edge_collapse_rips_persistence.cpp, edge_collapse_basic_example.cpp, edge_collapse_conserve_persistence.cpp, and point_cloud_edge_collapse_rips_persistence.cpp.