### comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_edge_kcomponents.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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()
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
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 = 
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)
378 clique2 = frozenset(paths)
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 = [
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 = 
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 = 
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 = 
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)