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, except for start itself.

Raises:

NetworkXNotImplemented: If G is undirected.
NetworkXError: If start is not in G.

Notes

The immediate dominators are the parents of their corresponding nodes in the dominator tree. Every node reachable from start has an immediate dominator, except for start itself.

References

[1]

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

[2]

Lengauer, Thomas; Tarjan, Robert Endre (July 1979). “A fast algorithm for finding dominators in a flowgraph”. ACM Transactions on Programming Languages and Systems. 1 (1): 121–141. https://dl.acm.org/doi/10.1145/357062.357071

Examples

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