This documents the development version of NetworkX. Documentation for the current release can be found here.
Returns the immediate dominators of all nodes of a directed graph.
- Ga DiGraph or MultiDiGraph
The graph where dominance is to be computed.
The start node of dominance computation.
- idomdict keyed by nodes
A dict containing the immediate dominators of each node reachable from
startis not in
start, the immediate dominators are the parents of their corresponding nodes in the dominator tree.
K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.
>>> 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)]