Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/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 approximation to k-components algorithm | |
2 import pytest | |
3 import networkx as nx | |
4 from networkx.algorithms.approximation import k_components | |
5 from networkx.algorithms.approximation.kcomponents import _AntiGraph, _same | |
6 | |
7 | |
8 def build_k_number_dict(k_components): | |
9 k_num = {} | |
10 for k, comps in sorted(k_components.items()): | |
11 for comp in comps: | |
12 for node in comp: | |
13 k_num[node] = k | |
14 return k_num | |
15 | |
16 | |
17 ## | |
18 # Some nice synthetic graphs | |
19 ## | |
20 | |
21 | |
22 def graph_example_1(): | |
23 G = nx.convert_node_labels_to_integers( | |
24 nx.grid_graph([5, 5]), label_attribute="labels" | |
25 ) | |
26 rlabels = nx.get_node_attributes(G, "labels") | |
27 labels = {v: k for k, v in rlabels.items()} | |
28 | |
29 for nodes in [ | |
30 (labels[(0, 0)], labels[(1, 0)]), | |
31 (labels[(0, 4)], labels[(1, 4)]), | |
32 (labels[(3, 0)], labels[(4, 0)]), | |
33 (labels[(3, 4)], labels[(4, 4)]), | |
34 ]: | |
35 new_node = G.order() + 1 | |
36 # Petersen graph is triconnected | |
37 P = nx.petersen_graph() | |
38 G = nx.disjoint_union(G, P) | |
39 # Add two edges between the grid and P | |
40 G.add_edge(new_node + 1, nodes[0]) | |
41 G.add_edge(new_node, nodes[1]) | |
42 # K5 is 4-connected | |
43 K = nx.complete_graph(5) | |
44 G = nx.disjoint_union(G, K) | |
45 # Add three edges between P and K5 | |
46 G.add_edge(new_node + 2, new_node + 11) | |
47 G.add_edge(new_node + 3, new_node + 12) | |
48 G.add_edge(new_node + 4, new_node + 13) | |
49 # Add another K5 sharing a node | |
50 G = nx.disjoint_union(G, K) | |
51 nbrs = G[new_node + 10] | |
52 G.remove_node(new_node + 10) | |
53 for nbr in nbrs: | |
54 G.add_edge(new_node + 17, nbr) | |
55 G.add_edge(new_node + 16, new_node + 5) | |
56 return G | |
57 | |
58 | |
59 def torrents_and_ferraro_graph(): | |
60 G = nx.convert_node_labels_to_integers( | |
61 nx.grid_graph([5, 5]), label_attribute="labels" | |
62 ) | |
63 rlabels = nx.get_node_attributes(G, "labels") | |
64 labels = {v: k for k, v in rlabels.items()} | |
65 | |
66 for nodes in [(labels[(0, 4)], labels[(1, 4)]), (labels[(3, 4)], labels[(4, 4)])]: | |
67 new_node = G.order() + 1 | |
68 # Petersen graph is triconnected | |
69 P = nx.petersen_graph() | |
70 G = nx.disjoint_union(G, P) | |
71 # Add two edges between the grid and P | |
72 G.add_edge(new_node + 1, nodes[0]) | |
73 G.add_edge(new_node, nodes[1]) | |
74 # K5 is 4-connected | |
75 K = nx.complete_graph(5) | |
76 G = nx.disjoint_union(G, K) | |
77 # Add three edges between P and K5 | |
78 G.add_edge(new_node + 2, new_node + 11) | |
79 G.add_edge(new_node + 3, new_node + 12) | |
80 G.add_edge(new_node + 4, new_node + 13) | |
81 # Add another K5 sharing a node | |
82 G = nx.disjoint_union(G, K) | |
83 nbrs = G[new_node + 10] | |
84 G.remove_node(new_node + 10) | |
85 for nbr in nbrs: | |
86 G.add_edge(new_node + 17, nbr) | |
87 # Commenting this makes the graph not biconnected !! | |
88 # This stupid mistake make one reviewer very angry :P | |
89 G.add_edge(new_node + 16, new_node + 8) | |
90 | |
91 for nodes in [(labels[(0, 0)], labels[(1, 0)]), (labels[(3, 0)], labels[(4, 0)])]: | |
92 new_node = G.order() + 1 | |
93 # Petersen graph is triconnected | |
94 P = nx.petersen_graph() | |
95 G = nx.disjoint_union(G, P) | |
96 # Add two edges between the grid and P | |
97 G.add_edge(new_node + 1, nodes[0]) | |
98 G.add_edge(new_node, nodes[1]) | |
99 # K5 is 4-connected | |
100 K = nx.complete_graph(5) | |
101 G = nx.disjoint_union(G, K) | |
102 # Add three edges between P and K5 | |
103 G.add_edge(new_node + 2, new_node + 11) | |
104 G.add_edge(new_node + 3, new_node + 12) | |
105 G.add_edge(new_node + 4, new_node + 13) | |
106 # Add another K5 sharing two nodes | |
107 G = nx.disjoint_union(G, K) | |
108 nbrs = G[new_node + 10] | |
109 G.remove_node(new_node + 10) | |
110 for nbr in nbrs: | |
111 G.add_edge(new_node + 17, nbr) | |
112 nbrs2 = G[new_node + 9] | |
113 G.remove_node(new_node + 9) | |
114 for nbr in nbrs2: | |
115 G.add_edge(new_node + 18, nbr) | |
116 return G | |
117 | |
118 | |
119 # Helper function | |
120 | |
121 | |
122 def _check_connectivity(G): | |
123 result = k_components(G) | |
124 for k, components in result.items(): | |
125 if k < 3: | |
126 continue | |
127 for component in components: | |
128 C = G.subgraph(component) | |
129 K = nx.node_connectivity(C) | |
130 assert K >= k | |
131 | |
132 | |
133 def test_torrents_and_ferraro_graph(): | |
134 G = torrents_and_ferraro_graph() | |
135 _check_connectivity(G) | |
136 | |
137 | |
138 def test_example_1(): | |
139 G = graph_example_1() | |
140 _check_connectivity(G) | |
141 | |
142 | |
143 def test_karate_0(): | |
144 G = nx.karate_club_graph() | |
145 _check_connectivity(G) | |
146 | |
147 | |
148 def test_karate_1(): | |
149 karate_k_num = { | |
150 0: 4, | |
151 1: 4, | |
152 2: 4, | |
153 3: 4, | |
154 4: 3, | |
155 5: 3, | |
156 6: 3, | |
157 7: 4, | |
158 8: 4, | |
159 9: 2, | |
160 10: 3, | |
161 11: 1, | |
162 12: 2, | |
163 13: 4, | |
164 14: 2, | |
165 15: 2, | |
166 16: 2, | |
167 17: 2, | |
168 18: 2, | |
169 19: 3, | |
170 20: 2, | |
171 21: 2, | |
172 22: 2, | |
173 23: 3, | |
174 24: 3, | |
175 25: 3, | |
176 26: 2, | |
177 27: 3, | |
178 28: 3, | |
179 29: 3, | |
180 30: 4, | |
181 31: 3, | |
182 32: 4, | |
183 33: 4, | |
184 } | |
185 approx_karate_k_num = karate_k_num.copy() | |
186 approx_karate_k_num[24] = 2 | |
187 approx_karate_k_num[25] = 2 | |
188 G = nx.karate_club_graph() | |
189 k_comps = k_components(G) | |
190 k_num = build_k_number_dict(k_comps) | |
191 assert k_num in (karate_k_num, approx_karate_k_num) | |
192 | |
193 | |
194 def test_example_1_detail_3_and_4(): | |
195 G = graph_example_1() | |
196 result = k_components(G) | |
197 # In this example graph there are 8 3-components, 4 with 15 nodes | |
198 # and 4 with 5 nodes. | |
199 assert len(result[3]) == 8 | |
200 assert len([c for c in result[3] if len(c) == 15]) == 4 | |
201 assert len([c for c in result[3] if len(c) == 5]) == 4 | |
202 # There are also 8 4-components all with 5 nodes. | |
203 assert len(result[4]) == 8 | |
204 assert all(len(c) == 5 for c in result[4]) | |
205 # Finally check that the k-components detected have actually node | |
206 # connectivity >= k. | |
207 for k, components in result.items(): | |
208 if k < 3: | |
209 continue | |
210 for component in components: | |
211 K = nx.node_connectivity(G.subgraph(component)) | |
212 assert K >= k | |
213 | |
214 | |
215 def test_directed(): | |
216 with pytest.raises(nx.NetworkXNotImplemented): | |
217 G = nx.gnp_random_graph(10, 0.4, directed=True) | |
218 kc = k_components(G) | |
219 | |
220 | |
221 def test_same(): | |
222 equal = {"A": 2, "B": 2, "C": 2} | |
223 slightly_different = {"A": 2, "B": 1, "C": 2} | |
224 different = {"A": 2, "B": 8, "C": 18} | |
225 assert _same(equal) | |
226 assert not _same(slightly_different) | |
227 assert _same(slightly_different, tol=1) | |
228 assert not _same(different) | |
229 assert not _same(different, tol=4) | |
230 | |
231 | |
232 class TestAntiGraph: | |
233 @classmethod | |
234 def setup_class(cls): | |
235 cls.Gnp = nx.gnp_random_graph(20, 0.8) | |
236 cls.Anp = _AntiGraph(nx.complement(cls.Gnp)) | |
237 cls.Gd = nx.davis_southern_women_graph() | |
238 cls.Ad = _AntiGraph(nx.complement(cls.Gd)) | |
239 cls.Gk = nx.karate_club_graph() | |
240 cls.Ak = _AntiGraph(nx.complement(cls.Gk)) | |
241 cls.GA = [(cls.Gnp, cls.Anp), (cls.Gd, cls.Ad), (cls.Gk, cls.Ak)] | |
242 | |
243 def test_size(self): | |
244 for G, A in self.GA: | |
245 n = G.order() | |
246 s = len(list(G.edges())) + len(list(A.edges())) | |
247 assert s == (n * (n - 1)) / 2 | |
248 | |
249 def test_degree(self): | |
250 for G, A in self.GA: | |
251 assert sorted(G.degree()) == sorted(A.degree()) | |
252 | |
253 def test_core_number(self): | |
254 for G, A in self.GA: | |
255 assert nx.core_number(G) == nx.core_number(A) | |
256 | |
257 def test_connected_components(self): | |
258 for G, A in self.GA: | |
259 gc = [set(c) for c in nx.connected_components(G)] | |
260 ac = [set(c) for c in nx.connected_components(A)] | |
261 for comp in ac: | |
262 assert comp in gc | |
263 | |
264 def test_adj(self): | |
265 for G, A in self.GA: | |
266 for n, nbrs in G.adj.items(): | |
267 a_adj = sorted((n, sorted(ad)) for n, ad in A.adj.items()) | |
268 g_adj = sorted((n, sorted(ad)) for n, ad in G.adj.items()) | |
269 assert a_adj == g_adj | |
270 | |
271 def test_adjacency(self): | |
272 for G, A in self.GA: | |
273 a_adj = list(A.adjacency()) | |
274 for n, nbrs in G.adjacency(): | |
275 assert (n, set(nbrs)) in a_adj | |
276 | |
277 def test_neighbors(self): | |
278 for G, A in self.GA: | |
279 node = list(G.nodes())[0] | |
280 assert set(G.neighbors(node)) == set(A.neighbors(node)) | |
281 | |
282 def test_node_not_in_graph(self): | |
283 for G, A in self.GA: | |
284 node = "non_existent_node" | |
285 pytest.raises(nx.NetworkXError, A.neighbors, node) | |
286 pytest.raises(nx.NetworkXError, G.neighbors, node) | |
287 | |
288 def test_degree_thingraph(self): | |
289 for G, A in self.GA: | |
290 node = list(G.nodes())[0] | |
291 nodes = list(G.nodes())[1:4] | |
292 assert G.degree(node) == A.degree(node) | |
293 assert sum(d for n, d in G.degree()) == sum(d for n, d in A.degree()) | |
294 # AntiGraph is a ThinGraph, so all the weights are 1 | |
295 assert sum(d for n, d in A.degree()) == sum( | |
296 d for n, d in A.degree(weight="weight") | |
297 ) | |
298 assert sum(d for n, d in G.degree(nodes)) == sum( | |
299 d for n, d in A.degree(nodes) | |
300 ) |