1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
"""
Dominance algorithms.
"""
from functools import reduce
import networkx as nx
from networkx.utils import not_implemented_for
__all__ = ["immediate_dominators", "dominance_frontiers"]
@not_implemented_for("undirected")
def immediate_dominators(G, start):
"""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 : dict keyed by nodes
A dict containing the immediate dominators of each node reachable from
`start`.
Raises
------
NetworkXNotImplemented
If `G` is undirected.
NetworkXError
If `start` is not in `G`.
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.
"""
if start not in G:
raise nx.NetworkXError("start is not in G")
idom = {start: start}
order = list(nx.dfs_postorder_nodes(G, start))
dfn = {u: i for i, u in enumerate(order)}
order.pop()
order.reverse()
def intersect(u, v):
while u != v:
while dfn[u] < dfn[v]:
u = idom[u]
while dfn[u] > dfn[v]:
v = idom[v]
return u
changed = True
while changed:
changed = False
for u in order:
new_idom = reduce(intersect, (v for v in G.pred[u] if v in idom))
if u not in idom or idom[u] != new_idom:
idom[u] = new_idom
changed = True
return idom
def dominance_frontiers(G, start):
"""Returns the dominance frontiers 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
-------
df : dict keyed by nodes
A dict containing the dominance frontiers of each node reachable from
`start` as lists.
Raises
------
NetworkXNotImplemented
If `G` is undirected.
NetworkXError
If `start` is not in `G`.
Examples
--------
>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted((u, sorted(df)) for u, df in nx.dominance_frontiers(G, 1).items())
[(1, []), (2, [5]), (3, [5]), (4, [5]), (5, [])]
References
----------
.. [1] K. D. Cooper, T. J. Harvey, and K. Kennedy.
A simple, fast dominance algorithm.
Software Practice & Experience, 4:110, 2001.
"""
idom = nx.immediate_dominators(G, start)
df = {u: set() for u in idom}
for u in idom:
if len(G.pred[u]) >= 2:
for v in G.pred[u]:
if v in idom:
while v != idom[u]:
df[v].add(u)
v = idom[v]
return df
|
