Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_dominance.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 import networkx as nx | |
2 import pytest | |
3 | |
4 | |
5 class TestImmediateDominators: | |
6 def test_exceptions(self): | |
7 G = nx.Graph() | |
8 G.add_node(0) | |
9 pytest.raises(nx.NetworkXNotImplemented, nx.immediate_dominators, G, 0) | |
10 G = nx.MultiGraph(G) | |
11 pytest.raises(nx.NetworkXNotImplemented, nx.immediate_dominators, G, 0) | |
12 G = nx.DiGraph([[0, 0]]) | |
13 pytest.raises(nx.NetworkXError, nx.immediate_dominators, G, 1) | |
14 | |
15 def test_singleton(self): | |
16 G = nx.DiGraph() | |
17 G.add_node(0) | |
18 assert nx.immediate_dominators(G, 0) == {0: 0} | |
19 G.add_edge(0, 0) | |
20 assert nx.immediate_dominators(G, 0) == {0: 0} | |
21 | |
22 def test_path(self): | |
23 n = 5 | |
24 G = nx.path_graph(n, create_using=nx.DiGraph()) | |
25 assert nx.immediate_dominators(G, 0) == {i: max(i - 1, 0) for i in range(n)} | |
26 | |
27 def test_cycle(self): | |
28 n = 5 | |
29 G = nx.cycle_graph(n, create_using=nx.DiGraph()) | |
30 assert nx.immediate_dominators(G, 0) == {i: max(i - 1, 0) for i in range(n)} | |
31 | |
32 def test_unreachable(self): | |
33 n = 5 | |
34 assert n > 1 | |
35 G = nx.path_graph(n, create_using=nx.DiGraph()) | |
36 assert nx.immediate_dominators(G, n // 2) == { | |
37 i: max(i - 1, n // 2) for i in range(n // 2, n) | |
38 } | |
39 | |
40 def test_irreducible1(self): | |
41 # Graph taken from Figure 2 of | |
42 # K. D. Cooper, T. J. Harvey, and K. Kennedy. | |
43 # A simple, fast dominance algorithm. | |
44 # Software Practice & Experience, 4:110, 2001. | |
45 edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)] | |
46 G = nx.DiGraph(edges) | |
47 assert nx.immediate_dominators(G, 5) == {i: 5 for i in range(1, 6)} | |
48 | |
49 def test_irreducible2(self): | |
50 # Graph taken from Figure 4 of | |
51 # K. D. Cooper, T. J. Harvey, and K. Kennedy. | |
52 # A simple, fast dominance algorithm. | |
53 # Software Practice & Experience, 4:110, 2001. | |
54 edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1), (6, 4), (6, 5)] | |
55 G = nx.DiGraph(edges) | |
56 result = nx.immediate_dominators(G, 6) | |
57 assert result == {i: 6 for i in range(1, 7)} | |
58 | |
59 def test_domrel_png(self): | |
60 # Graph taken from https://commons.wikipedia.org/wiki/File:Domrel.png | |
61 edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)] | |
62 G = nx.DiGraph(edges) | |
63 result = nx.immediate_dominators(G, 1) | |
64 assert result == {1: 1, 2: 1, 3: 2, 4: 2, 5: 2, 6: 2} | |
65 # Test postdominance. | |
66 result = nx.immediate_dominators(G.reverse(copy=False), 6) | |
67 assert result == {1: 2, 2: 6, 3: 5, 4: 5, 5: 2, 6: 6} | |
68 | |
69 def test_boost_example(self): | |
70 # Graph taken from Figure 1 of | |
71 # http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/lengauer_tarjan_dominator.htm | |
72 edges = [(0, 1), (1, 2), (1, 3), (2, 7), (3, 4), (4, 5), (4, 6), (5, 7), (6, 4)] | |
73 G = nx.DiGraph(edges) | |
74 result = nx.immediate_dominators(G, 0) | |
75 assert result == {0: 0, 1: 0, 2: 1, 3: 1, 4: 3, 5: 4, 6: 4, 7: 1} | |
76 # Test postdominance. | |
77 result = nx.immediate_dominators(G.reverse(copy=False), 7) | |
78 assert result == {0: 1, 1: 7, 2: 7, 3: 4, 4: 5, 5: 7, 6: 4, 7: 7} | |
79 | |
80 | |
81 class TestDominanceFrontiers: | |
82 def test_exceptions(self): | |
83 G = nx.Graph() | |
84 G.add_node(0) | |
85 pytest.raises(nx.NetworkXNotImplemented, nx.dominance_frontiers, G, 0) | |
86 G = nx.MultiGraph(G) | |
87 pytest.raises(nx.NetworkXNotImplemented, nx.dominance_frontiers, G, 0) | |
88 G = nx.DiGraph([[0, 0]]) | |
89 pytest.raises(nx.NetworkXError, nx.dominance_frontiers, G, 1) | |
90 | |
91 def test_singleton(self): | |
92 G = nx.DiGraph() | |
93 G.add_node(0) | |
94 assert nx.dominance_frontiers(G, 0) == {0: set()} | |
95 G.add_edge(0, 0) | |
96 assert nx.dominance_frontiers(G, 0) == {0: set()} | |
97 | |
98 def test_path(self): | |
99 n = 5 | |
100 G = nx.path_graph(n, create_using=nx.DiGraph()) | |
101 assert nx.dominance_frontiers(G, 0) == {i: set() for i in range(n)} | |
102 | |
103 def test_cycle(self): | |
104 n = 5 | |
105 G = nx.cycle_graph(n, create_using=nx.DiGraph()) | |
106 assert nx.dominance_frontiers(G, 0) == {i: set() for i in range(n)} | |
107 | |
108 def test_unreachable(self): | |
109 n = 5 | |
110 assert n > 1 | |
111 G = nx.path_graph(n, create_using=nx.DiGraph()) | |
112 assert nx.dominance_frontiers(G, n // 2) == {i: set() for i in range(n // 2, n)} | |
113 | |
114 def test_irreducible1(self): | |
115 # Graph taken from Figure 2 of | |
116 # K. D. Cooper, T. J. Harvey, and K. Kennedy. | |
117 # A simple, fast dominance algorithm. | |
118 # Software Practice & Experience, 4:110, 2001. | |
119 edges = [(1, 2), (2, 1), (3, 2), (4, 1), (5, 3), (5, 4)] | |
120 G = nx.DiGraph(edges) | |
121 assert {u: df for u, df in nx.dominance_frontiers(G, 5).items()} == { | |
122 1: {2}, | |
123 2: {1}, | |
124 3: {2}, | |
125 4: {1}, | |
126 5: set(), | |
127 } | |
128 | |
129 def test_irreducible2(self): | |
130 # Graph taken from Figure 4 of | |
131 # K. D. Cooper, T. J. Harvey, and K. Kennedy. | |
132 # A simple, fast dominance algorithm. | |
133 # Software Practice & Experience, 4:110, 2001. | |
134 edges = [(1, 2), (2, 1), (2, 3), (3, 2), (4, 2), (4, 3), (5, 1), (6, 4), (6, 5)] | |
135 G = nx.DiGraph(edges) | |
136 assert nx.dominance_frontiers(G, 6) == { | |
137 1: {2}, | |
138 2: {1, 3}, | |
139 3: {2}, | |
140 4: {2, 3}, | |
141 5: {1}, | |
142 6: set(), | |
143 } | |
144 | |
145 def test_domrel_png(self): | |
146 # Graph taken from https://commons.wikipedia.org/wiki/File:Domrel.png | |
147 edges = [(1, 2), (2, 3), (2, 4), (2, 6), (3, 5), (4, 5), (5, 2)] | |
148 G = nx.DiGraph(edges) | |
149 assert nx.dominance_frontiers(G, 1) == { | |
150 1: set(), | |
151 2: {2}, | |
152 3: {5}, | |
153 4: {5}, | |
154 5: {2}, | |
155 6: set(), | |
156 } | |
157 # Test postdominance. | |
158 result = nx.dominance_frontiers(G.reverse(copy=False), 6) | |
159 assert result == {1: set(), 2: {2}, 3: {2}, 4: {2}, 5: {2}, 6: set()} | |
160 | |
161 def test_boost_example(self): | |
162 # Graph taken from Figure 1 of | |
163 # http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/lengauer_tarjan_dominator.htm | |
164 edges = [(0, 1), (1, 2), (1, 3), (2, 7), (3, 4), (4, 5), (4, 6), (5, 7), (6, 4)] | |
165 G = nx.DiGraph(edges) | |
166 assert nx.dominance_frontiers(G, 0) == { | |
167 0: set(), | |
168 1: set(), | |
169 2: {7}, | |
170 3: {7}, | |
171 4: {4, 7}, | |
172 5: {7}, | |
173 6: {4}, | |
174 7: set(), | |
175 } | |
176 # Test postdominance. | |
177 result = nx.dominance_frontiers(G.reverse(copy=False), 7) | |
178 expected = { | |
179 0: set(), | |
180 1: set(), | |
181 2: {1}, | |
182 3: {1}, | |
183 4: {1, 4}, | |
184 5: {1}, | |
185 6: {4}, | |
186 7: set(), | |
187 } | |
188 assert result == expected | |
189 | |
190 def test_discard_issue(self): | |
191 # https://github.com/networkx/networkx/issues/2071 | |
192 g = nx.DiGraph() | |
193 g.add_edges_from( | |
194 [ | |
195 ("b0", "b1"), | |
196 ("b1", "b2"), | |
197 ("b2", "b3"), | |
198 ("b3", "b1"), | |
199 ("b1", "b5"), | |
200 ("b5", "b6"), | |
201 ("b5", "b8"), | |
202 ("b6", "b7"), | |
203 ("b8", "b7"), | |
204 ("b7", "b3"), | |
205 ("b3", "b4"), | |
206 ] | |
207 ) | |
208 df = nx.dominance_frontiers(g, "b0") | |
209 assert df == { | |
210 "b4": set(), | |
211 "b5": {"b3"}, | |
212 "b6": {"b7"}, | |
213 "b7": {"b3"}, | |
214 "b0": set(), | |
215 "b1": {"b1"}, | |
216 "b2": {"b3"}, | |
217 "b3": {"b1"}, | |
218 "b8": {"b7"}, | |
219 } | |
220 | |
221 def test_loop(self): | |
222 g = nx.DiGraph() | |
223 g.add_edges_from([("a", "b"), ("b", "c"), ("b", "a")]) | |
224 df = nx.dominance_frontiers(g, "a") | |
225 assert df == {"a": set(), "b": set(), "c": set()} | |
226 | |
227 def test_missing_immediate_doms(self): | |
228 # see https://github.com/networkx/networkx/issues/2070 | |
229 g = nx.DiGraph() | |
230 edges = [ | |
231 ("entry_1", "b1"), | |
232 ("b1", "b2"), | |
233 ("b2", "b3"), | |
234 ("b3", "exit"), | |
235 ("entry_2", "b3"), | |
236 ] | |
237 | |
238 # entry_1 | |
239 # | | |
240 # b1 | |
241 # | | |
242 # b2 entry_2 | |
243 # | / | |
244 # b3 | |
245 # | | |
246 # exit | |
247 | |
248 g.add_edges_from(edges) | |
249 # formerly raised KeyError on entry_2 when parsing b3 | |
250 # because entry_2 does not have immediate doms (no path) | |
251 nx.dominance_frontiers(g, "entry_1") | |
252 | |
253 def test_loops_larger(self): | |
254 # from | |
255 # http://ecee.colorado.edu/~waite/Darmstadt/motion.html | |
256 g = nx.DiGraph() | |
257 edges = [ | |
258 ("entry", "exit"), | |
259 ("entry", "1"), | |
260 ("1", "2"), | |
261 ("2", "3"), | |
262 ("3", "4"), | |
263 ("4", "5"), | |
264 ("5", "6"), | |
265 ("6", "exit"), | |
266 ("6", "2"), | |
267 ("5", "3"), | |
268 ("4", "4"), | |
269 ] | |
270 | |
271 g.add_edges_from(edges) | |
272 df = nx.dominance_frontiers(g, "entry") | |
273 answer = { | |
274 "entry": set(), | |
275 "1": {"exit"}, | |
276 "2": {"exit", "2"}, | |
277 "3": {"exit", "3", "2"}, | |
278 "4": {"exit", "4", "3", "2"}, | |
279 "5": {"exit", "3", "2"}, | |
280 "6": {"exit", "2"}, | |
281 "exit": set(), | |
282 } | |
283 for n in df: | |
284 assert set(df[n]) == set(answer[n]) |