Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_matching.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 from itertools import permutations | |
2 import math | |
3 | |
4 import networkx as nx | |
5 from networkx.algorithms.matching import matching_dict_to_set | |
6 from networkx.testing import assert_edges_equal | |
7 | |
8 | |
9 class TestMaxWeightMatching: | |
10 """Unit tests for the | |
11 :func:`~networkx.algorithms.matching.max_weight_matching` function. | |
12 | |
13 """ | |
14 | |
15 def test_trivial1(self): | |
16 """Empty graph""" | |
17 G = nx.Graph() | |
18 assert nx.max_weight_matching(G) == set() | |
19 | |
20 def test_trivial2(self): | |
21 """Self loop""" | |
22 G = nx.Graph() | |
23 G.add_edge(0, 0, weight=100) | |
24 assert nx.max_weight_matching(G) == set() | |
25 | |
26 def test_trivial3(self): | |
27 """Single edge""" | |
28 G = nx.Graph() | |
29 G.add_edge(0, 1) | |
30 assert_edges_equal( | |
31 nx.max_weight_matching(G), matching_dict_to_set({0: 1, 1: 0}) | |
32 ) | |
33 | |
34 def test_trivial4(self): | |
35 """Small graph""" | |
36 G = nx.Graph() | |
37 G.add_edge("one", "two", weight=10) | |
38 G.add_edge("two", "three", weight=11) | |
39 assert_edges_equal( | |
40 nx.max_weight_matching(G), | |
41 matching_dict_to_set({"three": "two", "two": "three"}), | |
42 ) | |
43 | |
44 def test_trivial5(self): | |
45 """Path""" | |
46 G = nx.Graph() | |
47 G.add_edge(1, 2, weight=5) | |
48 G.add_edge(2, 3, weight=11) | |
49 G.add_edge(3, 4, weight=5) | |
50 assert_edges_equal( | |
51 nx.max_weight_matching(G), matching_dict_to_set({2: 3, 3: 2}) | |
52 ) | |
53 assert_edges_equal( | |
54 nx.max_weight_matching(G, 1), matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3}) | |
55 ) | |
56 | |
57 def test_trivial6(self): | |
58 """Small graph with arbitrary weight attribute""" | |
59 G = nx.Graph() | |
60 G.add_edge("one", "two", weight=10, abcd=11) | |
61 G.add_edge("two", "three", weight=11, abcd=10) | |
62 assert_edges_equal( | |
63 nx.max_weight_matching(G, weight="abcd"), | |
64 matching_dict_to_set({"one": "two", "two": "one"}), | |
65 ) | |
66 | |
67 def test_floating_point_weights(self): | |
68 """Floating point weights""" | |
69 G = nx.Graph() | |
70 G.add_edge(1, 2, weight=math.pi) | |
71 G.add_edge(2, 3, weight=math.exp(1)) | |
72 G.add_edge(1, 3, weight=3.0) | |
73 G.add_edge(1, 4, weight=math.sqrt(2.0)) | |
74 assert_edges_equal( | |
75 nx.max_weight_matching(G), matching_dict_to_set({1: 4, 2: 3, 3: 2, 4: 1}) | |
76 ) | |
77 | |
78 def test_negative_weights(self): | |
79 """Negative weights""" | |
80 G = nx.Graph() | |
81 G.add_edge(1, 2, weight=2) | |
82 G.add_edge(1, 3, weight=-2) | |
83 G.add_edge(2, 3, weight=1) | |
84 G.add_edge(2, 4, weight=-1) | |
85 G.add_edge(3, 4, weight=-6) | |
86 assert_edges_equal( | |
87 nx.max_weight_matching(G), matching_dict_to_set({1: 2, 2: 1}) | |
88 ) | |
89 assert_edges_equal( | |
90 nx.max_weight_matching(G, 1), matching_dict_to_set({1: 3, 2: 4, 3: 1, 4: 2}) | |
91 ) | |
92 | |
93 def test_s_blossom(self): | |
94 """Create S-blossom and use it for augmentation:""" | |
95 G = nx.Graph() | |
96 G.add_weighted_edges_from([(1, 2, 8), (1, 3, 9), (2, 3, 10), (3, 4, 7)]) | |
97 assert_edges_equal( | |
98 nx.max_weight_matching(G), matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3}) | |
99 ) | |
100 | |
101 G.add_weighted_edges_from([(1, 6, 5), (4, 5, 6)]) | |
102 assert_edges_equal( | |
103 nx.max_weight_matching(G), | |
104 matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}), | |
105 ) | |
106 | |
107 def test_s_t_blossom(self): | |
108 """Create S-blossom, relabel as T-blossom, use for augmentation:""" | |
109 G = nx.Graph() | |
110 G.add_weighted_edges_from( | |
111 [(1, 2, 9), (1, 3, 8), (2, 3, 10), (1, 4, 5), (4, 5, 4), (1, 6, 3)] | |
112 ) | |
113 assert_edges_equal( | |
114 nx.max_weight_matching(G), | |
115 matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}), | |
116 ) | |
117 G.add_edge(4, 5, weight=3) | |
118 G.add_edge(1, 6, weight=4) | |
119 assert_edges_equal( | |
120 nx.max_weight_matching(G), | |
121 matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 5, 5: 4, 6: 1}), | |
122 ) | |
123 G.remove_edge(1, 6) | |
124 G.add_edge(3, 6, weight=4) | |
125 assert_edges_equal( | |
126 nx.max_weight_matching(G), | |
127 matching_dict_to_set({1: 2, 2: 1, 3: 6, 4: 5, 5: 4, 6: 3}), | |
128 ) | |
129 | |
130 def test_nested_s_blossom(self): | |
131 """Create nested S-blossom, use for augmentation:""" | |
132 | |
133 G = nx.Graph() | |
134 G.add_weighted_edges_from( | |
135 [ | |
136 (1, 2, 9), | |
137 (1, 3, 9), | |
138 (2, 3, 10), | |
139 (2, 4, 8), | |
140 (3, 5, 8), | |
141 (4, 5, 10), | |
142 (5, 6, 6), | |
143 ] | |
144 ) | |
145 dict_format = {1: 3, 2: 4, 3: 1, 4: 2, 5: 6, 6: 5} | |
146 expected = {frozenset(e) for e in matching_dict_to_set(dict_format)} | |
147 answer = {frozenset(e) for e in nx.max_weight_matching(G)} | |
148 assert answer == expected | |
149 | |
150 def test_nested_s_blossom_relabel(self): | |
151 """Create S-blossom, relabel as S, include in nested S-blossom:""" | |
152 G = nx.Graph() | |
153 G.add_weighted_edges_from( | |
154 [ | |
155 (1, 2, 10), | |
156 (1, 7, 10), | |
157 (2, 3, 12), | |
158 (3, 4, 20), | |
159 (3, 5, 20), | |
160 (4, 5, 25), | |
161 (5, 6, 10), | |
162 (6, 7, 10), | |
163 (7, 8, 8), | |
164 ] | |
165 ) | |
166 assert_edges_equal( | |
167 nx.max_weight_matching(G), | |
168 matching_dict_to_set({1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5, 7: 8, 8: 7}), | |
169 ) | |
170 | |
171 def test_nested_s_blossom_expand(self): | |
172 """Create nested S-blossom, augment, expand recursively:""" | |
173 G = nx.Graph() | |
174 G.add_weighted_edges_from( | |
175 [ | |
176 (1, 2, 8), | |
177 (1, 3, 8), | |
178 (2, 3, 10), | |
179 (2, 4, 12), | |
180 (3, 5, 12), | |
181 (4, 5, 14), | |
182 (4, 6, 12), | |
183 (5, 7, 12), | |
184 (6, 7, 14), | |
185 (7, 8, 12), | |
186 ] | |
187 ) | |
188 assert_edges_equal( | |
189 nx.max_weight_matching(G), | |
190 matching_dict_to_set({1: 2, 2: 1, 3: 5, 4: 6, 5: 3, 6: 4, 7: 8, 8: 7}), | |
191 ) | |
192 | |
193 def test_s_blossom_relabel_expand(self): | |
194 """Create S-blossom, relabel as T, expand:""" | |
195 G = nx.Graph() | |
196 G.add_weighted_edges_from( | |
197 [ | |
198 (1, 2, 23), | |
199 (1, 5, 22), | |
200 (1, 6, 15), | |
201 (2, 3, 25), | |
202 (3, 4, 22), | |
203 (4, 5, 25), | |
204 (4, 8, 14), | |
205 (5, 7, 13), | |
206 ] | |
207 ) | |
208 assert_edges_equal( | |
209 nx.max_weight_matching(G), | |
210 matching_dict_to_set({1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4}), | |
211 ) | |
212 | |
213 def test_nested_s_blossom_relabel_expand(self): | |
214 """Create nested S-blossom, relabel as T, expand:""" | |
215 G = nx.Graph() | |
216 G.add_weighted_edges_from( | |
217 [ | |
218 (1, 2, 19), | |
219 (1, 3, 20), | |
220 (1, 8, 8), | |
221 (2, 3, 25), | |
222 (2, 4, 18), | |
223 (3, 5, 18), | |
224 (4, 5, 13), | |
225 (4, 7, 7), | |
226 (5, 6, 7), | |
227 ] | |
228 ) | |
229 assert_edges_equal( | |
230 nx.max_weight_matching(G), | |
231 matching_dict_to_set({1: 8, 2: 3, 3: 2, 4: 7, 5: 6, 6: 5, 7: 4, 8: 1}), | |
232 ) | |
233 | |
234 def test_nasty_blossom1(self): | |
235 """Create blossom, relabel as T in more than one way, expand, | |
236 augment: | |
237 """ | |
238 G = nx.Graph() | |
239 G.add_weighted_edges_from( | |
240 [ | |
241 (1, 2, 45), | |
242 (1, 5, 45), | |
243 (2, 3, 50), | |
244 (3, 4, 45), | |
245 (4, 5, 50), | |
246 (1, 6, 30), | |
247 (3, 9, 35), | |
248 (4, 8, 35), | |
249 (5, 7, 26), | |
250 (9, 10, 5), | |
251 ] | |
252 ) | |
253 assert_edges_equal( | |
254 nx.max_weight_matching(G), | |
255 matching_dict_to_set( | |
256 {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9} | |
257 ), | |
258 ) | |
259 | |
260 def test_nasty_blossom2(self): | |
261 """Again but slightly different:""" | |
262 G = nx.Graph() | |
263 G.add_weighted_edges_from( | |
264 [ | |
265 (1, 2, 45), | |
266 (1, 5, 45), | |
267 (2, 3, 50), | |
268 (3, 4, 45), | |
269 (4, 5, 50), | |
270 (1, 6, 30), | |
271 (3, 9, 35), | |
272 (4, 8, 26), | |
273 (5, 7, 40), | |
274 (9, 10, 5), | |
275 ] | |
276 ) | |
277 assert_edges_equal( | |
278 nx.max_weight_matching(G), | |
279 matching_dict_to_set( | |
280 {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9} | |
281 ), | |
282 ) | |
283 | |
284 def test_nasty_blossom_least_slack(self): | |
285 """Create blossom, relabel as T, expand such that a new | |
286 least-slack S-to-free dge is produced, augment: | |
287 """ | |
288 G = nx.Graph() | |
289 G.add_weighted_edges_from( | |
290 [ | |
291 (1, 2, 45), | |
292 (1, 5, 45), | |
293 (2, 3, 50), | |
294 (3, 4, 45), | |
295 (4, 5, 50), | |
296 (1, 6, 30), | |
297 (3, 9, 35), | |
298 (4, 8, 28), | |
299 (5, 7, 26), | |
300 (9, 10, 5), | |
301 ] | |
302 ) | |
303 assert_edges_equal( | |
304 nx.max_weight_matching(G), | |
305 matching_dict_to_set( | |
306 {1: 6, 2: 3, 3: 2, 4: 8, 5: 7, 6: 1, 7: 5, 8: 4, 9: 10, 10: 9} | |
307 ), | |
308 ) | |
309 | |
310 def test_nasty_blossom_augmenting(self): | |
311 """Create nested blossom, relabel as T in more than one way""" | |
312 # expand outer blossom such that inner blossom ends up on an | |
313 # augmenting path: | |
314 G = nx.Graph() | |
315 G.add_weighted_edges_from( | |
316 [ | |
317 (1, 2, 45), | |
318 (1, 7, 45), | |
319 (2, 3, 50), | |
320 (3, 4, 45), | |
321 (4, 5, 95), | |
322 (4, 6, 94), | |
323 (5, 6, 94), | |
324 (6, 7, 50), | |
325 (1, 8, 30), | |
326 (3, 11, 35), | |
327 (5, 9, 36), | |
328 (7, 10, 26), | |
329 (11, 12, 5), | |
330 ] | |
331 ) | |
332 assert_edges_equal( | |
333 nx.max_weight_matching(G), | |
334 matching_dict_to_set( | |
335 { | |
336 1: 8, | |
337 2: 3, | |
338 3: 2, | |
339 4: 6, | |
340 5: 9, | |
341 6: 4, | |
342 7: 10, | |
343 8: 1, | |
344 9: 5, | |
345 10: 7, | |
346 11: 12, | |
347 12: 11, | |
348 } | |
349 ), | |
350 ) | |
351 | |
352 def test_nasty_blossom_expand_recursively(self): | |
353 """Create nested S-blossom, relabel as S, expand recursively:""" | |
354 G = nx.Graph() | |
355 G.add_weighted_edges_from( | |
356 [ | |
357 (1, 2, 40), | |
358 (1, 3, 40), | |
359 (2, 3, 60), | |
360 (2, 4, 55), | |
361 (3, 5, 55), | |
362 (4, 5, 50), | |
363 (1, 8, 15), | |
364 (5, 7, 30), | |
365 (7, 6, 10), | |
366 (8, 10, 10), | |
367 (4, 9, 30), | |
368 ] | |
369 ) | |
370 assert_edges_equal( | |
371 nx.max_weight_matching(G), | |
372 matching_dict_to_set( | |
373 {1: 2, 2: 1, 3: 5, 4: 9, 5: 3, 6: 7, 7: 6, 8: 10, 9: 4, 10: 8} | |
374 ), | |
375 ) | |
376 | |
377 | |
378 class TestIsMatching: | |
379 """Unit tests for the | |
380 :func:`~networkx.algorithms.matching.is_matching` function. | |
381 | |
382 """ | |
383 | |
384 def test_dict(self): | |
385 G = nx.path_graph(4) | |
386 assert nx.is_matching(G, {0: 1, 1: 0, 2: 3, 3: 2}) | |
387 | |
388 def test_empty_matching(self): | |
389 G = nx.path_graph(4) | |
390 assert nx.is_matching(G, set()) | |
391 | |
392 def test_single_edge(self): | |
393 G = nx.path_graph(4) | |
394 assert nx.is_matching(G, {(1, 2)}) | |
395 | |
396 def test_edge_order(self): | |
397 G = nx.path_graph(4) | |
398 assert nx.is_matching(G, {(0, 1), (2, 3)}) | |
399 assert nx.is_matching(G, {(1, 0), (2, 3)}) | |
400 assert nx.is_matching(G, {(0, 1), (3, 2)}) | |
401 assert nx.is_matching(G, {(1, 0), (3, 2)}) | |
402 | |
403 def test_valid(self): | |
404 G = nx.path_graph(4) | |
405 assert nx.is_matching(G, {(0, 1), (2, 3)}) | |
406 | |
407 def test_invalid(self): | |
408 G = nx.path_graph(4) | |
409 assert not nx.is_matching(G, {(0, 1), (1, 2), (2, 3)}) | |
410 | |
411 | |
412 class TestIsMaximalMatching: | |
413 """Unit tests for the | |
414 :func:`~networkx.algorithms.matching.is_maximal_matching` function. | |
415 | |
416 """ | |
417 | |
418 def test_dict(self): | |
419 G = nx.path_graph(4) | |
420 assert nx.is_maximal_matching(G, {0: 1, 1: 0, 2: 3, 3: 2}) | |
421 | |
422 def test_valid(self): | |
423 G = nx.path_graph(4) | |
424 assert nx.is_maximal_matching(G, {(0, 1), (2, 3)}) | |
425 | |
426 def test_not_matching(self): | |
427 G = nx.path_graph(4) | |
428 assert not nx.is_maximal_matching(G, {(0, 1), (1, 2), (2, 3)}) | |
429 | |
430 def test_not_maximal(self): | |
431 G = nx.path_graph(4) | |
432 assert not nx.is_maximal_matching(G, {(0, 1)}) | |
433 | |
434 | |
435 class TestIsPerfectMatching: | |
436 """Unit tests for the | |
437 :func:`~networkx.algorithms.matching.is_perfect_matching` function. | |
438 | |
439 """ | |
440 | |
441 def test_dict(self): | |
442 G = nx.path_graph(4) | |
443 assert nx.is_perfect_matching(G, {0: 1, 1: 0, 2: 3, 3: 2}) | |
444 | |
445 def test_valid(self): | |
446 G = nx.path_graph(4) | |
447 assert nx.is_perfect_matching(G, {(0, 1), (2, 3)}) | |
448 | |
449 def test_valid_not_path(self): | |
450 G = nx.cycle_graph(4) | |
451 G.add_edge(0, 4) | |
452 G.add_edge(1, 4) | |
453 G.add_edge(5, 2) | |
454 | |
455 assert nx.is_perfect_matching(G, {(1, 4), (0, 3), (5, 2)}) | |
456 | |
457 def test_not_matching(self): | |
458 G = nx.path_graph(4) | |
459 assert not nx.is_perfect_matching(G, {(0, 1), (1, 2), (2, 3)}) | |
460 | |
461 def test_maximal_but_not_perfect(self): | |
462 G = nx.cycle_graph(4) | |
463 G.add_edge(0, 4) | |
464 G.add_edge(1, 4) | |
465 | |
466 assert not nx.is_perfect_matching(G, {(1, 4), (0, 3)}) | |
467 | |
468 | |
469 class TestMaximalMatching: | |
470 """Unit tests for the | |
471 :func:`~networkx.algorithms.matching.maximal_matching`. | |
472 | |
473 """ | |
474 | |
475 def test_valid_matching(self): | |
476 edges = [(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (3, 6), (5, 6)] | |
477 G = nx.Graph(edges) | |
478 matching = nx.maximal_matching(G) | |
479 assert nx.is_maximal_matching(G, matching) | |
480 | |
481 def test_single_edge_matching(self): | |
482 # In the star graph, any maximal matching has just one edge. | |
483 G = nx.star_graph(5) | |
484 matching = nx.maximal_matching(G) | |
485 assert 1 == len(matching) | |
486 assert nx.is_maximal_matching(G, matching) | |
487 | |
488 def test_self_loops(self): | |
489 # Create the path graph with two self-loops. | |
490 G = nx.path_graph(3) | |
491 G.add_edges_from([(0, 0), (1, 1)]) | |
492 matching = nx.maximal_matching(G) | |
493 assert len(matching) == 1 | |
494 # The matching should never include self-loops. | |
495 assert not any(u == v for u, v in matching) | |
496 assert nx.is_maximal_matching(G, matching) | |
497 | |
498 def test_ordering(self): | |
499 """Tests that a maximal matching is computed correctly | |
500 regardless of the order in which nodes are added to the graph. | |
501 | |
502 """ | |
503 for nodes in permutations(range(3)): | |
504 G = nx.Graph() | |
505 G.add_nodes_from(nodes) | |
506 G.add_edges_from([(0, 1), (0, 2)]) | |
507 matching = nx.maximal_matching(G) | |
508 assert len(matching) == 1 | |
509 assert nx.is_maximal_matching(G, matching) |