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§
- Creates a representation of the same graph respecting topological order for use in
tred::dag_transitive_reduction_closure
. - Computes the transitive reduction and closure of a DAG.