Warning

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

networkx.algorithms.dag.transitive_closure

transitive_closure(G, reflexive=False)

Returns transitive closure of a directed graph

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 path from v to w in G.

Handling of paths from v to v has some flexibility within this definition. A reflexive transitive closure creates a self-loop for the path from v to v of length 0. The usual transitive closure creates a self-loop only if a cycle exists (a path from v to v with length > 0). We also allow an option for no self-loops.

Parameters

• G (NetworkX DiGraph) – A directed graph

• reflexive (Bool or None, optional (default: False)) – Determines when cycles create self-loops in the Transitive Closure. If True, trivial cycles (length 0) create self-loops. The result is a reflexive tranistive closure of G. If False (the default) non-trivial cycles create self-loops. If None, self-loops are not created.

Returns

The transitive closure of G

Return type

NetworkX DiGraph

Raises

NetworkXNotImplemented – If G is not directed

References

1

http://www.ics.uci.edu/~eppstein/PADS/PartialOrder.py

TODO this function applies to all directed graphs and is probably misplaced

here in dag.py