Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_edge_kcomponents.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 itertools as it | |
3 import pytest | |
4 from networkx.utils import pairwise | |
5 from networkx.algorithms.connectivity import bridge_components, EdgeComponentAuxGraph | |
6 from networkx.algorithms.connectivity.edge_kcomponents import general_k_edge_subgraphs | |
7 | |
8 | |
9 # ---------------- | |
10 # Helper functions | |
11 # ---------------- | |
12 | |
13 | |
14 def fset(list_of_sets): | |
15 """ allows == to be used for list of sets """ | |
16 return set(map(frozenset, list_of_sets)) | |
17 | |
18 | |
19 def _assert_subgraph_edge_connectivity(G, ccs_subgraph, k): | |
20 """ | |
21 tests properties of k-edge-connected subgraphs | |
22 | |
23 the actual edge connectivity should be no less than k unless the cc is a | |
24 single node. | |
25 """ | |
26 for cc in ccs_subgraph: | |
27 C = G.subgraph(cc) | |
28 if len(cc) > 1: | |
29 connectivity = nx.edge_connectivity(C) | |
30 assert connectivity >= k | |
31 | |
32 | |
33 def _memo_connectivity(G, u, v, memo): | |
34 edge = (u, v) | |
35 if edge in memo: | |
36 return memo[edge] | |
37 if not G.is_directed(): | |
38 redge = (v, u) | |
39 if redge in memo: | |
40 return memo[redge] | |
41 memo[edge] = nx.edge_connectivity(G, *edge) | |
42 return memo[edge] | |
43 | |
44 | |
45 def _all_pairs_connectivity(G, cc, k, memo): | |
46 # Brute force check | |
47 for u, v in it.combinations(cc, 2): | |
48 # Use a memoization dict to save on computation | |
49 connectivity = _memo_connectivity(G, u, v, memo) | |
50 if G.is_directed(): | |
51 connectivity = min(connectivity, _memo_connectivity(G, v, u, memo)) | |
52 assert connectivity >= k | |
53 | |
54 | |
55 def _assert_local_cc_edge_connectivity(G, ccs_local, k, memo): | |
56 """ | |
57 tests properties of k-edge-connected components | |
58 | |
59 the local edge connectivity between each pair of nodes in the the original | |
60 graph should be no less than k unless the cc is a single node. | |
61 """ | |
62 for cc in ccs_local: | |
63 if len(cc) > 1: | |
64 # Strategy for testing a bit faster: If the subgraph has high edge | |
65 # connectivity then it must have local connectivity | |
66 C = G.subgraph(cc) | |
67 connectivity = nx.edge_connectivity(C) | |
68 if connectivity < k: | |
69 # Otherwise do the brute force (with memoization) check | |
70 _all_pairs_connectivity(G, cc, k, memo) | |
71 | |
72 | |
73 # Helper function | |
74 def _check_edge_connectivity(G): | |
75 """ | |
76 Helper - generates all k-edge-components using the aux graph. Checks the | |
77 both local and subgraph edge connectivity of each cc. Also checks that | |
78 alternate methods of computing the k-edge-ccs generate the same result. | |
79 """ | |
80 # Construct the auxiliary graph that can be used to make each k-cc or k-sub | |
81 aux_graph = EdgeComponentAuxGraph.construct(G) | |
82 | |
83 # memoize the local connectivity in this graph | |
84 memo = {} | |
85 | |
86 for k in it.count(1): | |
87 # Test "local" k-edge-components and k-edge-subgraphs | |
88 ccs_local = fset(aux_graph.k_edge_components(k)) | |
89 ccs_subgraph = fset(aux_graph.k_edge_subgraphs(k)) | |
90 | |
91 # Check connectivity properties that should be garuenteed by the | |
92 # algorithms. | |
93 _assert_local_cc_edge_connectivity(G, ccs_local, k, memo) | |
94 _assert_subgraph_edge_connectivity(G, ccs_subgraph, k) | |
95 | |
96 if k == 1 or k == 2 and not G.is_directed(): | |
97 assert ( | |
98 ccs_local == ccs_subgraph | |
99 ), "Subgraphs and components should be the same when k == 1 or (k == 2 and not G.directed())" | |
100 | |
101 if G.is_directed(): | |
102 # Test special case methods are the same as the aux graph | |
103 if k == 1: | |
104 alt_sccs = fset(nx.strongly_connected_components(G)) | |
105 assert alt_sccs == ccs_local, "k=1 failed alt" | |
106 assert alt_sccs == ccs_subgraph, "k=1 failed alt" | |
107 else: | |
108 # Test special case methods are the same as the aux graph | |
109 if k == 1: | |
110 alt_ccs = fset(nx.connected_components(G)) | |
111 assert alt_ccs == ccs_local, "k=1 failed alt" | |
112 assert alt_ccs == ccs_subgraph, "k=1 failed alt" | |
113 elif k == 2: | |
114 alt_bridge_ccs = fset(bridge_components(G)) | |
115 assert alt_bridge_ccs == ccs_local, "k=2 failed alt" | |
116 assert alt_bridge_ccs == ccs_subgraph, "k=2 failed alt" | |
117 # if new methods for k == 3 or k == 4 are implemented add them here | |
118 | |
119 # Check the general subgraph method works by itself | |
120 alt_subgraph_ccs = fset( | |
121 [set(C.nodes()) for C in general_k_edge_subgraphs(G, k=k)] | |
122 ) | |
123 assert alt_subgraph_ccs == ccs_subgraph, "alt subgraph method failed" | |
124 | |
125 # Stop once k is larger than all special case methods | |
126 # and we cannot break down ccs any further. | |
127 if k > 2 and all(len(cc) == 1 for cc in ccs_local): | |
128 break | |
129 | |
130 | |
131 # ---------------- | |
132 # Misc tests | |
133 # ---------------- | |
134 | |
135 | |
136 def test_zero_k_exception(): | |
137 G = nx.Graph() | |
138 # functions that return generators error immediately | |
139 pytest.raises(ValueError, nx.k_edge_components, G, k=0) | |
140 pytest.raises(ValueError, nx.k_edge_subgraphs, G, k=0) | |
141 | |
142 # actual generators only error when you get the first item | |
143 aux_graph = EdgeComponentAuxGraph.construct(G) | |
144 pytest.raises(ValueError, list, aux_graph.k_edge_components(k=0)) | |
145 pytest.raises(ValueError, list, aux_graph.k_edge_subgraphs(k=0)) | |
146 | |
147 pytest.raises(ValueError, list, general_k_edge_subgraphs(G, k=0)) | |
148 | |
149 | |
150 def test_empty_input(): | |
151 G = nx.Graph() | |
152 assert [] == list(nx.k_edge_components(G, k=5)) | |
153 assert [] == list(nx.k_edge_subgraphs(G, k=5)) | |
154 | |
155 G = nx.DiGraph() | |
156 assert [] == list(nx.k_edge_components(G, k=5)) | |
157 assert [] == list(nx.k_edge_subgraphs(G, k=5)) | |
158 | |
159 | |
160 def test_not_implemented(): | |
161 G = nx.MultiGraph() | |
162 pytest.raises(nx.NetworkXNotImplemented, EdgeComponentAuxGraph.construct, G) | |
163 pytest.raises(nx.NetworkXNotImplemented, nx.k_edge_components, G, k=2) | |
164 pytest.raises(nx.NetworkXNotImplemented, nx.k_edge_subgraphs, G, k=2) | |
165 pytest.raises(nx.NetworkXNotImplemented, bridge_components, G) | |
166 pytest.raises(nx.NetworkXNotImplemented, bridge_components, nx.DiGraph()) | |
167 | |
168 | |
169 def test_general_k_edge_subgraph_quick_return(): | |
170 # tests quick return optimization | |
171 G = nx.Graph() | |
172 G.add_node(0) | |
173 subgraphs = list(general_k_edge_subgraphs(G, k=1)) | |
174 assert len(subgraphs) == 1 | |
175 for subgraph in subgraphs: | |
176 assert subgraph.number_of_nodes() == 1 | |
177 | |
178 G.add_node(1) | |
179 subgraphs = list(general_k_edge_subgraphs(G, k=1)) | |
180 assert len(subgraphs) == 2 | |
181 for subgraph in subgraphs: | |
182 assert subgraph.number_of_nodes() == 1 | |
183 | |
184 | |
185 # ---------------- | |
186 # Undirected tests | |
187 # ---------------- | |
188 | |
189 | |
190 def test_random_gnp(): | |
191 # seeds = [1550709854, 1309423156, 4208992358, 2785630813, 1915069929] | |
192 seeds = [12, 13] | |
193 | |
194 for seed in seeds: | |
195 G = nx.gnp_random_graph(20, 0.2, seed=seed) | |
196 _check_edge_connectivity(G) | |
197 | |
198 | |
199 def test_configuration(): | |
200 # seeds = [2718183590, 2470619828, 1694705158, 3001036531, 2401251497] | |
201 seeds = [14, 15] | |
202 for seed in seeds: | |
203 deg_seq = nx.random_powerlaw_tree_sequence(20, seed=seed, tries=5000) | |
204 G = nx.Graph(nx.configuration_model(deg_seq, seed=seed)) | |
205 G.remove_edges_from(nx.selfloop_edges(G)) | |
206 _check_edge_connectivity(G) | |
207 | |
208 | |
209 def test_shell(): | |
210 # seeds = [2057382236, 3331169846, 1840105863, 476020778, 2247498425] | |
211 seeds = [20] | |
212 for seed in seeds: | |
213 constructor = [(12, 70, 0.8), (15, 40, 0.6)] | |
214 G = nx.random_shell_graph(constructor, seed=seed) | |
215 _check_edge_connectivity(G) | |
216 | |
217 | |
218 def test_karate(): | |
219 G = nx.karate_club_graph() | |
220 _check_edge_connectivity(G) | |
221 | |
222 | |
223 def test_tarjan_bridge(): | |
224 # graph from tarjan paper | |
225 # RE Tarjan - "A note on finding the bridges of a graph" | |
226 # Information Processing Letters, 1974 - Elsevier | |
227 # doi:10.1016/0020-0190(74)90003-9. | |
228 # define 2-connected components and bridges | |
229 ccs = [ | |
230 (1, 2, 4, 3, 1, 4), | |
231 (5, 6, 7, 5), | |
232 (8, 9, 10, 8), | |
233 (17, 18, 16, 15, 17), | |
234 (11, 12, 14, 13, 11, 14), | |
235 ] | |
236 bridges = [(4, 8), (3, 5), (3, 17)] | |
237 G = nx.Graph(it.chain(*(pairwise(path) for path in ccs + bridges))) | |
238 _check_edge_connectivity(G) | |
239 | |
240 | |
241 def test_bridge_cc(): | |
242 # define 2-connected components and bridges | |
243 cc2 = [(1, 2, 4, 3, 1, 4), (8, 9, 10, 8), (11, 12, 13, 11)] | |
244 bridges = [(4, 8), (3, 5), (20, 21), (22, 23, 24)] | |
245 G = nx.Graph(it.chain(*(pairwise(path) for path in cc2 + bridges))) | |
246 bridge_ccs = fset(bridge_components(G)) | |
247 target_ccs = fset( | |
248 [{1, 2, 3, 4}, {5}, {8, 9, 10}, {11, 12, 13}, {20}, {21}, {22}, {23}, {24}] | |
249 ) | |
250 assert bridge_ccs == target_ccs | |
251 _check_edge_connectivity(G) | |
252 | |
253 | |
254 def test_undirected_aux_graph(): | |
255 # Graph similar to the one in | |
256 # http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264 | |
257 a, b, c, d, e, f, g, h, i = "abcdefghi" | |
258 paths = [ | |
259 (a, d, b, f, c), | |
260 (a, e, b), | |
261 (a, e, b, c, g, b, a), | |
262 (c, b), | |
263 (f, g, f), | |
264 (h, i), | |
265 ] | |
266 G = nx.Graph(it.chain(*[pairwise(path) for path in paths])) | |
267 aux_graph = EdgeComponentAuxGraph.construct(G) | |
268 | |
269 components_1 = fset(aux_graph.k_edge_subgraphs(k=1)) | |
270 target_1 = fset([{a, b, c, d, e, f, g}, {h, i}]) | |
271 assert target_1 == components_1 | |
272 | |
273 # Check that the undirected case for k=1 agrees with CCs | |
274 alt_1 = fset(nx.k_edge_subgraphs(G, k=1)) | |
275 assert alt_1 == components_1 | |
276 | |
277 components_2 = fset(aux_graph.k_edge_subgraphs(k=2)) | |
278 target_2 = fset([{a, b, c, d, e, f, g}, {h}, {i}]) | |
279 assert target_2 == components_2 | |
280 | |
281 # Check that the undirected case for k=2 agrees with bridge components | |
282 alt_2 = fset(nx.k_edge_subgraphs(G, k=2)) | |
283 assert alt_2 == components_2 | |
284 | |
285 components_3 = fset(aux_graph.k_edge_subgraphs(k=3)) | |
286 target_3 = fset([{a}, {b, c, f, g}, {d}, {e}, {h}, {i}]) | |
287 assert target_3 == components_3 | |
288 | |
289 components_4 = fset(aux_graph.k_edge_subgraphs(k=4)) | |
290 target_4 = fset([{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}]) | |
291 assert target_4 == components_4 | |
292 | |
293 _check_edge_connectivity(G) | |
294 | |
295 | |
296 def test_local_subgraph_difference(): | |
297 paths = [ | |
298 (11, 12, 13, 14, 11, 13, 14, 12), # first 4-clique | |
299 (21, 22, 23, 24, 21, 23, 24, 22), # second 4-clique | |
300 # paths connecting each node of the 4 cliques | |
301 (11, 101, 21), | |
302 (12, 102, 22), | |
303 (13, 103, 23), | |
304 (14, 104, 24), | |
305 ] | |
306 G = nx.Graph(it.chain(*[pairwise(path) for path in paths])) | |
307 aux_graph = EdgeComponentAuxGraph.construct(G) | |
308 | |
309 # Each clique is returned separately in k-edge-subgraphs | |
310 subgraph_ccs = fset(aux_graph.k_edge_subgraphs(3)) | |
311 subgraph_target = fset( | |
312 [{101}, {102}, {103}, {104}, {21, 22, 23, 24}, {11, 12, 13, 14}] | |
313 ) | |
314 assert subgraph_ccs == subgraph_target | |
315 | |
316 # But in k-edge-ccs they are returned together | |
317 # because they are locally 3-edge-connected | |
318 local_ccs = fset(aux_graph.k_edge_components(3)) | |
319 local_target = fset([{101}, {102}, {103}, {104}, {11, 12, 13, 14, 21, 22, 23, 24}]) | |
320 assert local_ccs == local_target | |
321 | |
322 | |
323 def test_local_subgraph_difference_directed(): | |
324 dipaths = [(1, 2, 3, 4, 1), (1, 3, 1)] | |
325 G = nx.DiGraph(it.chain(*[pairwise(path) for path in dipaths])) | |
326 | |
327 assert fset(nx.k_edge_components(G, k=1)) == fset(nx.k_edge_subgraphs(G, k=1)) | |
328 | |
329 # Unlike undirected graphs, when k=2, for directed graphs there is a case | |
330 # where the k-edge-ccs are not the same as the k-edge-subgraphs. | |
331 # (in directed graphs ccs and subgraphs are the same when k=2) | |
332 assert fset(nx.k_edge_components(G, k=2)) != fset(nx.k_edge_subgraphs(G, k=2)) | |
333 | |
334 assert fset(nx.k_edge_components(G, k=3)) == fset(nx.k_edge_subgraphs(G, k=3)) | |
335 | |
336 _check_edge_connectivity(G) | |
337 | |
338 | |
339 def test_triangles(): | |
340 paths = [ | |
341 (11, 12, 13, 11), # first 3-clique | |
342 (21, 22, 23, 21), # second 3-clique | |
343 (11, 21), # connected by an edge | |
344 ] | |
345 G = nx.Graph(it.chain(*[pairwise(path) for path in paths])) | |
346 | |
347 # subgraph and ccs are the same in all cases here | |
348 assert fset(nx.k_edge_components(G, k=1)) == fset(nx.k_edge_subgraphs(G, k=1)) | |
349 | |
350 assert fset(nx.k_edge_components(G, k=2)) == fset(nx.k_edge_subgraphs(G, k=2)) | |
351 | |
352 assert fset(nx.k_edge_components(G, k=3)) == fset(nx.k_edge_subgraphs(G, k=3)) | |
353 | |
354 _check_edge_connectivity(G) | |
355 | |
356 | |
357 def test_four_clique(): | |
358 paths = [ | |
359 (11, 12, 13, 14, 11, 13, 14, 12), # first 4-clique | |
360 (21, 22, 23, 24, 21, 23, 24, 22), # second 4-clique | |
361 # paths connecting the 4 cliques such that they are | |
362 # 3-connected in G, but not in the subgraph. | |
363 # Case where the nodes bridging them do not have degree less than 3. | |
364 (100, 13), | |
365 (12, 100, 22), | |
366 (13, 200, 23), | |
367 (14, 300, 24), | |
368 ] | |
369 G = nx.Graph(it.chain(*[pairwise(path) for path in paths])) | |
370 | |
371 # The subgraphs and ccs are different for k=3 | |
372 local_ccs = fset(nx.k_edge_components(G, k=3)) | |
373 subgraphs = fset(nx.k_edge_subgraphs(G, k=3)) | |
374 assert local_ccs != subgraphs | |
375 | |
376 # The cliques ares in the same cc | |
377 clique1 = frozenset(paths[0]) | |
378 clique2 = frozenset(paths[1]) | |
379 assert clique1.union(clique2).union({100}) in local_ccs | |
380 | |
381 # but different subgraphs | |
382 assert clique1 in subgraphs | |
383 assert clique2 in subgraphs | |
384 | |
385 assert G.degree(100) == 3 | |
386 | |
387 _check_edge_connectivity(G) | |
388 | |
389 | |
390 def test_five_clique(): | |
391 # Make a graph that can be disconnected less than 4 edges, but no node has | |
392 # degree less than 4. | |
393 G = nx.disjoint_union(nx.complete_graph(5), nx.complete_graph(5)) | |
394 paths = [ | |
395 # add aux-connections | |
396 (1, 100, 6), | |
397 (2, 100, 7), | |
398 (3, 200, 8), | |
399 (4, 200, 100), | |
400 ] | |
401 G.add_edges_from(it.chain(*[pairwise(path) for path in paths])) | |
402 assert min(dict(nx.degree(G)).values()) == 4 | |
403 | |
404 # For k=3 they are the same | |
405 assert fset(nx.k_edge_components(G, k=3)) == fset(nx.k_edge_subgraphs(G, k=3)) | |
406 | |
407 # For k=4 they are the different | |
408 # the aux nodes are in the same CC as clique 1 but no the same subgraph | |
409 assert fset(nx.k_edge_components(G, k=4)) != fset(nx.k_edge_subgraphs(G, k=4)) | |
410 | |
411 # For k=5 they are not the same | |
412 assert fset(nx.k_edge_components(G, k=5)) != fset(nx.k_edge_subgraphs(G, k=5)) | |
413 | |
414 # For k=6 they are the same | |
415 assert fset(nx.k_edge_components(G, k=6)) == fset(nx.k_edge_subgraphs(G, k=6)) | |
416 _check_edge_connectivity(G) | |
417 | |
418 | |
419 # ---------------- | |
420 # Undirected tests | |
421 # ---------------- | |
422 | |
423 | |
424 def test_directed_aux_graph(): | |
425 # Graph similar to the one in | |
426 # http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264 | |
427 a, b, c, d, e, f, g, h, i = "abcdefghi" | |
428 dipaths = [ | |
429 (a, d, b, f, c), | |
430 (a, e, b), | |
431 (a, e, b, c, g, b, a), | |
432 (c, b), | |
433 (f, g, f), | |
434 (h, i), | |
435 ] | |
436 G = nx.DiGraph(it.chain(*[pairwise(path) for path in dipaths])) | |
437 aux_graph = EdgeComponentAuxGraph.construct(G) | |
438 | |
439 components_1 = fset(aux_graph.k_edge_subgraphs(k=1)) | |
440 target_1 = fset([{a, b, c, d, e, f, g}, {h}, {i}]) | |
441 assert target_1 == components_1 | |
442 | |
443 # Check that the directed case for k=1 agrees with SCCs | |
444 alt_1 = fset(nx.strongly_connected_components(G)) | |
445 assert alt_1 == components_1 | |
446 | |
447 components_2 = fset(aux_graph.k_edge_subgraphs(k=2)) | |
448 target_2 = fset([{i}, {e}, {d}, {b, c, f, g}, {h}, {a}]) | |
449 assert target_2 == components_2 | |
450 | |
451 components_3 = fset(aux_graph.k_edge_subgraphs(k=3)) | |
452 target_3 = fset([{a}, {b}, {c}, {d}, {e}, {f}, {g}, {h}, {i}]) | |
453 assert target_3 == components_3 | |
454 | |
455 | |
456 def test_random_gnp_directed(): | |
457 # seeds = [3894723670, 500186844, 267231174, 2181982262, 1116750056] | |
458 seeds = [21] | |
459 for seed in seeds: | |
460 G = nx.gnp_random_graph(20, 0.2, directed=True, seed=seed) | |
461 _check_edge_connectivity(G) | |
462 | |
463 | |
464 def test_configuration_directed(): | |
465 # seeds = [671221681, 2403749451, 124433910, 672335939, 1193127215] | |
466 seeds = [67] | |
467 for seed in seeds: | |
468 deg_seq = nx.random_powerlaw_tree_sequence(20, seed=seed, tries=5000) | |
469 G = nx.DiGraph(nx.configuration_model(deg_seq, seed=seed)) | |
470 G.remove_edges_from(nx.selfloop_edges(G)) | |
471 _check_edge_connectivity(G) | |
472 | |
473 | |
474 def test_shell_directed(): | |
475 # seeds = [3134027055, 4079264063, 1350769518, 1405643020, 530038094] | |
476 seeds = [31] | |
477 for seed in seeds: | |
478 constructor = [(12, 70, 0.8), (15, 40, 0.6)] | |
479 G = nx.random_shell_graph(constructor, seed=seed).to_directed() | |
480 _check_edge_connectivity(G) | |
481 | |
482 | |
483 def test_karate_directed(): | |
484 G = nx.karate_club_graph().to_directed() | |
485 _check_edge_connectivity(G) |