Warning

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

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:
  • 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.

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.