transitive_closure_dag#

transitive_closure_dag(G, topo_order=None)[source]#

Returns the transitive closure of a directed acyclic graph.

This function is faster than the function transitive_closure, but fails if the graph has a cycle.

The transitive closure 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 there is a non-null path from v to w in G.

Parameters:

GNetworkX DiGraph: A directed acyclic graph (DAG)
topo_order: list or tuple, optional: A topological order for G (if None, the function will compute one)

Returns:

NetworkX DiGraph: The transitive closure of G

Raises:

NetworkXNotImplemented: If G is not directed
NetworkXUnfeasible: If G has a cycle

Notes

This algorithm is probably simple enough to be well-known but I didn’t find a mention in the literature.

Examples

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> TC = nx.transitive_closure_dag(DG)
>>> TC.edges()
OutEdgeView([(1, 2), (1, 3), (2, 3)])