networkx.algorithms.dominance.immediate_dominators

immediate_dominators(G, start)[source]

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 – A dict containing the immediate dominators of each node reachable from start.

Return type

dict keyed by nodes

Raises

Notes

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

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)]

References

1

K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.