Module 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.