Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/tests/test_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 # Test for Moody and White k-components algorithm | |
2 import pytest | |
3 import networkx as nx | |
4 from networkx.algorithms.connectivity.kcomponents import ( | |
5 build_k_number_dict, | |
6 _consolidate, | |
7 ) | |
8 | |
9 ## | |
10 # A nice synthetic graph | |
11 ## | |
12 | |
13 | |
14 def torrents_and_ferraro_graph(): | |
15 # Graph from https://arxiv.org/pdf/1503.04476v1 p.26 | |
16 G = nx.convert_node_labels_to_integers( | |
17 nx.grid_graph([5, 5]), label_attribute="labels" | |
18 ) | |
19 rlabels = nx.get_node_attributes(G, "labels") | |
20 labels = {v: k for k, v in rlabels.items()} | |
21 | |
22 for nodes in [(labels[(0, 4)], labels[(1, 4)]), (labels[(3, 4)], labels[(4, 4)])]: | |
23 new_node = G.order() + 1 | |
24 # Petersen graph is triconnected | |
25 P = nx.petersen_graph() | |
26 G = nx.disjoint_union(G, P) | |
27 # Add two edges between the grid and P | |
28 G.add_edge(new_node + 1, nodes[0]) | |
29 G.add_edge(new_node, nodes[1]) | |
30 # K5 is 4-connected | |
31 K = nx.complete_graph(5) | |
32 G = nx.disjoint_union(G, K) | |
33 # Add three edges between P and K5 | |
34 G.add_edge(new_node + 2, new_node + 11) | |
35 G.add_edge(new_node + 3, new_node + 12) | |
36 G.add_edge(new_node + 4, new_node + 13) | |
37 # Add another K5 sharing a node | |
38 G = nx.disjoint_union(G, K) | |
39 nbrs = G[new_node + 10] | |
40 G.remove_node(new_node + 10) | |
41 for nbr in nbrs: | |
42 G.add_edge(new_node + 17, nbr) | |
43 # This edge makes the graph biconnected; it's | |
44 # needed because K5s share only one node. | |
45 G.add_edge(new_node + 16, new_node + 8) | |
46 | |
47 for nodes in [(labels[(0, 0)], labels[(1, 0)]), (labels[(3, 0)], labels[(4, 0)])]: | |
48 new_node = G.order() + 1 | |
49 # Petersen graph is triconnected | |
50 P = nx.petersen_graph() | |
51 G = nx.disjoint_union(G, P) | |
52 # Add two edges between the grid and P | |
53 G.add_edge(new_node + 1, nodes[0]) | |
54 G.add_edge(new_node, nodes[1]) | |
55 # K5 is 4-connected | |
56 K = nx.complete_graph(5) | |
57 G = nx.disjoint_union(G, K) | |
58 # Add three edges between P and K5 | |
59 G.add_edge(new_node + 2, new_node + 11) | |
60 G.add_edge(new_node + 3, new_node + 12) | |
61 G.add_edge(new_node + 4, new_node + 13) | |
62 # Add another K5 sharing two nodes | |
63 G = nx.disjoint_union(G, K) | |
64 nbrs = G[new_node + 10] | |
65 G.remove_node(new_node + 10) | |
66 for nbr in nbrs: | |
67 G.add_edge(new_node + 17, nbr) | |
68 nbrs2 = G[new_node + 9] | |
69 G.remove_node(new_node + 9) | |
70 for nbr in nbrs2: | |
71 G.add_edge(new_node + 18, nbr) | |
72 return G | |
73 | |
74 | |
75 def test_directed(): | |
76 with pytest.raises(nx.NetworkXNotImplemented): | |
77 G = nx.gnp_random_graph(10, 0.2, directed=True, seed=42) | |
78 nx.k_components(G) | |
79 | |
80 | |
81 # Helper function | |
82 def _check_connectivity(G, k_components): | |
83 for k, components in k_components.items(): | |
84 if k < 3: | |
85 continue | |
86 # check that k-components have node connectivity >= k. | |
87 for component in components: | |
88 C = G.subgraph(component) | |
89 K = nx.node_connectivity(C) | |
90 assert K >= k | |
91 | |
92 | |
93 @pytest.mark.slow | |
94 def test_torrents_and_ferraro_graph(): | |
95 G = torrents_and_ferraro_graph() | |
96 result = nx.k_components(G) | |
97 _check_connectivity(G, result) | |
98 | |
99 # In this example graph there are 8 3-components, 4 with 15 nodes | |
100 # and 4 with 5 nodes. | |
101 assert len(result[3]) == 8 | |
102 assert len([c for c in result[3] if len(c) == 15]) == 4 | |
103 assert len([c for c in result[3] if len(c) == 5]) == 4 | |
104 # There are also 8 4-components all with 5 nodes. | |
105 assert len(result[4]) == 8 | |
106 assert all(len(c) == 5 for c in result[4]) | |
107 | |
108 | |
109 @pytest.mark.slow | |
110 def test_random_gnp(): | |
111 G = nx.gnp_random_graph(50, 0.2, seed=42) | |
112 result = nx.k_components(G) | |
113 _check_connectivity(G, result) | |
114 | |
115 | |
116 @pytest.mark.slow | |
117 def test_shell(): | |
118 constructor = [(20, 80, 0.8), (80, 180, 0.6)] | |
119 G = nx.random_shell_graph(constructor, seed=42) | |
120 result = nx.k_components(G) | |
121 _check_connectivity(G, result) | |
122 | |
123 | |
124 def test_configuration(): | |
125 deg_seq = nx.random_powerlaw_tree_sequence(100, tries=5, seed=72) | |
126 G = nx.Graph(nx.configuration_model(deg_seq)) | |
127 G.remove_edges_from(nx.selfloop_edges(G)) | |
128 result = nx.k_components(G) | |
129 _check_connectivity(G, result) | |
130 | |
131 | |
132 def test_karate(): | |
133 G = nx.karate_club_graph() | |
134 result = nx.k_components(G) | |
135 _check_connectivity(G, result) | |
136 | |
137 | |
138 def test_karate_component_number(): | |
139 karate_k_num = { | |
140 0: 4, | |
141 1: 4, | |
142 2: 4, | |
143 3: 4, | |
144 4: 3, | |
145 5: 3, | |
146 6: 3, | |
147 7: 4, | |
148 8: 4, | |
149 9: 2, | |
150 10: 3, | |
151 11: 1, | |
152 12: 2, | |
153 13: 4, | |
154 14: 2, | |
155 15: 2, | |
156 16: 2, | |
157 17: 2, | |
158 18: 2, | |
159 19: 3, | |
160 20: 2, | |
161 21: 2, | |
162 22: 2, | |
163 23: 3, | |
164 24: 3, | |
165 25: 3, | |
166 26: 2, | |
167 27: 3, | |
168 28: 3, | |
169 29: 3, | |
170 30: 4, | |
171 31: 3, | |
172 32: 4, | |
173 33: 4, | |
174 } | |
175 G = nx.karate_club_graph() | |
176 k_components = nx.k_components(G) | |
177 k_num = build_k_number_dict(k_components) | |
178 assert karate_k_num == k_num | |
179 | |
180 | |
181 def test_davis_southern_women(): | |
182 G = nx.davis_southern_women_graph() | |
183 result = nx.k_components(G) | |
184 _check_connectivity(G, result) | |
185 | |
186 | |
187 def test_davis_southern_women_detail_3_and_4(): | |
188 solution = { | |
189 3: [ | |
190 { | |
191 "Nora Fayette", | |
192 "E10", | |
193 "Myra Liddel", | |
194 "E12", | |
195 "E14", | |
196 "Frances Anderson", | |
197 "Evelyn Jefferson", | |
198 "Ruth DeSand", | |
199 "Helen Lloyd", | |
200 "Eleanor Nye", | |
201 "E9", | |
202 "E8", | |
203 "E5", | |
204 "E4", | |
205 "E7", | |
206 "E6", | |
207 "E1", | |
208 "Verne Sanderson", | |
209 "E3", | |
210 "E2", | |
211 "Theresa Anderson", | |
212 "Pearl Oglethorpe", | |
213 "Katherina Rogers", | |
214 "Brenda Rogers", | |
215 "E13", | |
216 "Charlotte McDowd", | |
217 "Sylvia Avondale", | |
218 "Laura Mandeville", | |
219 } | |
220 ], | |
221 4: [ | |
222 { | |
223 "Nora Fayette", | |
224 "E10", | |
225 "Verne Sanderson", | |
226 "E12", | |
227 "Frances Anderson", | |
228 "Evelyn Jefferson", | |
229 "Ruth DeSand", | |
230 "Helen Lloyd", | |
231 "Eleanor Nye", | |
232 "E9", | |
233 "E8", | |
234 "E5", | |
235 "E4", | |
236 "E7", | |
237 "E6", | |
238 "Myra Liddel", | |
239 "E3", | |
240 "Theresa Anderson", | |
241 "Katherina Rogers", | |
242 "Brenda Rogers", | |
243 "Charlotte McDowd", | |
244 "Sylvia Avondale", | |
245 "Laura Mandeville", | |
246 } | |
247 ], | |
248 } | |
249 G = nx.davis_southern_women_graph() | |
250 result = nx.k_components(G) | |
251 for k, components in result.items(): | |
252 if k < 3: | |
253 continue | |
254 assert len(components) == len(solution[k]) | |
255 for component in components: | |
256 assert component in solution[k] | |
257 | |
258 | |
259 def test_set_consolidation_rosettacode(): | |
260 # Tests from http://rosettacode.org/wiki/Set_consolidation | |
261 def list_of_sets_equal(result, solution): | |
262 assert {frozenset(s) for s in result} == {frozenset(s) for s in solution} | |
263 | |
264 question = [{"A", "B"}, {"C", "D"}] | |
265 solution = [{"A", "B"}, {"C", "D"}] | |
266 list_of_sets_equal(_consolidate(question, 1), solution) | |
267 question = [{"A", "B"}, {"B", "C"}] | |
268 solution = [{"A", "B", "C"}] | |
269 list_of_sets_equal(_consolidate(question, 1), solution) | |
270 question = [{"A", "B"}, {"C", "D"}, {"D", "B"}] | |
271 solution = [{"A", "C", "B", "D"}] | |
272 list_of_sets_equal(_consolidate(question, 1), solution) | |
273 question = [{"H", "I", "K"}, {"A", "B"}, {"C", "D"}, {"D", "B"}, {"F", "G", "H"}] | |
274 solution = [{"A", "C", "B", "D"}, {"G", "F", "I", "H", "K"}] | |
275 list_of_sets_equal(_consolidate(question, 1), solution) | |
276 question = [ | |
277 {"A", "H"}, | |
278 {"H", "I", "K"}, | |
279 {"A", "B"}, | |
280 {"C", "D"}, | |
281 {"D", "B"}, | |
282 {"F", "G", "H"}, | |
283 ] | |
284 solution = [{"A", "C", "B", "D", "G", "F", "I", "H", "K"}] | |
285 list_of_sets_equal(_consolidate(question, 1), solution) | |
286 question = [ | |
287 {"H", "I", "K"}, | |
288 {"A", "B"}, | |
289 {"C", "D"}, | |
290 {"D", "B"}, | |
291 {"F", "G", "H"}, | |
292 {"A", "H"}, | |
293 ] | |
294 solution = [{"A", "C", "B", "D", "G", "F", "I", "H", "K"}] | |
295 list_of_sets_equal(_consolidate(question, 1), solution) |