Skip to main content
`Ctrl`+`K`

# transitive_closure_dag

transitive_closure_dag(G, topo_order=None)

  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:
    G NetworkX 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)])