Module petgraph::algo::tred

Compute the transitive reduction and closure of a directed acyclic graph

Transitive reduction and closure

The transitive closure of a graph G = (V, E) is the graph Gc = (V, Ec) such that (i, j) belongs to Ec if and only if there is a path connecting i to j in G. The transitive reduction of G is the graph Gr = (V, Er) such that Er is minimal wrt. inclusion in E and the transitive closure of Gr is the same as that of G. The transitive reduction is well-defined for acyclic graphs only.

Functions

dag_to_toposorted_adjacency_list

Creates a representation of the same graph respecting topological order for use in tred::dag_transitive_reduction_closure.

dag_transitive_reduction_closure

Computes the transitive reduction and closure of a DAG.