networkx.algorithms.dominance.immediate_dominators¶
-
immediate_dominators
(G, start)[source]¶ Returns the immediate dominators of all nodes of a directed graph.
Parameters: - G (a DiGraph or MultiDiGraph) – The graph where dominance is to be computed.
- start (node) – The start node of dominance computation.
Returns: idom – A dict containing the immediate dominators of each node reachable from
start
.Return type: dict keyed by nodes
Raises: NetworkXNotImplemented
– IfG
is undirected.NetworkXError
– Ifstart
is not inG
.
Notes
Except for
start
, the immediate dominators are the parents of their corresponding nodes in the dominator tree.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)]
References
[1] K. D. Cooper, T. J. Harvey, and K. Kennedy. A simple, fast dominance algorithm. Software Practice & Experience, 4:110, 2001.