Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_edge_augmentation.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 random | |
2 import networkx as nx | |
3 import itertools as it | |
4 from networkx.utils import pairwise | |
5 import pytest | |
6 from networkx.algorithms.connectivity import k_edge_augmentation | |
7 from networkx.algorithms.connectivity.edge_augmentation import ( | |
8 collapse, | |
9 complement_edges, | |
10 is_locally_k_edge_connected, | |
11 is_k_edge_connected, | |
12 _unpack_available_edges, | |
13 ) | |
14 | |
15 # This should be set to the largest k for which an efficient algorithm is | |
16 # explicitly defined. | |
17 MAX_EFFICIENT_K = 2 | |
18 | |
19 | |
20 def tarjan_bridge_graph(): | |
21 # graph from tarjan paper | |
22 # RE Tarjan - "A note on finding the bridges of a graph" | |
23 # Information Processing Letters, 1974 - Elsevier | |
24 # doi:10.1016/0020-0190(74)90003-9. | |
25 # define 2-connected components and bridges | |
26 ccs = [ | |
27 (1, 2, 4, 3, 1, 4), | |
28 (5, 6, 7, 5), | |
29 (8, 9, 10, 8), | |
30 (17, 18, 16, 15, 17), | |
31 (11, 12, 14, 13, 11, 14), | |
32 ] | |
33 bridges = [(4, 8), (3, 5), (3, 17)] | |
34 G = nx.Graph(it.chain(*(pairwise(path) for path in ccs + bridges))) | |
35 return G | |
36 | |
37 | |
38 def test_weight_key(): | |
39 G = nx.Graph() | |
40 G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9]) | |
41 G.add_edges_from([(3, 8), (1, 2), (2, 3)]) | |
42 impossible = {(3, 6), (3, 9)} | |
43 rng = random.Random(0) | |
44 avail_uv = list(set(complement_edges(G)) - impossible) | |
45 avail = [(u, v, {"cost": rng.random()}) for u, v in avail_uv] | |
46 | |
47 _augment_and_check(G, k=1) | |
48 _augment_and_check(G, k=1, avail=avail_uv) | |
49 _augment_and_check(G, k=1, avail=avail, weight="cost") | |
50 | |
51 _check_augmentations(G, avail, weight="cost") | |
52 | |
53 | |
54 def test_is_locally_k_edge_connected_exceptions(): | |
55 pytest.raises(nx.NetworkXNotImplemented, is_k_edge_connected, nx.DiGraph(), k=0) | |
56 pytest.raises(nx.NetworkXNotImplemented, is_k_edge_connected, nx.MultiGraph(), k=0) | |
57 pytest.raises(ValueError, is_k_edge_connected, nx.Graph(), k=0) | |
58 | |
59 | |
60 def test_is_k_edge_connected(): | |
61 G = nx.barbell_graph(10, 0) | |
62 assert is_k_edge_connected(G, k=1) | |
63 assert not is_k_edge_connected(G, k=2) | |
64 | |
65 G = nx.Graph() | |
66 G.add_nodes_from([5, 15]) | |
67 assert not is_k_edge_connected(G, k=1) | |
68 assert not is_k_edge_connected(G, k=2) | |
69 | |
70 G = nx.complete_graph(5) | |
71 assert is_k_edge_connected(G, k=1) | |
72 assert is_k_edge_connected(G, k=2) | |
73 assert is_k_edge_connected(G, k=3) | |
74 assert is_k_edge_connected(G, k=4) | |
75 | |
76 | |
77 def test_is_k_edge_connected_exceptions(): | |
78 pytest.raises( | |
79 nx.NetworkXNotImplemented, is_locally_k_edge_connected, nx.DiGraph(), 1, 2, k=0 | |
80 ) | |
81 pytest.raises( | |
82 nx.NetworkXNotImplemented, | |
83 is_locally_k_edge_connected, | |
84 nx.MultiGraph(), | |
85 1, | |
86 2, | |
87 k=0, | |
88 ) | |
89 pytest.raises(ValueError, is_locally_k_edge_connected, nx.Graph(), 1, 2, k=0) | |
90 | |
91 | |
92 def test_is_locally_k_edge_connected(): | |
93 G = nx.barbell_graph(10, 0) | |
94 assert is_locally_k_edge_connected(G, 5, 15, k=1) | |
95 assert not is_locally_k_edge_connected(G, 5, 15, k=2) | |
96 | |
97 G = nx.Graph() | |
98 G.add_nodes_from([5, 15]) | |
99 assert not is_locally_k_edge_connected(G, 5, 15, k=2) | |
100 | |
101 | |
102 def test_null_graph(): | |
103 G = nx.Graph() | |
104 _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2) | |
105 | |
106 | |
107 def test_cliques(): | |
108 for n in range(1, 10): | |
109 G = nx.complete_graph(n) | |
110 _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2) | |
111 | |
112 | |
113 def test_clique_and_node(): | |
114 for n in range(1, 10): | |
115 G = nx.complete_graph(n) | |
116 G.add_node(n + 1) | |
117 _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2) | |
118 | |
119 | |
120 def test_point_graph(): | |
121 G = nx.Graph() | |
122 G.add_node(1) | |
123 _check_augmentations(G, max_k=MAX_EFFICIENT_K + 2) | |
124 | |
125 | |
126 def test_edgeless_graph(): | |
127 G = nx.Graph() | |
128 G.add_nodes_from([1, 2, 3, 4]) | |
129 _check_augmentations(G) | |
130 | |
131 | |
132 def test_invalid_k(): | |
133 G = nx.Graph() | |
134 pytest.raises(ValueError, list, k_edge_augmentation(G, k=-1)) | |
135 pytest.raises(ValueError, list, k_edge_augmentation(G, k=0)) | |
136 | |
137 | |
138 def test_unfeasible(): | |
139 G = tarjan_bridge_graph() | |
140 pytest.raises(nx.NetworkXUnfeasible, list, k_edge_augmentation(G, k=1, avail=[])) | |
141 | |
142 pytest.raises(nx.NetworkXUnfeasible, list, k_edge_augmentation(G, k=2, avail=[])) | |
143 | |
144 pytest.raises( | |
145 nx.NetworkXUnfeasible, list, k_edge_augmentation(G, k=2, avail=[(7, 9)]) | |
146 ) | |
147 | |
148 # partial solutions should not error if real solutions are infeasible | |
149 aug_edges = list(k_edge_augmentation(G, k=2, avail=[(7, 9)], partial=True)) | |
150 assert aug_edges == [(7, 9)] | |
151 | |
152 _check_augmentations(G, avail=[], max_k=MAX_EFFICIENT_K + 2) | |
153 | |
154 _check_augmentations(G, avail=[(7, 9)], max_k=MAX_EFFICIENT_K + 2) | |
155 | |
156 | |
157 def test_tarjan(): | |
158 G = tarjan_bridge_graph() | |
159 | |
160 aug_edges = set(_augment_and_check(G, k=2)[0]) | |
161 print(f"aug_edges = {aug_edges!r}") | |
162 # can't assert edge exactly equality due to non-determinant edge order | |
163 # but we do know the size of the solution must be 3 | |
164 assert len(aug_edges) == 3 | |
165 | |
166 avail = [ | |
167 (9, 7), | |
168 (8, 5), | |
169 (2, 10), | |
170 (6, 13), | |
171 (11, 18), | |
172 (1, 17), | |
173 (2, 3), | |
174 (16, 17), | |
175 (18, 14), | |
176 (15, 14), | |
177 ] | |
178 aug_edges = set(_augment_and_check(G, avail=avail, k=2)[0]) | |
179 | |
180 # Can't assert exact length since approximation depends on the order of a | |
181 # dict traversal. | |
182 assert len(aug_edges) <= 3 * 2 | |
183 | |
184 _check_augmentations(G, avail) | |
185 | |
186 | |
187 def test_configuration(): | |
188 # seeds = [2718183590, 2470619828, 1694705158, 3001036531, 2401251497] | |
189 seeds = [1001, 1002, 1003, 1004] | |
190 for seed in seeds: | |
191 deg_seq = nx.random_powerlaw_tree_sequence(20, seed=seed, tries=5000) | |
192 G = nx.Graph(nx.configuration_model(deg_seq, seed=seed)) | |
193 G.remove_edges_from(nx.selfloop_edges(G)) | |
194 _check_augmentations(G) | |
195 | |
196 | |
197 def test_shell(): | |
198 # seeds = [2057382236, 3331169846, 1840105863, 476020778, 2247498425] | |
199 seeds = [18] | |
200 for seed in seeds: | |
201 constructor = [(12, 70, 0.8), (15, 40, 0.6)] | |
202 G = nx.random_shell_graph(constructor, seed=seed) | |
203 _check_augmentations(G) | |
204 | |
205 | |
206 def test_karate(): | |
207 G = nx.karate_club_graph() | |
208 _check_augmentations(G) | |
209 | |
210 | |
211 def test_star(): | |
212 G = nx.star_graph(3) | |
213 _check_augmentations(G) | |
214 | |
215 G = nx.star_graph(5) | |
216 _check_augmentations(G) | |
217 | |
218 G = nx.star_graph(10) | |
219 _check_augmentations(G) | |
220 | |
221 | |
222 def test_barbell(): | |
223 G = nx.barbell_graph(5, 0) | |
224 _check_augmentations(G) | |
225 | |
226 G = nx.barbell_graph(5, 2) | |
227 _check_augmentations(G) | |
228 | |
229 G = nx.barbell_graph(5, 3) | |
230 _check_augmentations(G) | |
231 | |
232 G = nx.barbell_graph(5, 4) | |
233 _check_augmentations(G) | |
234 | |
235 | |
236 def test_bridge(): | |
237 G = nx.Graph([(2393, 2257), (2393, 2685), (2685, 2257), (1758, 2257)]) | |
238 _check_augmentations(G) | |
239 | |
240 | |
241 def test_gnp_augmentation(): | |
242 rng = random.Random(0) | |
243 G = nx.gnp_random_graph(30, 0.005, seed=0) | |
244 # Randomly make edges available | |
245 avail = { | |
246 (u, v): 1 + rng.random() for u, v in complement_edges(G) if rng.random() < 0.25 | |
247 } | |
248 _check_augmentations(G, avail) | |
249 | |
250 | |
251 def _assert_solution_properties(G, aug_edges, avail_dict=None): | |
252 """ Checks that aug_edges are consistently formatted """ | |
253 if avail_dict is not None: | |
254 assert all( | |
255 e in avail_dict for e in aug_edges | |
256 ), "when avail is specified aug-edges should be in avail" | |
257 | |
258 unique_aug = set(map(tuple, map(sorted, aug_edges))) | |
259 unique_aug = list(map(tuple, map(sorted, aug_edges))) | |
260 assert len(aug_edges) == len(unique_aug), "edges should be unique" | |
261 | |
262 assert not any(u == v for u, v in unique_aug), "should be no self-edges" | |
263 | |
264 assert not any( | |
265 G.has_edge(u, v) for u, v in unique_aug | |
266 ), "aug edges and G.edges should be disjoint" | |
267 | |
268 | |
269 def _augment_and_check( | |
270 G, k, avail=None, weight=None, verbose=False, orig_k=None, max_aug_k=None | |
271 ): | |
272 """ | |
273 Does one specific augmentation and checks for properties of the result | |
274 """ | |
275 if orig_k is None: | |
276 try: | |
277 orig_k = nx.edge_connectivity(G) | |
278 except nx.NetworkXPointlessConcept: | |
279 orig_k = 0 | |
280 info = {} | |
281 try: | |
282 if avail is not None: | |
283 # ensure avail is in dict form | |
284 avail_dict = dict(zip(*_unpack_available_edges(avail, weight=weight))) | |
285 else: | |
286 avail_dict = None | |
287 try: | |
288 # Find the augmentation if possible | |
289 generator = nx.k_edge_augmentation(G, k=k, weight=weight, avail=avail) | |
290 assert not isinstance(generator, list), "should always return an iter" | |
291 aug_edges = [] | |
292 for edge in generator: | |
293 aug_edges.append(edge) | |
294 except nx.NetworkXUnfeasible: | |
295 infeasible = True | |
296 info["infeasible"] = True | |
297 assert len(aug_edges) == 0, "should not generate anything if unfeasible" | |
298 | |
299 if avail is None: | |
300 n_nodes = G.number_of_nodes() | |
301 assert n_nodes <= k, ( | |
302 "unconstrained cases are only unfeasible if |V| <= k. " | |
303 f"Got |V|={n_nodes} and k={k}" | |
304 ) | |
305 else: | |
306 if max_aug_k is None: | |
307 G_aug_all = G.copy() | |
308 G_aug_all.add_edges_from(avail_dict.keys()) | |
309 try: | |
310 max_aug_k = nx.edge_connectivity(G_aug_all) | |
311 except nx.NetworkXPointlessConcept: | |
312 max_aug_k = 0 | |
313 | |
314 assert max_aug_k < k, ( | |
315 "avail should only be unfeasible if using all edges " | |
316 "does not achieve k-edge-connectivity" | |
317 ) | |
318 | |
319 # Test for a partial solution | |
320 partial_edges = list( | |
321 nx.k_edge_augmentation(G, k=k, weight=weight, partial=True, avail=avail) | |
322 ) | |
323 | |
324 info["n_partial_edges"] = len(partial_edges) | |
325 | |
326 if avail_dict is None: | |
327 assert set(partial_edges) == set( | |
328 complement_edges(G) | |
329 ), "unweighted partial solutions should be the complement" | |
330 elif len(avail_dict) > 0: | |
331 H = G.copy() | |
332 | |
333 # Find the partial / full augmented connectivity | |
334 H.add_edges_from(partial_edges) | |
335 partial_conn = nx.edge_connectivity(H) | |
336 | |
337 H.add_edges_from(set(avail_dict.keys())) | |
338 full_conn = nx.edge_connectivity(H) | |
339 | |
340 # Full connectivity should be no better than our partial | |
341 # solution. | |
342 assert ( | |
343 partial_conn == full_conn | |
344 ), "adding more edges should not increase k-conn" | |
345 | |
346 # Find the new edge-connectivity after adding the augmenting edges | |
347 aug_edges = partial_edges | |
348 else: | |
349 infeasible = False | |
350 | |
351 # Find the weight of the augmentation | |
352 num_edges = len(aug_edges) | |
353 if avail is not None: | |
354 total_weight = sum([avail_dict[e] for e in aug_edges]) | |
355 else: | |
356 total_weight = num_edges | |
357 | |
358 info["total_weight"] = total_weight | |
359 info["num_edges"] = num_edges | |
360 | |
361 # Find the new edge-connectivity after adding the augmenting edges | |
362 G_aug = G.copy() | |
363 G_aug.add_edges_from(aug_edges) | |
364 try: | |
365 aug_k = nx.edge_connectivity(G_aug) | |
366 except nx.NetworkXPointlessConcept: | |
367 aug_k = 0 | |
368 info["aug_k"] = aug_k | |
369 | |
370 # Do checks | |
371 if not infeasible and orig_k < k: | |
372 assert info["aug_k"] >= k, f"connectivity should increase to k={k} or more" | |
373 | |
374 assert info["aug_k"] >= orig_k, "augmenting should never reduce connectivity" | |
375 | |
376 _assert_solution_properties(G, aug_edges, avail_dict) | |
377 | |
378 except Exception: | |
379 info["failed"] = True | |
380 print(f"edges = {list(G.edges())}") | |
381 print(f"nodes = {list(G.nodes())}") | |
382 print(f"aug_edges = {list(aug_edges)}") | |
383 print(f"info = {info}") | |
384 raise | |
385 else: | |
386 if verbose: | |
387 print(f"info = {info}") | |
388 | |
389 if infeasible: | |
390 aug_edges = None | |
391 return aug_edges, info | |
392 | |
393 | |
394 def _check_augmentations(G, avail=None, max_k=None, weight=None, verbose=False): | |
395 """ Helper to check weighted/unweighted cases with multiple values of k """ | |
396 # Using all available edges, find the maximum edge-connectivity | |
397 try: | |
398 orig_k = nx.edge_connectivity(G) | |
399 except nx.NetworkXPointlessConcept: | |
400 orig_k = 0 | |
401 | |
402 if avail is not None: | |
403 all_aug_edges = _unpack_available_edges(avail, weight=weight)[0] | |
404 G_aug_all = G.copy() | |
405 G_aug_all.add_edges_from(all_aug_edges) | |
406 try: | |
407 max_aug_k = nx.edge_connectivity(G_aug_all) | |
408 except nx.NetworkXPointlessConcept: | |
409 max_aug_k = 0 | |
410 else: | |
411 max_aug_k = G.number_of_nodes() - 1 | |
412 | |
413 if max_k is None: | |
414 max_k = min(4, max_aug_k) | |
415 | |
416 avail_uniform = {e: 1 for e in complement_edges(G)} | |
417 | |
418 if verbose: | |
419 print("\n=== CHECK_AUGMENTATION ===") | |
420 print(f"G.number_of_nodes = {G.number_of_nodes()!r}") | |
421 print(f"G.number_of_edges = {G.number_of_edges()!r}") | |
422 print(f"max_k = {max_k!r}") | |
423 print(f"max_aug_k = {max_aug_k!r}") | |
424 print(f"orig_k = {orig_k!r}") | |
425 | |
426 # check augmentation for multiple values of k | |
427 for k in range(1, max_k + 1): | |
428 if verbose: | |
429 print("---------------") | |
430 print(f"Checking k = {k}") | |
431 | |
432 # Check the unweighted version | |
433 if verbose: | |
434 print("unweighted case") | |
435 aug_edges1, info1 = _augment_and_check(G, k=k, verbose=verbose, orig_k=orig_k) | |
436 | |
437 # Check that the weighted version with all available edges and uniform | |
438 # weights gives a similar solution to the unweighted case. | |
439 if verbose: | |
440 print("weighted uniform case") | |
441 aug_edges2, info2 = _augment_and_check( | |
442 G, | |
443 k=k, | |
444 avail=avail_uniform, | |
445 verbose=verbose, | |
446 orig_k=orig_k, | |
447 max_aug_k=G.number_of_nodes() - 1, | |
448 ) | |
449 | |
450 # Check the weighted version | |
451 if avail is not None: | |
452 if verbose: | |
453 print("weighted case") | |
454 aug_edges3, info3 = _augment_and_check( | |
455 G, | |
456 k=k, | |
457 avail=avail, | |
458 weight=weight, | |
459 verbose=verbose, | |
460 max_aug_k=max_aug_k, | |
461 orig_k=orig_k, | |
462 ) | |
463 | |
464 if aug_edges1 is not None: | |
465 # Check approximation ratios | |
466 if k == 1: | |
467 # when k=1, both solutions should be optimal | |
468 assert info2["total_weight"] == info1["total_weight"] | |
469 if k == 2: | |
470 # when k=2, the weighted version is an approximation | |
471 if orig_k == 0: | |
472 # the approximation ratio is 3 if G is not connected | |
473 assert info2["total_weight"] <= info1["total_weight"] * 3 | |
474 else: | |
475 # the approximation ratio is 2 if G is was connected | |
476 assert info2["total_weight"] <= info1["total_weight"] * 2 | |
477 _check_unconstrained_bridge_property(G, info1) | |
478 | |
479 | |
480 def _check_unconstrained_bridge_property(G, info1): | |
481 # Check Theorem 5 from Eswaran and Tarjan. (1975) Augmentation problems | |
482 import math | |
483 | |
484 bridge_ccs = list(nx.connectivity.bridge_components(G)) | |
485 # condense G into an forest C | |
486 C = collapse(G, bridge_ccs) | |
487 | |
488 p = len([n for n, d in C.degree() if d == 1]) # leafs | |
489 q = len([n for n, d in C.degree() if d == 0]) # isolated | |
490 if p + q > 1: | |
491 size_target = int(math.ceil(p / 2.0)) + q | |
492 size_aug = info1["num_edges"] | |
493 assert ( | |
494 size_aug == size_target | |
495 ), "augmentation size is different from what theory predicts" |