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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
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:
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
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:
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
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:
112 nbrs2 = G[new_node + 9]
113 G.remove_node(new_node + 9)
114 for nbr in nbrs2:
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()
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
265 for G, A in self.GA:
266 for n, nbrs in G.adj.items():
270
272 for G, A in self.GA:
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 )