Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Dominance algorithms.
3"""
5from functools import reduce
7import networkx as nx
8from networkx.utils import not_implemented_for
10__all__ = ["immediate_dominators", "dominance_frontiers"]
13@not_implemented_for("undirected")
14@nx._dispatchable
15def immediate_dominators(G, start):
16 """Returns the immediate dominators of all nodes of a directed graph.
18 Parameters
19 ----------
20 G : a DiGraph or MultiDiGraph
21 The graph where dominance is to be computed.
23 start : node
24 The start node of dominance computation.
26 Returns
27 -------
28 idom : dict keyed by nodes
29 A dict containing the immediate dominators of each node reachable from
30 `start`, except for `start` itself.
32 Raises
33 ------
34 NetworkXNotImplemented
35 If `G` is undirected.
37 NetworkXError
38 If `start` is not in `G`.
40 Notes
41 -----
42 The immediate dominators are the parents of their corresponding nodes in
43 the dominator tree. Every node reachable from `start` has an immediate
44 dominator, except for `start` itself.
46 Examples
47 --------
48 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
49 >>> sorted(nx.immediate_dominators(G, 1).items())
50 [(2, 1), (3, 1), (4, 3), (5, 1)]
52 References
53 ----------
54 .. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
55 "A simple, fast dominance algorithm." (2006).
56 https://hdl.handle.net/1911/96345
57 .. [2] Lengauer, Thomas; Tarjan, Robert Endre (July 1979).
58 "A fast algorithm for finding dominators in a flowgraph".
59 ACM Transactions on Programming Languages and Systems. 1 (1): 121--141.
60 https://dl.acm.org/doi/10.1145/357062.357071
61 """
62 if start not in G:
63 raise nx.NetworkXError("start is not in G")
65 idom = {start: None}
67 order = list(nx.dfs_postorder_nodes(G, start))
68 dfn = {u: i for i, u in enumerate(order)}
69 order.pop()
70 order.reverse()
72 def intersect(u, v):
73 while u != v:
74 while dfn[u] < dfn[v]:
75 u = idom[u]
76 while dfn[u] > dfn[v]:
77 v = idom[v]
78 return u
80 changed = True
81 while changed:
82 changed = False
83 for u in order:
84 new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom))
85 if u not in idom or idom[u] != new_idom:
86 idom[u] = new_idom
87 changed = True
89 del idom[start]
90 return idom
93@not_implemented_for("undirected")
94@nx._dispatchable
95def dominance_frontiers(G, start):
96 """Returns the dominance frontiers of all nodes of a directed graph.
98 Parameters
99 ----------
100 G : a DiGraph or MultiDiGraph
101 The graph where dominance is to be computed.
103 start : node
104 The start node of dominance computation.
106 Returns
107 -------
108 df : dict keyed by nodes
109 A dict containing the dominance frontiers of each node reachable from
110 `start` as lists.
112 Raises
113 ------
114 NetworkXNotImplemented
115 If `G` is undirected.
117 NetworkXError
118 If `start` is not in `G`.
120 Examples
121 --------
122 >>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
123 >>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
124 [(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]
126 References
127 ----------
128 .. [1] Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken.
129 "A simple, fast dominance algorithm." (2006).
130 https://hdl.handle.net/1911/96345
131 """
132 idom = nx.immediate_dominators(G, start) | {start: None}
134 df = {u: set() for u in idom}
135 for u in idom:
136 if u == start or len(G.pred[u]) >= 2:
137 for v in G.pred[u]:
138 if v in idom:
139 while v != idom[u]:
140 df[v].add(u)
141 v = idom[v]
142 return df