immediate_dominators

immediate_dominators(G, start)

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

We can obtain the immediate post-dominators by reversing the graph before calling immediate_dominators.

>>> G = nx.DiGraph([(1, 2), (2, 3), (2, 4), (3, 5), (4, 5), (5, 6)])
>>> nx.immediate_dominators(G.reverse(copy=False), 6)
{5: 6, 4: 5, 3: 5, 2: 5, 1: 2}