Edge collapse#

gudhi.flag_filtration.edge_collapse.reduce_graph(input_edges, nb_iterations=1)[source]#

Simplify a clique filtration, preserving its persistent homology. The clique filtration is represented as a sparse weighted graph, giving for each edge its 2 vertices and its filtration value, and the output is in the same format. An edge may be represented arbitrarily as (i, j) or (j, i). Listing the same edge twice, or a self-loop, is undefined. The cliques of the graph composed of the edges with filtration value less than some arbitrary value implicitly define a flag complex, so the weighted graph describes a flag filtration. This function outputs another flag filtration which is guaranteed to have the same persistent homology as the input. The algorithm works by collapsing edges, as described in [22]. Note that this simplification is independent of the filtration values of the vertices. The output has the same shape as the input, which is presumed to be (N, N) where all vertices have index less than N, since the simplification does not affect vertices.

Parameters:
  • input_edges (scipy.sparse.coo_matrix) – Input weighted graph.

  • nb_iterations (int) – The number of times we apply the algorithm. Default is 1.

Return type:

scipy.sparse.coo_matrix