Module petgraph::algo::tred [−][src]
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 |
| dag_transitive_reduction_closure | Computes the transitive reduction and closure of a DAG. |