immediate_dominators#

immediate_dominators(G, start)[source]#

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

Parameters:

Ga DiGraph or MultiDiGraph: The graph where dominance is to be computed.
startnode: The start node of dominance computation.

Returns:

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