Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

networkx.algorithms.dag.transitive_reduction

transitive_reduction(G)

Returns transitive reduction of a directed graph

The transitive reduction of G = (V,E) is a graph G- = (V,E-) such that for all v,w in V there is an edge (v,w) in E- if and only if (v,w) is in E and there is no path from v to w in G with length greater than 1.

Parameters

G (NetworkX DiGraph) – A directed acyclic graph (DAG)

Returns

The transitive reduction of G

Return type

NetworkX DiGraph

Raises

NetworkXError – If G is not a directed acyclic graph (DAG) transitive reduction is not uniquely defined and a NetworkXError exception is raised.

References

https://en.wikipedia.org/wiki/Transitive_reduction