This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
Returns the immediate dominators of all nodes of a directed graph.
- G (a DiGraph or MultiDiGraph) – The graph where dominance is to be computed.
- start (node) – The start node of dominance computation.
idom – A dict containing the immediate dominators of each node reachable from
dict keyed by nodes
startis not in
start, the immediate dominators are the parents of their corresponding nodes in the dominator tree.
>>> 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)]
 K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.