Module petgraph::algo::tred

source ·
Expand description

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§