Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/operators/tests/test_product.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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 import pytest
2 import networkx as nx
3 from networkx.testing import assert_edges_equal
4
5
6 def test_tensor_product_raises():
7 with pytest.raises(nx.NetworkXError):
8 P = nx.tensor_product(nx.DiGraph(), nx.Graph())
9
10
11 def test_tensor_product_null():
12 null = nx.null_graph()
13 empty10 = nx.empty_graph(10)
14 K3 = nx.complete_graph(3)
15 K10 = nx.complete_graph(10)
16 P3 = nx.path_graph(3)
17 P10 = nx.path_graph(10)
18 # null graph
19 G = nx.tensor_product(null, null)
20 assert nx.is_isomorphic(G, null)
21 # null_graph X anything = null_graph and v.v.
22 G = nx.tensor_product(null, empty10)
23 assert nx.is_isomorphic(G, null)
24 G = nx.tensor_product(null, K3)
25 assert nx.is_isomorphic(G, null)
26 G = nx.tensor_product(null, K10)
27 assert nx.is_isomorphic(G, null)
28 G = nx.tensor_product(null, P3)
29 assert nx.is_isomorphic(G, null)
30 G = nx.tensor_product(null, P10)
31 assert nx.is_isomorphic(G, null)
32 G = nx.tensor_product(empty10, null)
33 assert nx.is_isomorphic(G, null)
34 G = nx.tensor_product(K3, null)
35 assert nx.is_isomorphic(G, null)
36 G = nx.tensor_product(K10, null)
37 assert nx.is_isomorphic(G, null)
38 G = nx.tensor_product(P3, null)
39 assert nx.is_isomorphic(G, null)
40 G = nx.tensor_product(P10, null)
41 assert nx.is_isomorphic(G, null)
42
43
44 def test_tensor_product_size():
45 P5 = nx.path_graph(5)
46 K3 = nx.complete_graph(3)
47 K5 = nx.complete_graph(5)
48
49 G = nx.tensor_product(P5, K3)
50 assert nx.number_of_nodes(G) == 5 * 3
51 G = nx.tensor_product(K3, K5)
52 assert nx.number_of_nodes(G) == 3 * 5
53
54
55 def test_tensor_product_combinations():
56 # basic smoke test, more realistic tests would be useful
57 P5 = nx.path_graph(5)
58 K3 = nx.complete_graph(3)
59 G = nx.tensor_product(P5, K3)
60 assert nx.number_of_nodes(G) == 5 * 3
61 G = nx.tensor_product(P5, nx.MultiGraph(K3))
62 assert nx.number_of_nodes(G) == 5 * 3
63 G = nx.tensor_product(nx.MultiGraph(P5), K3)
64 assert nx.number_of_nodes(G) == 5 * 3
65 G = nx.tensor_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
66 assert nx.number_of_nodes(G) == 5 * 3
67
68 G = nx.tensor_product(nx.DiGraph(P5), nx.DiGraph(K3))
69 assert nx.number_of_nodes(G) == 5 * 3
70
71
72 def test_tensor_product_classic_result():
73 K2 = nx.complete_graph(2)
74 G = nx.petersen_graph()
75 G = nx.tensor_product(G, K2)
76 assert nx.is_isomorphic(G, nx.desargues_graph())
77
78 G = nx.cycle_graph(5)
79 G = nx.tensor_product(G, K2)
80 assert nx.is_isomorphic(G, nx.cycle_graph(10))
81
82 G = nx.tetrahedral_graph()
83 G = nx.tensor_product(G, K2)
84 assert nx.is_isomorphic(G, nx.cubical_graph())
85
86
87 def test_tensor_product_random():
88 G = nx.erdos_renyi_graph(10, 2 / 10.0)
89 H = nx.erdos_renyi_graph(10, 2 / 10.0)
90 GH = nx.tensor_product(G, H)
91
92 for (u_G, u_H) in GH.nodes():
93 for (v_G, v_H) in GH.nodes():
94 if H.has_edge(u_H, v_H) and G.has_edge(u_G, v_G):
95 assert GH.has_edge((u_G, u_H), (v_G, v_H))
96 else:
97 assert not GH.has_edge((u_G, u_H), (v_G, v_H))
98
99
100 def test_cartesian_product_multigraph():
101 G = nx.MultiGraph()
102 G.add_edge(1, 2, key=0)
103 G.add_edge(1, 2, key=1)
104 H = nx.MultiGraph()
105 H.add_edge(3, 4, key=0)
106 H.add_edge(3, 4, key=1)
107 GH = nx.cartesian_product(G, H)
108 assert set(GH) == {(1, 3), (2, 3), (2, 4), (1, 4)}
109 assert {(frozenset([u, v]), k) for u, v, k in GH.edges(keys=True)} == {
110 (frozenset([u, v]), k)
111 for u, v, k in [
112 ((1, 3), (2, 3), 0),
113 ((1, 3), (2, 3), 1),
114 ((1, 3), (1, 4), 0),
115 ((1, 3), (1, 4), 1),
116 ((2, 3), (2, 4), 0),
117 ((2, 3), (2, 4), 1),
118 ((2, 4), (1, 4), 0),
119 ((2, 4), (1, 4), 1),
120 ]
121 }
122
123
124 def test_cartesian_product_raises():
125 with pytest.raises(nx.NetworkXError):
126 P = nx.cartesian_product(nx.DiGraph(), nx.Graph())
127
128
129 def test_cartesian_product_null():
130 null = nx.null_graph()
131 empty10 = nx.empty_graph(10)
132 K3 = nx.complete_graph(3)
133 K10 = nx.complete_graph(10)
134 P3 = nx.path_graph(3)
135 P10 = nx.path_graph(10)
136 # null graph
137 G = nx.cartesian_product(null, null)
138 assert nx.is_isomorphic(G, null)
139 # null_graph X anything = null_graph and v.v.
140 G = nx.cartesian_product(null, empty10)
141 assert nx.is_isomorphic(G, null)
142 G = nx.cartesian_product(null, K3)
143 assert nx.is_isomorphic(G, null)
144 G = nx.cartesian_product(null, K10)
145 assert nx.is_isomorphic(G, null)
146 G = nx.cartesian_product(null, P3)
147 assert nx.is_isomorphic(G, null)
148 G = nx.cartesian_product(null, P10)
149 assert nx.is_isomorphic(G, null)
150 G = nx.cartesian_product(empty10, null)
151 assert nx.is_isomorphic(G, null)
152 G = nx.cartesian_product(K3, null)
153 assert nx.is_isomorphic(G, null)
154 G = nx.cartesian_product(K10, null)
155 assert nx.is_isomorphic(G, null)
156 G = nx.cartesian_product(P3, null)
157 assert nx.is_isomorphic(G, null)
158 G = nx.cartesian_product(P10, null)
159 assert nx.is_isomorphic(G, null)
160
161
162 def test_cartesian_product_size():
163 # order(GXH)=order(G)*order(H)
164 K5 = nx.complete_graph(5)
165 P5 = nx.path_graph(5)
166 K3 = nx.complete_graph(3)
167 G = nx.cartesian_product(P5, K3)
168 assert nx.number_of_nodes(G) == 5 * 3
169 assert nx.number_of_edges(G) == nx.number_of_edges(P5) * nx.number_of_nodes(
170 K3
171 ) + nx.number_of_edges(K3) * nx.number_of_nodes(P5)
172 G = nx.cartesian_product(K3, K5)
173 assert nx.number_of_nodes(G) == 3 * 5
174 assert nx.number_of_edges(G) == nx.number_of_edges(K5) * nx.number_of_nodes(
175 K3
176 ) + nx.number_of_edges(K3) * nx.number_of_nodes(K5)
177
178
179 def test_cartesian_product_classic():
180 # test some classic product graphs
181 P2 = nx.path_graph(2)
182 P3 = nx.path_graph(3)
183 # cube = 2-path X 2-path
184 G = nx.cartesian_product(P2, P2)
185 G = nx.cartesian_product(P2, G)
186 assert nx.is_isomorphic(G, nx.cubical_graph())
187
188 # 3x3 grid
189 G = nx.cartesian_product(P3, P3)
190 assert nx.is_isomorphic(G, nx.grid_2d_graph(3, 3))
191
192
193 def test_cartesian_product_random():
194 G = nx.erdos_renyi_graph(10, 2 / 10.0)
195 H = nx.erdos_renyi_graph(10, 2 / 10.0)
196 GH = nx.cartesian_product(G, H)
197
198 for (u_G, u_H) in GH.nodes():
199 for (v_G, v_H) in GH.nodes():
200 if (u_G == v_G and H.has_edge(u_H, v_H)) or (
201 u_H == v_H and G.has_edge(u_G, v_G)
202 ):
203 assert GH.has_edge((u_G, u_H), (v_G, v_H))
204 else:
205 assert not GH.has_edge((u_G, u_H), (v_G, v_H))
206
207
208 def test_lexicographic_product_raises():
209 with pytest.raises(nx.NetworkXError):
210 P = nx.lexicographic_product(nx.DiGraph(), nx.Graph())
211
212
213 def test_lexicographic_product_null():
214 null = nx.null_graph()
215 empty10 = nx.empty_graph(10)
216 K3 = nx.complete_graph(3)
217 K10 = nx.complete_graph(10)
218 P3 = nx.path_graph(3)
219 P10 = nx.path_graph(10)
220 # null graph
221 G = nx.lexicographic_product(null, null)
222 assert nx.is_isomorphic(G, null)
223 # null_graph X anything = null_graph and v.v.
224 G = nx.lexicographic_product(null, empty10)
225 assert nx.is_isomorphic(G, null)
226 G = nx.lexicographic_product(null, K3)
227 assert nx.is_isomorphic(G, null)
228 G = nx.lexicographic_product(null, K10)
229 assert nx.is_isomorphic(G, null)
230 G = nx.lexicographic_product(null, P3)
231 assert nx.is_isomorphic(G, null)
232 G = nx.lexicographic_product(null, P10)
233 assert nx.is_isomorphic(G, null)
234 G = nx.lexicographic_product(empty10, null)
235 assert nx.is_isomorphic(G, null)
236 G = nx.lexicographic_product(K3, null)
237 assert nx.is_isomorphic(G, null)
238 G = nx.lexicographic_product(K10, null)
239 assert nx.is_isomorphic(G, null)
240 G = nx.lexicographic_product(P3, null)
241 assert nx.is_isomorphic(G, null)
242 G = nx.lexicographic_product(P10, null)
243 assert nx.is_isomorphic(G, null)
244
245
246 def test_lexicographic_product_size():
247 K5 = nx.complete_graph(5)
248 P5 = nx.path_graph(5)
249 K3 = nx.complete_graph(3)
250 G = nx.lexicographic_product(P5, K3)
251 assert nx.number_of_nodes(G) == 5 * 3
252 G = nx.lexicographic_product(K3, K5)
253 assert nx.number_of_nodes(G) == 3 * 5
254
255
256 def test_lexicographic_product_combinations():
257 P5 = nx.path_graph(5)
258 K3 = nx.complete_graph(3)
259 G = nx.lexicographic_product(P5, K3)
260 assert nx.number_of_nodes(G) == 5 * 3
261 G = nx.lexicographic_product(nx.MultiGraph(P5), K3)
262 assert nx.number_of_nodes(G) == 5 * 3
263 G = nx.lexicographic_product(P5, nx.MultiGraph(K3))
264 assert nx.number_of_nodes(G) == 5 * 3
265 G = nx.lexicographic_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
266 assert nx.number_of_nodes(G) == 5 * 3
267
268 # No classic easily found classic results for lexicographic product
269
270
271 def test_lexicographic_product_random():
272 G = nx.erdos_renyi_graph(10, 2 / 10.0)
273 H = nx.erdos_renyi_graph(10, 2 / 10.0)
274 GH = nx.lexicographic_product(G, H)
275
276 for (u_G, u_H) in GH.nodes():
277 for (v_G, v_H) in GH.nodes():
278 if G.has_edge(u_G, v_G) or (u_G == v_G and H.has_edge(u_H, v_H)):
279 assert GH.has_edge((u_G, u_H), (v_G, v_H))
280 else:
281 assert not GH.has_edge((u_G, u_H), (v_G, v_H))
282
283
284 def test_strong_product_raises():
285 with pytest.raises(nx.NetworkXError):
286 P = nx.strong_product(nx.DiGraph(), nx.Graph())
287
288
289 def test_strong_product_null():
290 null = nx.null_graph()
291 empty10 = nx.empty_graph(10)
292 K3 = nx.complete_graph(3)
293 K10 = nx.complete_graph(10)
294 P3 = nx.path_graph(3)
295 P10 = nx.path_graph(10)
296 # null graph
297 G = nx.strong_product(null, null)
298 assert nx.is_isomorphic(G, null)
299 # null_graph X anything = null_graph and v.v.
300 G = nx.strong_product(null, empty10)
301 assert nx.is_isomorphic(G, null)
302 G = nx.strong_product(null, K3)
303 assert nx.is_isomorphic(G, null)
304 G = nx.strong_product(null, K10)
305 assert nx.is_isomorphic(G, null)
306 G = nx.strong_product(null, P3)
307 assert nx.is_isomorphic(G, null)
308 G = nx.strong_product(null, P10)
309 assert nx.is_isomorphic(G, null)
310 G = nx.strong_product(empty10, null)
311 assert nx.is_isomorphic(G, null)
312 G = nx.strong_product(K3, null)
313 assert nx.is_isomorphic(G, null)
314 G = nx.strong_product(K10, null)
315 assert nx.is_isomorphic(G, null)
316 G = nx.strong_product(P3, null)
317 assert nx.is_isomorphic(G, null)
318 G = nx.strong_product(P10, null)
319 assert nx.is_isomorphic(G, null)
320
321
322 def test_strong_product_size():
323 K5 = nx.complete_graph(5)
324 P5 = nx.path_graph(5)
325 K3 = nx.complete_graph(3)
326 G = nx.strong_product(P5, K3)
327 assert nx.number_of_nodes(G) == 5 * 3
328 G = nx.strong_product(K3, K5)
329 assert nx.number_of_nodes(G) == 3 * 5
330
331
332 def test_strong_product_combinations():
333 P5 = nx.path_graph(5)
334 K3 = nx.complete_graph(3)
335 G = nx.strong_product(P5, K3)
336 assert nx.number_of_nodes(G) == 5 * 3
337 G = nx.strong_product(nx.MultiGraph(P5), K3)
338 assert nx.number_of_nodes(G) == 5 * 3
339 G = nx.strong_product(P5, nx.MultiGraph(K3))
340 assert nx.number_of_nodes(G) == 5 * 3
341 G = nx.strong_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
342 assert nx.number_of_nodes(G) == 5 * 3
343
344 # No classic easily found classic results for strong product
345
346
347 def test_strong_product_random():
348 G = nx.erdos_renyi_graph(10, 2 / 10.0)
349 H = nx.erdos_renyi_graph(10, 2 / 10.0)
350 GH = nx.strong_product(G, H)
351
352 for (u_G, u_H) in GH.nodes():
353 for (v_G, v_H) in GH.nodes():
354 if (
355 (u_G == v_G and H.has_edge(u_H, v_H))
356 or (u_H == v_H and G.has_edge(u_G, v_G))
357 or (G.has_edge(u_G, v_G) and H.has_edge(u_H, v_H))
358 ):
359 assert GH.has_edge((u_G, u_H), (v_G, v_H))
360 else:
361 assert not GH.has_edge((u_G, u_H), (v_G, v_H))
362
363
364 def test_graph_power_raises():
365 with pytest.raises(nx.NetworkXNotImplemented):
366 nx.power(nx.MultiDiGraph(), 2)
367
368
369 def test_graph_power():
370 # wikipedia example for graph power
371 G = nx.cycle_graph(7)
372 G.add_edge(6, 7)
373 G.add_edge(7, 8)
374 G.add_edge(8, 9)
375 G.add_edge(9, 2)
376 H = nx.power(G, 2)
377
378 assert_edges_equal(
379 list(H.edges()),
380 [
381 (0, 1),
382 (0, 2),
383 (0, 5),
384 (0, 6),
385 (0, 7),
386 (1, 9),
387 (1, 2),
388 (1, 3),
389 (1, 6),
390 (2, 3),
391 (2, 4),
392 (2, 8),
393 (2, 9),
394 (3, 4),
395 (3, 5),
396 (3, 9),
397 (4, 5),
398 (4, 6),
399 (5, 6),
400 (5, 7),
401 (6, 7),
402 (6, 8),
403 (7, 8),
404 (7, 9),
405 (8, 9),
406 ],
407 )
408
409
410 def test_graph_power_negative():
411 with pytest.raises(ValueError):
412 nx.power(nx.Graph(), -1)
413
414
415 def test_rooted_product_raises():
416 with pytest.raises(nx.NetworkXError):
417 nx.rooted_product(nx.Graph(), nx.path_graph(2), 10)
418
419
420 def test_rooted_product():
421 G = nx.cycle_graph(5)
422 H = nx.Graph()
423 H.add_edges_from([("a", "b"), ("b", "c"), ("b", "d")])
424 R = nx.rooted_product(G, H, "a")
425 assert len(R) == len(G) * len(H)
426 assert R.size() == G.size() + len(G) * H.size()