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