Skip to main content
`Ctrl`+`K`

# immediate_dominators

immediate_dominators(G, start)

  Returns the immediate dominators of all nodes of a directed graph.

  Parameters:
    G a DiGraph or MultiDiGraph

      The graph where dominance is to be computed.

    start node

      The start node of dominance computation.

  Returns:
    idom dict keyed by nodes

      A dict containing the immediate dominators of each node reachable from `start`.

  Raises:
    NetworkXNotImplemented

      If `G` is undirected.

    NetworkXError

      If `start` is not in `G`.

  Notes

  Except for `start`, the immediate dominators are the parents of their corresponding nodes in the dominator tree.

  References

  [1]

  Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken. “A simple, fast dominance algorithm.” (2006). https://hdl.handle.net/1911/96345

  Examples

      >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
      >>> sorted(nx.immediate_dominators(G, 1).items())
      [(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)]