Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_simple_paths.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 import random | |
2 | |
3 import pytest | |
4 | |
5 import networkx as nx | |
6 from networkx import convert_node_labels_to_integers as cnlti | |
7 from networkx.algorithms.simple_paths import _bidirectional_dijkstra | |
8 from networkx.algorithms.simple_paths import _bidirectional_shortest_path | |
9 from networkx.utils import arbitrary_element | |
10 from networkx.utils import pairwise | |
11 | |
12 | |
13 class TestIsSimplePath: | |
14 """Unit tests for the | |
15 :func:`networkx.algorithms.simple_paths.is_simple_path` function. | |
16 | |
17 """ | |
18 | |
19 def test_empty_list(self): | |
20 """Tests that the empty list is not a valid path, since there | |
21 should be a one-to-one correspondence between paths as lists of | |
22 nodes and paths as lists of edges. | |
23 | |
24 """ | |
25 G = nx.trivial_graph() | |
26 assert not nx.is_simple_path(G, []) | |
27 | |
28 def test_trivial_path(self): | |
29 """Tests that the trivial path, a path of length one, is | |
30 considered a simple path in a graph. | |
31 | |
32 """ | |
33 G = nx.trivial_graph() | |
34 assert nx.is_simple_path(G, [0]) | |
35 | |
36 def test_trivial_nonpath(self): | |
37 """Tests that a list whose sole element is an object not in the | |
38 graph is not considered a simple path. | |
39 | |
40 """ | |
41 G = nx.trivial_graph() | |
42 assert not nx.is_simple_path(G, ["not a node"]) | |
43 | |
44 def test_simple_path(self): | |
45 G = nx.path_graph(2) | |
46 assert nx.is_simple_path(G, [0, 1]) | |
47 | |
48 def test_non_simple_path(self): | |
49 G = nx.path_graph(2) | |
50 assert not nx.is_simple_path(G, [0, 1, 0]) | |
51 | |
52 def test_cycle(self): | |
53 G = nx.cycle_graph(3) | |
54 assert not nx.is_simple_path(G, [0, 1, 2, 0]) | |
55 | |
56 def test_missing_node(self): | |
57 G = nx.path_graph(2) | |
58 assert not nx.is_simple_path(G, [0, 2]) | |
59 | |
60 def test_directed_path(self): | |
61 G = nx.DiGraph([(0, 1), (1, 2)]) | |
62 assert nx.is_simple_path(G, [0, 1, 2]) | |
63 | |
64 def test_directed_non_path(self): | |
65 G = nx.DiGraph([(0, 1), (1, 2)]) | |
66 assert not nx.is_simple_path(G, [2, 1, 0]) | |
67 | |
68 def test_directed_cycle(self): | |
69 G = nx.DiGraph([(0, 1), (1, 2), (2, 0)]) | |
70 assert not nx.is_simple_path(G, [0, 1, 2, 0]) | |
71 | |
72 def test_multigraph(self): | |
73 G = nx.MultiGraph([(0, 1), (0, 1)]) | |
74 assert nx.is_simple_path(G, [0, 1]) | |
75 | |
76 def test_multidigraph(self): | |
77 G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 0), (1, 0)]) | |
78 assert nx.is_simple_path(G, [0, 1]) | |
79 | |
80 | |
81 # Tests for all_simple_paths | |
82 def test_all_simple_paths(): | |
83 G = nx.path_graph(4) | |
84 paths = nx.all_simple_paths(G, 0, 3) | |
85 assert {tuple(p) for p in paths} == {(0, 1, 2, 3)} | |
86 | |
87 | |
88 def test_all_simple_paths_with_two_targets_emits_two_paths(): | |
89 G = nx.path_graph(4) | |
90 G.add_edge(2, 4) | |
91 paths = nx.all_simple_paths(G, 0, [3, 4]) | |
92 assert {tuple(p) for p in paths} == {(0, 1, 2, 3), (0, 1, 2, 4)} | |
93 | |
94 | |
95 def test_digraph_all_simple_paths_with_two_targets_emits_two_paths(): | |
96 G = nx.path_graph(4, create_using=nx.DiGraph()) | |
97 G.add_edge(2, 4) | |
98 paths = nx.all_simple_paths(G, 0, [3, 4]) | |
99 assert {tuple(p) for p in paths} == {(0, 1, 2, 3), (0, 1, 2, 4)} | |
100 | |
101 | |
102 def test_all_simple_paths_with_two_targets_cutoff(): | |
103 G = nx.path_graph(4) | |
104 G.add_edge(2, 4) | |
105 paths = nx.all_simple_paths(G, 0, [3, 4], cutoff=3) | |
106 assert {tuple(p) for p in paths} == {(0, 1, 2, 3), (0, 1, 2, 4)} | |
107 | |
108 | |
109 def test_digraph_all_simple_paths_with_two_targets_cutoff(): | |
110 G = nx.path_graph(4, create_using=nx.DiGraph()) | |
111 G.add_edge(2, 4) | |
112 paths = nx.all_simple_paths(G, 0, [3, 4], cutoff=3) | |
113 assert {tuple(p) for p in paths} == {(0, 1, 2, 3), (0, 1, 2, 4)} | |
114 | |
115 | |
116 def test_all_simple_paths_with_two_targets_in_line_emits_two_paths(): | |
117 G = nx.path_graph(4) | |
118 paths = nx.all_simple_paths(G, 0, [2, 3]) | |
119 assert {tuple(p) for p in paths} == {(0, 1, 2), (0, 1, 2, 3)} | |
120 | |
121 | |
122 def test_all_simple_paths_ignores_cycle(): | |
123 G = nx.cycle_graph(3, create_using=nx.DiGraph()) | |
124 G.add_edge(1, 3) | |
125 paths = nx.all_simple_paths(G, 0, 3) | |
126 assert {tuple(p) for p in paths} == {(0, 1, 3)} | |
127 | |
128 | |
129 def test_all_simple_paths_with_two_targets_inside_cycle_emits_two_paths(): | |
130 G = nx.cycle_graph(3, create_using=nx.DiGraph()) | |
131 G.add_edge(1, 3) | |
132 paths = nx.all_simple_paths(G, 0, [2, 3]) | |
133 assert {tuple(p) for p in paths} == {(0, 1, 2), (0, 1, 3)} | |
134 | |
135 | |
136 def test_all_simple_paths_source_target(): | |
137 G = nx.path_graph(4) | |
138 paths = nx.all_simple_paths(G, 1, 1) | |
139 assert list(paths) == [] | |
140 | |
141 | |
142 def test_all_simple_paths_cutoff(): | |
143 G = nx.complete_graph(4) | |
144 paths = nx.all_simple_paths(G, 0, 1, cutoff=1) | |
145 assert {tuple(p) for p in paths} == {(0, 1)} | |
146 paths = nx.all_simple_paths(G, 0, 1, cutoff=2) | |
147 assert {tuple(p) for p in paths} == {(0, 1), (0, 2, 1), (0, 3, 1)} | |
148 | |
149 | |
150 def test_all_simple_paths_on_non_trivial_graph(): | |
151 """ you may need to draw this graph to make sure it is reasonable """ | |
152 G = nx.path_graph(5, create_using=nx.DiGraph()) | |
153 G.add_edges_from([(0, 5), (1, 5), (1, 3), (5, 4), (4, 2), (4, 3)]) | |
154 paths = nx.all_simple_paths(G, 1, [2, 3]) | |
155 assert {tuple(p) for p in paths} == { | |
156 (1, 2), | |
157 (1, 3, 4, 2), | |
158 (1, 5, 4, 2), | |
159 (1, 3), | |
160 (1, 2, 3), | |
161 (1, 5, 4, 3), | |
162 (1, 5, 4, 2, 3), | |
163 } | |
164 paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=3) | |
165 assert {tuple(p) for p in paths} == { | |
166 (1, 2), | |
167 (1, 3, 4, 2), | |
168 (1, 5, 4, 2), | |
169 (1, 3), | |
170 (1, 2, 3), | |
171 (1, 5, 4, 3), | |
172 } | |
173 paths = nx.all_simple_paths(G, 1, [2, 3], cutoff=2) | |
174 assert {tuple(p) for p in paths} == {(1, 2), (1, 3), (1, 2, 3)} | |
175 | |
176 | |
177 def test_all_simple_paths_multigraph(): | |
178 G = nx.MultiGraph([(1, 2), (1, 2)]) | |
179 paths = nx.all_simple_paths(G, 1, 1) | |
180 assert list(paths) == [] | |
181 nx.add_path(G, [3, 1, 10, 2]) | |
182 paths = list(nx.all_simple_paths(G, 1, 2)) | |
183 assert len(paths) == 3 | |
184 assert {tuple(p) for p in paths} == {(1, 2), (1, 2), (1, 10, 2)} | |
185 | |
186 | |
187 def test_all_simple_paths_multigraph_with_cutoff(): | |
188 G = nx.MultiGraph([(1, 2), (1, 2), (1, 10), (10, 2)]) | |
189 paths = list(nx.all_simple_paths(G, 1, 2, cutoff=1)) | |
190 assert len(paths) == 2 | |
191 assert {tuple(p) for p in paths} == {(1, 2), (1, 2)} | |
192 | |
193 | |
194 def test_all_simple_paths_directed(): | |
195 G = nx.DiGraph() | |
196 nx.add_path(G, [1, 2, 3]) | |
197 nx.add_path(G, [3, 2, 1]) | |
198 paths = nx.all_simple_paths(G, 1, 3) | |
199 assert {tuple(p) for p in paths} == {(1, 2, 3)} | |
200 | |
201 | |
202 def test_all_simple_paths_empty(): | |
203 G = nx.path_graph(4) | |
204 paths = nx.all_simple_paths(G, 0, 3, cutoff=2) | |
205 assert list(paths) == [] | |
206 | |
207 | |
208 def test_all_simple_paths_corner_cases(): | |
209 assert list(nx.all_simple_paths(nx.empty_graph(2), 0, 0)) == [] | |
210 assert list(nx.all_simple_paths(nx.empty_graph(2), 0, 1)) == [] | |
211 assert list(nx.all_simple_paths(nx.path_graph(9), 0, 8, 0)) == [] | |
212 | |
213 | |
214 def hamiltonian_path(G, source): | |
215 source = arbitrary_element(G) | |
216 neighbors = set(G[source]) - {source} | |
217 n = len(G) | |
218 for target in neighbors: | |
219 for path in nx.all_simple_paths(G, source, target): | |
220 if len(path) == n: | |
221 yield path | |
222 | |
223 | |
224 def test_hamiltonian_path(): | |
225 from itertools import permutations | |
226 | |
227 G = nx.complete_graph(4) | |
228 paths = [list(p) for p in hamiltonian_path(G, 0)] | |
229 exact = [[0] + list(p) for p in permutations([1, 2, 3], 3)] | |
230 assert sorted(paths) == sorted(exact) | |
231 | |
232 | |
233 def test_cutoff_zero(): | |
234 G = nx.complete_graph(4) | |
235 paths = nx.all_simple_paths(G, 0, 3, cutoff=0) | |
236 assert list(list(p) for p in paths) == [] | |
237 paths = nx.all_simple_paths(nx.MultiGraph(G), 0, 3, cutoff=0) | |
238 assert list(list(p) for p in paths) == [] | |
239 | |
240 | |
241 def test_source_missing(): | |
242 with pytest.raises(nx.NodeNotFound): | |
243 G = nx.Graph() | |
244 nx.add_path(G, [1, 2, 3]) | |
245 list(nx.all_simple_paths(nx.MultiGraph(G), 0, 3)) | |
246 | |
247 | |
248 def test_target_missing(): | |
249 with pytest.raises(nx.NodeNotFound): | |
250 G = nx.Graph() | |
251 nx.add_path(G, [1, 2, 3]) | |
252 list(nx.all_simple_paths(nx.MultiGraph(G), 1, 4)) | |
253 | |
254 | |
255 # Tests for all_simple_edge_paths | |
256 def test_all_simple_edge_paths(): | |
257 G = nx.path_graph(4) | |
258 paths = nx.all_simple_edge_paths(G, 0, 3) | |
259 assert {tuple(p) for p in paths} == {((0, 1), (1, 2), (2, 3))} | |
260 | |
261 | |
262 def test_all_simple_edge_paths_with_two_targets_emits_two_paths(): | |
263 G = nx.path_graph(4) | |
264 G.add_edge(2, 4) | |
265 paths = nx.all_simple_edge_paths(G, 0, [3, 4]) | |
266 assert {tuple(p) for p in paths} == { | |
267 ((0, 1), (1, 2), (2, 3)), | |
268 ((0, 1), (1, 2), (2, 4)), | |
269 } | |
270 | |
271 | |
272 def test_digraph_all_simple_edge_paths_with_two_targets_emits_two_paths(): | |
273 G = nx.path_graph(4, create_using=nx.DiGraph()) | |
274 G.add_edge(2, 4) | |
275 paths = nx.all_simple_edge_paths(G, 0, [3, 4]) | |
276 assert {tuple(p) for p in paths} == { | |
277 ((0, 1), (1, 2), (2, 3)), | |
278 ((0, 1), (1, 2), (2, 4)), | |
279 } | |
280 | |
281 | |
282 def test_all_simple_edge_paths_with_two_targets_cutoff(): | |
283 G = nx.path_graph(4) | |
284 G.add_edge(2, 4) | |
285 paths = nx.all_simple_edge_paths(G, 0, [3, 4], cutoff=3) | |
286 assert {tuple(p) for p in paths} == { | |
287 ((0, 1), (1, 2), (2, 3)), | |
288 ((0, 1), (1, 2), (2, 4)), | |
289 } | |
290 | |
291 | |
292 def test_digraph_all_simple_edge_paths_with_two_targets_cutoff(): | |
293 G = nx.path_graph(4, create_using=nx.DiGraph()) | |
294 G.add_edge(2, 4) | |
295 paths = nx.all_simple_edge_paths(G, 0, [3, 4], cutoff=3) | |
296 assert {tuple(p) for p in paths} == { | |
297 ((0, 1), (1, 2), (2, 3)), | |
298 ((0, 1), (1, 2), (2, 4)), | |
299 } | |
300 | |
301 | |
302 def test_all_simple_edge_paths_with_two_targets_in_line_emits_two_paths(): | |
303 G = nx.path_graph(4) | |
304 paths = nx.all_simple_edge_paths(G, 0, [2, 3]) | |
305 assert {tuple(p) for p in paths} == {((0, 1), (1, 2)), ((0, 1), (1, 2), (2, 3))} | |
306 | |
307 | |
308 def test_all_simple_edge_paths_ignores_cycle(): | |
309 G = nx.cycle_graph(3, create_using=nx.DiGraph()) | |
310 G.add_edge(1, 3) | |
311 paths = nx.all_simple_edge_paths(G, 0, 3) | |
312 assert {tuple(p) for p in paths} == {((0, 1), (1, 3))} | |
313 | |
314 | |
315 def test_all_simple_edge_paths_with_two_targets_inside_cycle_emits_two_paths(): | |
316 G = nx.cycle_graph(3, create_using=nx.DiGraph()) | |
317 G.add_edge(1, 3) | |
318 paths = nx.all_simple_edge_paths(G, 0, [2, 3]) | |
319 assert {tuple(p) for p in paths} == {((0, 1), (1, 2)), ((0, 1), (1, 3))} | |
320 | |
321 | |
322 def test_all_simple_edge_paths_source_target(): | |
323 G = nx.path_graph(4) | |
324 paths = nx.all_simple_edge_paths(G, 1, 1) | |
325 assert list(paths) == [] | |
326 | |
327 | |
328 def test_all_simple_edge_paths_cutoff(): | |
329 G = nx.complete_graph(4) | |
330 paths = nx.all_simple_edge_paths(G, 0, 1, cutoff=1) | |
331 assert {tuple(p) for p in paths} == {((0, 1),)} | |
332 paths = nx.all_simple_edge_paths(G, 0, 1, cutoff=2) | |
333 assert {tuple(p) for p in paths} == {((0, 1),), ((0, 2), (2, 1)), ((0, 3), (3, 1))} | |
334 | |
335 | |
336 def test_all_simple_edge_paths_on_non_trivial_graph(): | |
337 """ you may need to draw this graph to make sure it is reasonable """ | |
338 G = nx.path_graph(5, create_using=nx.DiGraph()) | |
339 G.add_edges_from([(0, 5), (1, 5), (1, 3), (5, 4), (4, 2), (4, 3)]) | |
340 paths = nx.all_simple_edge_paths(G, 1, [2, 3]) | |
341 assert {tuple(p) for p in paths} == { | |
342 ((1, 2),), | |
343 ((1, 3), (3, 4), (4, 2)), | |
344 ((1, 5), (5, 4), (4, 2)), | |
345 ((1, 3),), | |
346 ((1, 2), (2, 3)), | |
347 ((1, 5), (5, 4), (4, 3)), | |
348 ((1, 5), (5, 4), (4, 2), (2, 3)), | |
349 } | |
350 paths = nx.all_simple_edge_paths(G, 1, [2, 3], cutoff=3) | |
351 assert {tuple(p) for p in paths} == { | |
352 ((1, 2),), | |
353 ((1, 3), (3, 4), (4, 2)), | |
354 ((1, 5), (5, 4), (4, 2)), | |
355 ((1, 3),), | |
356 ((1, 2), (2, 3)), | |
357 ((1, 5), (5, 4), (4, 3)), | |
358 } | |
359 paths = nx.all_simple_edge_paths(G, 1, [2, 3], cutoff=2) | |
360 assert {tuple(p) for p in paths} == {((1, 2),), ((1, 3),), ((1, 2), (2, 3))} | |
361 | |
362 | |
363 def test_all_simple_edge_paths_multigraph(): | |
364 G = nx.MultiGraph([(1, 2), (1, 2)]) | |
365 paths = nx.all_simple_edge_paths(G, 1, 1) | |
366 assert list(paths) == [] | |
367 nx.add_path(G, [3, 1, 10, 2]) | |
368 paths = list(nx.all_simple_edge_paths(G, 1, 2)) | |
369 assert len(paths) == 3 | |
370 assert {tuple(p) for p in paths} == { | |
371 ((1, 2, 0),), | |
372 ((1, 2, 1),), | |
373 ((1, 10, 0), (10, 2, 0)), | |
374 } | |
375 | |
376 | |
377 def test_all_simple_edge_paths_multigraph_with_cutoff(): | |
378 G = nx.MultiGraph([(1, 2), (1, 2), (1, 10), (10, 2)]) | |
379 paths = list(nx.all_simple_edge_paths(G, 1, 2, cutoff=1)) | |
380 assert len(paths) == 2 | |
381 assert {tuple(p) for p in paths} == {((1, 2, 0),), ((1, 2, 1),)} | |
382 | |
383 | |
384 def test_all_simple_edge_paths_directed(): | |
385 G = nx.DiGraph() | |
386 nx.add_path(G, [1, 2, 3]) | |
387 nx.add_path(G, [3, 2, 1]) | |
388 paths = nx.all_simple_edge_paths(G, 1, 3) | |
389 assert {tuple(p) for p in paths} == {((1, 2), (2, 3))} | |
390 | |
391 | |
392 def test_all_simple_edge_paths_empty(): | |
393 G = nx.path_graph(4) | |
394 paths = nx.all_simple_edge_paths(G, 0, 3, cutoff=2) | |
395 assert list(paths) == [] | |
396 | |
397 | |
398 def test_all_simple_edge_paths_corner_cases(): | |
399 assert list(nx.all_simple_edge_paths(nx.empty_graph(2), 0, 0)) == [] | |
400 assert list(nx.all_simple_edge_paths(nx.empty_graph(2), 0, 1)) == [] | |
401 assert list(nx.all_simple_edge_paths(nx.path_graph(9), 0, 8, 0)) == [] | |
402 | |
403 | |
404 def hamiltonian_edge_path(G, source): | |
405 source = arbitrary_element(G) | |
406 neighbors = set(G[source]) - {source} | |
407 n = len(G) | |
408 for target in neighbors: | |
409 for path in nx.all_simple_edge_paths(G, source, target): | |
410 if len(path) == n - 1: | |
411 yield path | |
412 | |
413 | |
414 def test_hamiltonian__edge_path(): | |
415 from itertools import permutations | |
416 | |
417 G = nx.complete_graph(4) | |
418 paths = hamiltonian_edge_path(G, 0) | |
419 exact = [list(pairwise([0] + list(p))) for p in permutations([1, 2, 3], 3)] | |
420 assert sorted(exact) == [p for p in sorted(paths)] | |
421 | |
422 | |
423 def test_edge_cutoff_zero(): | |
424 G = nx.complete_graph(4) | |
425 paths = nx.all_simple_edge_paths(G, 0, 3, cutoff=0) | |
426 assert list(list(p) for p in paths) == [] | |
427 paths = nx.all_simple_edge_paths(nx.MultiGraph(G), 0, 3, cutoff=0) | |
428 assert list(list(p) for p in paths) == [] | |
429 | |
430 | |
431 def test_edge_source_missing(): | |
432 with pytest.raises(nx.NodeNotFound): | |
433 G = nx.Graph() | |
434 nx.add_path(G, [1, 2, 3]) | |
435 list(nx.all_simple_edge_paths(nx.MultiGraph(G), 0, 3)) | |
436 | |
437 | |
438 def test_edge_target_missing(): | |
439 with pytest.raises(nx.NodeNotFound): | |
440 G = nx.Graph() | |
441 nx.add_path(G, [1, 2, 3]) | |
442 list(nx.all_simple_edge_paths(nx.MultiGraph(G), 1, 4)) | |
443 | |
444 | |
445 # Tests for shortest_simple_paths | |
446 def test_shortest_simple_paths(): | |
447 G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted") | |
448 paths = nx.shortest_simple_paths(G, 1, 12) | |
449 assert next(paths) == [1, 2, 3, 4, 8, 12] | |
450 assert next(paths) == [1, 5, 6, 7, 8, 12] | |
451 assert [len(path) for path in nx.shortest_simple_paths(G, 1, 12)] == sorted( | |
452 [len(path) for path in nx.all_simple_paths(G, 1, 12)] | |
453 ) | |
454 | |
455 | |
456 def test_shortest_simple_paths_directed(): | |
457 G = nx.cycle_graph(7, create_using=nx.DiGraph()) | |
458 paths = nx.shortest_simple_paths(G, 0, 3) | |
459 assert [path for path in paths] == [[0, 1, 2, 3]] | |
460 | |
461 | |
462 def test_shortest_simple_paths_directed_with_weight_fucntion(): | |
463 def cost(u, v, x): | |
464 return 1 | |
465 | |
466 G = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted") | |
467 paths = nx.shortest_simple_paths(G, 1, 12) | |
468 assert next(paths) == [1, 2, 3, 4, 8, 12] | |
469 assert next(paths) == [1, 5, 6, 7, 8, 12] | |
470 assert [ | |
471 len(path) for path in nx.shortest_simple_paths(G, 1, 12, weight=cost) | |
472 ] == sorted([len(path) for path in nx.all_simple_paths(G, 1, 12)]) | |
473 | |
474 | |
475 def test_shortest_simple_paths_with_weight_fucntion(): | |
476 def cost(u, v, x): | |
477 return 1 | |
478 | |
479 G = nx.cycle_graph(7, create_using=nx.DiGraph()) | |
480 paths = nx.shortest_simple_paths(G, 0, 3, weight=cost) | |
481 assert [path for path in paths] == [[0, 1, 2, 3]] | |
482 | |
483 | |
484 def test_Greg_Bernstein(): | |
485 g1 = nx.Graph() | |
486 g1.add_nodes_from(["N0", "N1", "N2", "N3", "N4"]) | |
487 g1.add_edge("N4", "N1", weight=10.0, capacity=50, name="L5") | |
488 g1.add_edge("N4", "N0", weight=7.0, capacity=40, name="L4") | |
489 g1.add_edge("N0", "N1", weight=10.0, capacity=45, name="L1") | |
490 g1.add_edge("N3", "N0", weight=10.0, capacity=50, name="L0") | |
491 g1.add_edge("N2", "N3", weight=12.0, capacity=30, name="L2") | |
492 g1.add_edge("N1", "N2", weight=15.0, capacity=42, name="L3") | |
493 solution = [["N1", "N0", "N3"], ["N1", "N2", "N3"], ["N1", "N4", "N0", "N3"]] | |
494 result = list(nx.shortest_simple_paths(g1, "N1", "N3", weight="weight")) | |
495 assert result == solution | |
496 | |
497 | |
498 def test_weighted_shortest_simple_path(): | |
499 def cost_func(path): | |
500 return sum(G.adj[u][v]["weight"] for (u, v) in zip(path, path[1:])) | |
501 | |
502 G = nx.complete_graph(5) | |
503 weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()} | |
504 nx.set_edge_attributes(G, weight, "weight") | |
505 cost = 0 | |
506 for path in nx.shortest_simple_paths(G, 0, 3, weight="weight"): | |
507 this_cost = cost_func(path) | |
508 assert cost <= this_cost | |
509 cost = this_cost | |
510 | |
511 | |
512 def test_directed_weighted_shortest_simple_path(): | |
513 def cost_func(path): | |
514 return sum(G.adj[u][v]["weight"] for (u, v) in zip(path, path[1:])) | |
515 | |
516 G = nx.complete_graph(5) | |
517 G = G.to_directed() | |
518 weight = {(u, v): random.randint(1, 100) for (u, v) in G.edges()} | |
519 nx.set_edge_attributes(G, weight, "weight") | |
520 cost = 0 | |
521 for path in nx.shortest_simple_paths(G, 0, 3, weight="weight"): | |
522 this_cost = cost_func(path) | |
523 assert cost <= this_cost | |
524 cost = this_cost | |
525 | |
526 | |
527 def test_weighted_shortest_simple_path_issue2427(): | |
528 G = nx.Graph() | |
529 G.add_edge("IN", "OUT", weight=2) | |
530 G.add_edge("IN", "A", weight=1) | |
531 G.add_edge("IN", "B", weight=2) | |
532 G.add_edge("B", "OUT", weight=2) | |
533 assert list(nx.shortest_simple_paths(G, "IN", "OUT", weight="weight")) == [ | |
534 ["IN", "OUT"], | |
535 ["IN", "B", "OUT"], | |
536 ] | |
537 G = nx.Graph() | |
538 G.add_edge("IN", "OUT", weight=10) | |
539 G.add_edge("IN", "A", weight=1) | |
540 G.add_edge("IN", "B", weight=1) | |
541 G.add_edge("B", "OUT", weight=1) | |
542 assert list(nx.shortest_simple_paths(G, "IN", "OUT", weight="weight")) == [ | |
543 ["IN", "B", "OUT"], | |
544 ["IN", "OUT"], | |
545 ] | |
546 | |
547 | |
548 def test_directed_weighted_shortest_simple_path_issue2427(): | |
549 G = nx.DiGraph() | |
550 G.add_edge("IN", "OUT", weight=2) | |
551 G.add_edge("IN", "A", weight=1) | |
552 G.add_edge("IN", "B", weight=2) | |
553 G.add_edge("B", "OUT", weight=2) | |
554 assert list(nx.shortest_simple_paths(G, "IN", "OUT", weight="weight")) == [ | |
555 ["IN", "OUT"], | |
556 ["IN", "B", "OUT"], | |
557 ] | |
558 G = nx.DiGraph() | |
559 G.add_edge("IN", "OUT", weight=10) | |
560 G.add_edge("IN", "A", weight=1) | |
561 G.add_edge("IN", "B", weight=1) | |
562 G.add_edge("B", "OUT", weight=1) | |
563 assert list(nx.shortest_simple_paths(G, "IN", "OUT", weight="weight")) == [ | |
564 ["IN", "B", "OUT"], | |
565 ["IN", "OUT"], | |
566 ] | |
567 | |
568 | |
569 def test_weight_name(): | |
570 G = nx.cycle_graph(7) | |
571 nx.set_edge_attributes(G, 1, "weight") | |
572 nx.set_edge_attributes(G, 1, "foo") | |
573 G.adj[1][2]["foo"] = 7 | |
574 paths = list(nx.shortest_simple_paths(G, 0, 3, weight="foo")) | |
575 solution = [[0, 6, 5, 4, 3], [0, 1, 2, 3]] | |
576 assert paths == solution | |
577 | |
578 | |
579 def test_ssp_source_missing(): | |
580 with pytest.raises(nx.NodeNotFound): | |
581 G = nx.Graph() | |
582 nx.add_path(G, [1, 2, 3]) | |
583 list(nx.shortest_simple_paths(G, 0, 3)) | |
584 | |
585 | |
586 def test_ssp_target_missing(): | |
587 with pytest.raises(nx.NodeNotFound): | |
588 G = nx.Graph() | |
589 nx.add_path(G, [1, 2, 3]) | |
590 list(nx.shortest_simple_paths(G, 1, 4)) | |
591 | |
592 | |
593 def test_ssp_multigraph(): | |
594 with pytest.raises(nx.NetworkXNotImplemented): | |
595 G = nx.MultiGraph() | |
596 nx.add_path(G, [1, 2, 3]) | |
597 list(nx.shortest_simple_paths(G, 1, 4)) | |
598 | |
599 | |
600 def test_ssp_source_missing2(): | |
601 with pytest.raises(nx.NetworkXNoPath): | |
602 G = nx.Graph() | |
603 nx.add_path(G, [0, 1, 2]) | |
604 nx.add_path(G, [3, 4, 5]) | |
605 list(nx.shortest_simple_paths(G, 0, 3)) | |
606 | |
607 | |
608 def test_bidirectional_shortest_path_restricted_cycle(): | |
609 cycle = nx.cycle_graph(7) | |
610 length, path = _bidirectional_shortest_path(cycle, 0, 3) | |
611 assert path == [0, 1, 2, 3] | |
612 length, path = _bidirectional_shortest_path(cycle, 0, 3, ignore_nodes=[1]) | |
613 assert path == [0, 6, 5, 4, 3] | |
614 | |
615 | |
616 def test_bidirectional_shortest_path_restricted_wheel(): | |
617 wheel = nx.wheel_graph(6) | |
618 length, path = _bidirectional_shortest_path(wheel, 1, 3) | |
619 assert path in [[1, 0, 3], [1, 2, 3]] | |
620 length, path = _bidirectional_shortest_path(wheel, 1, 3, ignore_nodes=[0]) | |
621 assert path == [1, 2, 3] | |
622 length, path = _bidirectional_shortest_path(wheel, 1, 3, ignore_nodes=[0, 2]) | |
623 assert path == [1, 5, 4, 3] | |
624 length, path = _bidirectional_shortest_path( | |
625 wheel, 1, 3, ignore_edges=[(1, 0), (5, 0), (2, 3)] | |
626 ) | |
627 assert path in [[1, 2, 0, 3], [1, 5, 4, 3]] | |
628 | |
629 | |
630 def test_bidirectional_shortest_path_restricted_directed_cycle(): | |
631 directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph()) | |
632 length, path = _bidirectional_shortest_path(directed_cycle, 0, 3) | |
633 assert path == [0, 1, 2, 3] | |
634 pytest.raises( | |
635 nx.NetworkXNoPath, | |
636 _bidirectional_shortest_path, | |
637 directed_cycle, | |
638 0, | |
639 3, | |
640 ignore_nodes=[1], | |
641 ) | |
642 length, path = _bidirectional_shortest_path( | |
643 directed_cycle, 0, 3, ignore_edges=[(2, 1)] | |
644 ) | |
645 assert path == [0, 1, 2, 3] | |
646 pytest.raises( | |
647 nx.NetworkXNoPath, | |
648 _bidirectional_shortest_path, | |
649 directed_cycle, | |
650 0, | |
651 3, | |
652 ignore_edges=[(1, 2)], | |
653 ) | |
654 | |
655 | |
656 def test_bidirectional_shortest_path_ignore(): | |
657 G = nx.Graph() | |
658 nx.add_path(G, [1, 2]) | |
659 nx.add_path(G, [1, 3]) | |
660 nx.add_path(G, [1, 4]) | |
661 pytest.raises( | |
662 nx.NetworkXNoPath, _bidirectional_shortest_path, G, 1, 2, ignore_nodes=[1] | |
663 ) | |
664 pytest.raises( | |
665 nx.NetworkXNoPath, _bidirectional_shortest_path, G, 1, 2, ignore_nodes=[2] | |
666 ) | |
667 G = nx.Graph() | |
668 nx.add_path(G, [1, 3]) | |
669 nx.add_path(G, [1, 4]) | |
670 nx.add_path(G, [3, 2]) | |
671 pytest.raises( | |
672 nx.NetworkXNoPath, _bidirectional_shortest_path, G, 1, 2, ignore_nodes=[1, 2] | |
673 ) | |
674 | |
675 | |
676 def validate_path(G, s, t, soln_len, path): | |
677 assert path[0] == s | |
678 assert path[-1] == t | |
679 assert soln_len == sum( | |
680 G[u][v].get("weight", 1) for u, v in zip(path[:-1], path[1:]) | |
681 ) | |
682 | |
683 | |
684 def validate_length_path(G, s, t, soln_len, length, path): | |
685 assert soln_len == length | |
686 validate_path(G, s, t, length, path) | |
687 | |
688 | |
689 def test_bidirectional_dijksta_restricted(): | |
690 XG = nx.DiGraph() | |
691 XG.add_weighted_edges_from( | |
692 [ | |
693 ("s", "u", 10), | |
694 ("s", "x", 5), | |
695 ("u", "v", 1), | |
696 ("u", "x", 2), | |
697 ("v", "y", 1), | |
698 ("x", "u", 3), | |
699 ("x", "v", 5), | |
700 ("x", "y", 2), | |
701 ("y", "s", 7), | |
702 ("y", "v", 6), | |
703 ] | |
704 ) | |
705 | |
706 XG3 = nx.Graph() | |
707 XG3.add_weighted_edges_from( | |
708 [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]] | |
709 ) | |
710 validate_length_path(XG, "s", "v", 9, *_bidirectional_dijkstra(XG, "s", "v")) | |
711 validate_length_path( | |
712 XG, "s", "v", 10, *_bidirectional_dijkstra(XG, "s", "v", ignore_nodes=["u"]) | |
713 ) | |
714 validate_length_path( | |
715 XG, | |
716 "s", | |
717 "v", | |
718 11, | |
719 *_bidirectional_dijkstra(XG, "s", "v", ignore_edges=[("s", "x")]) | |
720 ) | |
721 pytest.raises( | |
722 nx.NetworkXNoPath, | |
723 _bidirectional_dijkstra, | |
724 XG, | |
725 "s", | |
726 "v", | |
727 ignore_nodes=["u"], | |
728 ignore_edges=[("s", "x")], | |
729 ) | |
730 validate_length_path(XG3, 0, 3, 15, *_bidirectional_dijkstra(XG3, 0, 3)) | |
731 validate_length_path( | |
732 XG3, 0, 3, 16, *_bidirectional_dijkstra(XG3, 0, 3, ignore_nodes=[1]) | |
733 ) | |
734 validate_length_path( | |
735 XG3, 0, 3, 16, *_bidirectional_dijkstra(XG3, 0, 3, ignore_edges=[(2, 3)]) | |
736 ) | |
737 pytest.raises( | |
738 nx.NetworkXNoPath, | |
739 _bidirectional_dijkstra, | |
740 XG3, | |
741 0, | |
742 3, | |
743 ignore_nodes=[1], | |
744 ignore_edges=[(5, 4)], | |
745 ) | |
746 | |
747 | |
748 def test_bidirectional_dijkstra_no_path(): | |
749 with pytest.raises(nx.NetworkXNoPath): | |
750 G = nx.Graph() | |
751 nx.add_path(G, [1, 2, 3]) | |
752 nx.add_path(G, [4, 5, 6]) | |
753 _bidirectional_dijkstra(G, 1, 6) | |
754 | |
755 | |
756 def test_bidirectional_dijkstra_ignore(): | |
757 G = nx.Graph() | |
758 nx.add_path(G, [1, 2, 10]) | |
759 nx.add_path(G, [1, 3, 10]) | |
760 pytest.raises(nx.NetworkXNoPath, _bidirectional_dijkstra, G, 1, 2, ignore_nodes=[1]) | |
761 pytest.raises(nx.NetworkXNoPath, _bidirectional_dijkstra, G, 1, 2, ignore_nodes=[2]) | |
762 pytest.raises( | |
763 nx.NetworkXNoPath, _bidirectional_dijkstra, G, 1, 2, ignore_nodes=[1, 2] | |
764 ) |