Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tree/tests/test_branchings.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 pytest | |
2 | |
3 np = pytest.importorskip("numpy") | |
4 | |
5 import networkx as nx | |
6 | |
7 | |
8 from networkx.algorithms.tree import branchings | |
9 from networkx.algorithms.tree import recognition | |
10 | |
11 # | |
12 # Explicitly discussed examples from Edmonds paper. | |
13 # | |
14 | |
15 # Used in Figures A-F. | |
16 # | |
17 # fmt: off | |
18 G_array = np.array([ | |
19 # 0 1 2 3 4 5 6 7 8 | |
20 [0, 0, 12, 0, 12, 0, 0, 0, 0], # 0 | |
21 [4, 0, 0, 0, 0, 13, 0, 0, 0], # 1 | |
22 [0, 17, 0, 21, 0, 12, 0, 0, 0], # 2 | |
23 [5, 0, 0, 0, 17, 0, 18, 0, 0], # 3 | |
24 [0, 0, 0, 0, 0, 0, 0, 12, 0], # 4 | |
25 [0, 0, 0, 0, 0, 0, 14, 0, 12], # 5 | |
26 [0, 0, 21, 0, 0, 0, 0, 0, 15], # 6 | |
27 [0, 0, 0, 19, 0, 0, 15, 0, 0], # 7 | |
28 [0, 0, 0, 0, 0, 0, 0, 18, 0], # 8 | |
29 ], dtype=int) | |
30 # fmt: on | |
31 | |
32 | |
33 def G1(): | |
34 G = nx.from_numpy_array(G_array, create_using=nx.MultiDiGraph) | |
35 return G | |
36 | |
37 | |
38 def G2(): | |
39 # Now we shift all the weights by -10. | |
40 # Should not affect optimal arborescence, but does affect optimal branching. | |
41 Garr = G_array.copy() | |
42 Garr[np.nonzero(Garr)] -= 10 | |
43 G = nx.from_numpy_array(Garr, create_using=nx.MultiDiGraph) | |
44 return G | |
45 | |
46 | |
47 # An optimal branching for G1 that is also a spanning arborescence. So it is | |
48 # also an optimal spanning arborescence. | |
49 # | |
50 optimal_arborescence_1 = [ | |
51 (0, 2, 12), | |
52 (2, 1, 17), | |
53 (2, 3, 21), | |
54 (1, 5, 13), | |
55 (3, 4, 17), | |
56 (3, 6, 18), | |
57 (6, 8, 15), | |
58 (8, 7, 18), | |
59 ] | |
60 | |
61 # For G2, the optimal branching of G1 (with shifted weights) is no longer | |
62 # an optimal branching, but it is still an optimal spanning arborescence | |
63 # (just with shifted weights). An optimal branching for G2 is similar to what | |
64 # appears in figure G (this is greedy_subopt_branching_1a below), but with the | |
65 # edge (3, 0, 5), which is now (3, 0, -5), removed. Thus, the optimal branching | |
66 # is not a spanning arborescence. The code finds optimal_branching_2a. | |
67 # An alternative and equivalent branching is optimal_branching_2b. We would | |
68 # need to modify the code to iterate through all equivalent optimal branchings. | |
69 # | |
70 # These are maximal branchings or arborescences. | |
71 optimal_branching_2a = [ | |
72 (5, 6, 4), | |
73 (6, 2, 11), | |
74 (6, 8, 5), | |
75 (8, 7, 8), | |
76 (2, 1, 7), | |
77 (2, 3, 11), | |
78 (3, 4, 7), | |
79 ] | |
80 optimal_branching_2b = [ | |
81 (8, 7, 8), | |
82 (7, 3, 9), | |
83 (3, 4, 7), | |
84 (3, 6, 8), | |
85 (6, 2, 11), | |
86 (2, 1, 7), | |
87 (1, 5, 3), | |
88 ] | |
89 optimal_arborescence_2 = [ | |
90 (0, 2, 2), | |
91 (2, 1, 7), | |
92 (2, 3, 11), | |
93 (1, 5, 3), | |
94 (3, 4, 7), | |
95 (3, 6, 8), | |
96 (6, 8, 5), | |
97 (8, 7, 8), | |
98 ] | |
99 | |
100 # Two suboptimal maximal branchings on G1 obtained from a greedy algorithm. | |
101 # 1a matches what is shown in Figure G in Edmonds's paper. | |
102 greedy_subopt_branching_1a = [ | |
103 (5, 6, 14), | |
104 (6, 2, 21), | |
105 (6, 8, 15), | |
106 (8, 7, 18), | |
107 (2, 1, 17), | |
108 (2, 3, 21), | |
109 (3, 0, 5), | |
110 (3, 4, 17), | |
111 ] | |
112 greedy_subopt_branching_1b = [ | |
113 (8, 7, 18), | |
114 (7, 6, 15), | |
115 (6, 2, 21), | |
116 (2, 1, 17), | |
117 (2, 3, 21), | |
118 (1, 5, 13), | |
119 (3, 0, 5), | |
120 (3, 4, 17), | |
121 ] | |
122 | |
123 | |
124 def build_branching(edges): | |
125 G = nx.DiGraph() | |
126 for u, v, weight in edges: | |
127 G.add_edge(u, v, weight=weight) | |
128 return G | |
129 | |
130 | |
131 def sorted_edges(G, attr="weight", default=1): | |
132 edges = [(u, v, data.get(attr, default)) for (u, v, data) in G.edges(data=True)] | |
133 edges = sorted(edges, key=lambda x: (x[2], x[1], x[0])) | |
134 return edges | |
135 | |
136 | |
137 def assert_equal_branchings(G1, G2, attr="weight", default=1): | |
138 edges1 = list(G1.edges(data=True)) | |
139 edges2 = list(G2.edges(data=True)) | |
140 assert len(edges1) == len(edges2) | |
141 | |
142 # Grab the weights only. | |
143 e1 = sorted_edges(G1, attr, default) | |
144 e2 = sorted_edges(G2, attr, default) | |
145 | |
146 # If we have an exception, let's see the edges. | |
147 print(e1) | |
148 print(e2) | |
149 print | |
150 | |
151 for a, b in zip(e1, e2): | |
152 assert a[:2] == b[:2] | |
153 np.testing.assert_almost_equal(a[2], b[2]) | |
154 | |
155 | |
156 ################ | |
157 | |
158 | |
159 def test_optimal_branching1(): | |
160 G = build_branching(optimal_arborescence_1) | |
161 assert recognition.is_arborescence(G), True | |
162 assert branchings.branching_weight(G) == 131 | |
163 | |
164 | |
165 def test_optimal_branching2a(): | |
166 G = build_branching(optimal_branching_2a) | |
167 assert recognition.is_arborescence(G), True | |
168 assert branchings.branching_weight(G) == 53 | |
169 | |
170 | |
171 def test_optimal_branching2b(): | |
172 G = build_branching(optimal_branching_2b) | |
173 assert recognition.is_arborescence(G), True | |
174 assert branchings.branching_weight(G) == 53 | |
175 | |
176 | |
177 def test_optimal_arborescence2(): | |
178 G = build_branching(optimal_arborescence_2) | |
179 assert recognition.is_arborescence(G), True | |
180 assert branchings.branching_weight(G) == 51 | |
181 | |
182 | |
183 def test_greedy_suboptimal_branching1a(): | |
184 G = build_branching(greedy_subopt_branching_1a) | |
185 assert recognition.is_arborescence(G), True | |
186 assert branchings.branching_weight(G) == 128 | |
187 | |
188 | |
189 def test_greedy_suboptimal_branching1b(): | |
190 G = build_branching(greedy_subopt_branching_1b) | |
191 assert recognition.is_arborescence(G), True | |
192 assert branchings.branching_weight(G) == 127 | |
193 | |
194 | |
195 def test_greedy_max1(): | |
196 # Standard test. | |
197 # | |
198 G = G1() | |
199 B = branchings.greedy_branching(G) | |
200 # There are only two possible greedy branchings. The sorting is such | |
201 # that it should equal the second suboptimal branching: 1b. | |
202 B_ = build_branching(greedy_subopt_branching_1b) | |
203 assert_equal_branchings(B, B_) | |
204 | |
205 | |
206 def test_greedy_max2(): | |
207 # Different default weight. | |
208 # | |
209 G = G1() | |
210 del G[1][0][0]["weight"] | |
211 B = branchings.greedy_branching(G, default=6) | |
212 # Chosen so that edge (3,0,5) is not selected and (1,0,6) is instead. | |
213 | |
214 edges = [ | |
215 (1, 0, 6), | |
216 (1, 5, 13), | |
217 (7, 6, 15), | |
218 (2, 1, 17), | |
219 (3, 4, 17), | |
220 (8, 7, 18), | |
221 (2, 3, 21), | |
222 (6, 2, 21), | |
223 ] | |
224 B_ = build_branching(edges) | |
225 assert_equal_branchings(B, B_) | |
226 | |
227 | |
228 def test_greedy_max3(): | |
229 # All equal weights. | |
230 # | |
231 G = G1() | |
232 B = branchings.greedy_branching(G, attr=None) | |
233 | |
234 # This is mostly arbitrary...the output was generated by running the algo. | |
235 edges = [ | |
236 (2, 1, 1), | |
237 (3, 0, 1), | |
238 (3, 4, 1), | |
239 (5, 8, 1), | |
240 (6, 2, 1), | |
241 (7, 3, 1), | |
242 (7, 6, 1), | |
243 (8, 7, 1), | |
244 ] | |
245 B_ = build_branching(edges) | |
246 assert_equal_branchings(B, B_, default=1) | |
247 | |
248 | |
249 def test_greedy_min(): | |
250 G = G1() | |
251 B = branchings.greedy_branching(G, kind="min") | |
252 | |
253 edges = [ | |
254 (1, 0, 4), | |
255 (0, 2, 12), | |
256 (0, 4, 12), | |
257 (2, 5, 12), | |
258 (4, 7, 12), | |
259 (5, 8, 12), | |
260 (5, 6, 14), | |
261 (7, 3, 19), | |
262 ] | |
263 B_ = build_branching(edges) | |
264 assert_equal_branchings(B, B_) | |
265 | |
266 | |
267 def test_edmonds1_maxbranch(): | |
268 G = G1() | |
269 x = branchings.maximum_branching(G) | |
270 x_ = build_branching(optimal_arborescence_1) | |
271 assert_equal_branchings(x, x_) | |
272 | |
273 | |
274 def test_edmonds1_maxarbor(): | |
275 G = G1() | |
276 x = branchings.maximum_spanning_arborescence(G) | |
277 x_ = build_branching(optimal_arborescence_1) | |
278 assert_equal_branchings(x, x_) | |
279 | |
280 | |
281 def test_edmonds2_maxbranch(): | |
282 G = G2() | |
283 x = branchings.maximum_branching(G) | |
284 x_ = build_branching(optimal_branching_2a) | |
285 assert_equal_branchings(x, x_) | |
286 | |
287 | |
288 def test_edmonds2_maxarbor(): | |
289 G = G2() | |
290 x = branchings.maximum_spanning_arborescence(G) | |
291 x_ = build_branching(optimal_arborescence_2) | |
292 assert_equal_branchings(x, x_) | |
293 | |
294 | |
295 def test_edmonds2_minarbor(): | |
296 G = G1() | |
297 x = branchings.minimum_spanning_arborescence(G) | |
298 # This was obtained from algorithm. Need to verify it independently. | |
299 # Branch weight is: 96 | |
300 edges = [ | |
301 (3, 0, 5), | |
302 (0, 2, 12), | |
303 (0, 4, 12), | |
304 (2, 5, 12), | |
305 (4, 7, 12), | |
306 (5, 8, 12), | |
307 (5, 6, 14), | |
308 (2, 1, 17), | |
309 ] | |
310 x_ = build_branching(edges) | |
311 assert_equal_branchings(x, x_) | |
312 | |
313 | |
314 def test_edmonds3_minbranch1(): | |
315 G = G1() | |
316 x = branchings.minimum_branching(G) | |
317 edges = [] | |
318 x_ = build_branching(edges) | |
319 assert_equal_branchings(x, x_) | |
320 | |
321 | |
322 def test_edmonds3_minbranch2(): | |
323 G = G1() | |
324 G.add_edge(8, 9, weight=-10) | |
325 x = branchings.minimum_branching(G) | |
326 edges = [(8, 9, -10)] | |
327 x_ = build_branching(edges) | |
328 assert_equal_branchings(x, x_) | |
329 | |
330 | |
331 # Need more tests | |
332 | |
333 | |
334 def test_mst(): | |
335 # Make sure we get the same results for undirected graphs. | |
336 # Example from: https://en.wikipedia.org/wiki/Kruskal's_algorithm | |
337 G = nx.Graph() | |
338 edgelist = [ | |
339 (0, 3, [("weight", 5)]), | |
340 (0, 1, [("weight", 7)]), | |
341 (1, 3, [("weight", 9)]), | |
342 (1, 2, [("weight", 8)]), | |
343 (1, 4, [("weight", 7)]), | |
344 (3, 4, [("weight", 15)]), | |
345 (3, 5, [("weight", 6)]), | |
346 (2, 4, [("weight", 5)]), | |
347 (4, 5, [("weight", 8)]), | |
348 (4, 6, [("weight", 9)]), | |
349 (5, 6, [("weight", 11)]), | |
350 ] | |
351 G.add_edges_from(edgelist) | |
352 G = G.to_directed() | |
353 x = branchings.minimum_spanning_arborescence(G) | |
354 | |
355 edges = [ | |
356 ({0, 1}, 7), | |
357 ({0, 3}, 5), | |
358 ({3, 5}, 6), | |
359 ({1, 4}, 7), | |
360 ({4, 2}, 5), | |
361 ({4, 6}, 9), | |
362 ] | |
363 | |
364 assert x.number_of_edges() == len(edges) | |
365 for u, v, d in x.edges(data=True): | |
366 assert ({u, v}, d["weight"]) in edges | |
367 | |
368 | |
369 def test_mixed_nodetypes(): | |
370 # Smoke test to make sure no TypeError is raised for mixed node types. | |
371 G = nx.Graph() | |
372 edgelist = [(0, 3, [("weight", 5)]), (0, "1", [("weight", 5)])] | |
373 G.add_edges_from(edgelist) | |
374 G = G.to_directed() | |
375 x = branchings.minimum_spanning_arborescence(G) | |
376 | |
377 | |
378 def test_edmonds1_minbranch(): | |
379 # Using -G_array and min should give the same as optimal_arborescence_1, | |
380 # but with all edges negative. | |
381 edges = [(u, v, -w) for (u, v, w) in optimal_arborescence_1] | |
382 | |
383 G = nx.from_numpy_array(-G_array, create_using=nx.DiGraph) | |
384 | |
385 # Quickly make sure max branching is empty. | |
386 x = branchings.maximum_branching(G) | |
387 x_ = build_branching([]) | |
388 assert_equal_branchings(x, x_) | |
389 | |
390 # Now test the min branching. | |
391 x = branchings.minimum_branching(G) | |
392 x_ = build_branching(edges) | |
393 assert_equal_branchings(x, x_) | |
394 | |
395 | |
396 def test_edge_attribute_preservation_normal_graph(): | |
397 # Test that edge attributes are preserved when finding an optimum graph | |
398 # using the Edmonds class for normal graphs. | |
399 G = nx.Graph() | |
400 | |
401 edgelist = [ | |
402 (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]), | |
403 (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]), | |
404 (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]), | |
405 ] | |
406 G.add_edges_from(edgelist) | |
407 | |
408 ed = branchings.Edmonds(G) | |
409 B = ed.find_optimum("weight", preserve_attrs=True, seed=1) | |
410 | |
411 assert B[0][1]["otherattr"] == 1 | |
412 assert B[0][1]["otherattr2"] == 3 | |
413 | |
414 | |
415 def test_edge_attribute_preservation_multigraph(): | |
416 | |
417 # Test that edge attributes are preserved when finding an optimum graph | |
418 # using the Edmonds class for multigraphs. | |
419 G = nx.MultiGraph() | |
420 | |
421 edgelist = [ | |
422 (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]), | |
423 (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]), | |
424 (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]), | |
425 ] | |
426 G.add_edges_from(edgelist * 2) # Make sure we have duplicate edge paths | |
427 | |
428 ed = branchings.Edmonds(G) | |
429 B = ed.find_optimum("weight", preserve_attrs=True) | |
430 | |
431 assert B[0][1][0]["otherattr"] == 1 | |
432 assert B[0][1][0]["otherattr2"] == 3 | |
433 | |
434 | |
435 def test_edge_attribute_discard(): | |
436 # Test that edge attributes are discarded if we do not specify to keep them | |
437 G = nx.Graph() | |
438 | |
439 edgelist = [ | |
440 (0, 1, [("weight", 5), ("otherattr", 1), ("otherattr2", 3)]), | |
441 (0, 2, [("weight", 5), ("otherattr", 2), ("otherattr2", 2)]), | |
442 (1, 2, [("weight", 6), ("otherattr", 3), ("otherattr2", 1)]), | |
443 ] | |
444 G.add_edges_from(edgelist) | |
445 | |
446 ed = branchings.Edmonds(G) | |
447 B = ed.find_optimum("weight", preserve_attrs=False) | |
448 | |
449 edge_dict = B[0][1] | |
450 with pytest.raises(KeyError): | |
451 _ = edge_dict["otherattr"] |