Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_weighted.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
3 import networkx as nx
4 from networkx.utils import pairwise
5
6
7 def validate_path(G, s, t, soln_len, path, weight="weight"):
8 assert path[0] == s
9 assert path[-1] == t
10
11 if callable(weight):
12 weight_f = weight
13 else:
14 if G.is_multigraph():
15
16 def weight_f(u, v, d):
17 return min(e.get(weight, 1) for e in d.values())
18
19 else:
20
21 def weight_f(u, v, d):
22 return d.get(weight, 1)
23
24 computed = sum(weight_f(u, v, G[u][v]) for u, v in pairwise(path))
25 assert soln_len == computed
26
27
28 def validate_length_path(G, s, t, soln_len, length, path, weight="weight"):
29 assert soln_len == length
30 validate_path(G, s, t, length, path, weight=weight)
31
32
33 class WeightedTestBase:
34 """Base class for test classes that test functions for computing
35 shortest paths in weighted graphs.
36
37 """
38
39 def setup(self):
40 """Creates some graphs for use in the unit tests."""
41 cnlti = nx.convert_node_labels_to_integers
42 self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
43 self.cycle = nx.cycle_graph(7)
44 self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
45 self.XG = nx.DiGraph()
46 self.XG.add_weighted_edges_from(
47 [
48 ("s", "u", 10),
49 ("s", "x", 5),
50 ("u", "v", 1),
51 ("u", "x", 2),
52 ("v", "y", 1),
53 ("x", "u", 3),
54 ("x", "v", 5),
55 ("x", "y", 2),
56 ("y", "s", 7),
57 ("y", "v", 6),
58 ]
59 )
60 self.MXG = nx.MultiDiGraph(self.XG)
61 self.MXG.add_edge("s", "u", weight=15)
62 self.XG2 = nx.DiGraph()
63 self.XG2.add_weighted_edges_from(
64 [
65 [1, 4, 1],
66 [4, 5, 1],
67 [5, 6, 1],
68 [6, 3, 1],
69 [1, 3, 50],
70 [1, 2, 100],
71 [2, 3, 100],
72 ]
73 )
74
75 self.XG3 = nx.Graph()
76 self.XG3.add_weighted_edges_from(
77 [[0, 1, 2], [1, 2, 12], [2, 3, 1], [3, 4, 5], [4, 5, 1], [5, 0, 10]]
78 )
79
80 self.XG4 = nx.Graph()
81 self.XG4.add_weighted_edges_from(
82 [
83 [0, 1, 2],
84 [1, 2, 2],
85 [2, 3, 1],
86 [3, 4, 1],
87 [4, 5, 1],
88 [5, 6, 1],
89 [6, 7, 1],
90 [7, 0, 1],
91 ]
92 )
93 self.MXG4 = nx.MultiGraph(self.XG4)
94 self.MXG4.add_edge(0, 1, weight=3)
95 self.G = nx.DiGraph() # no weights
96 self.G.add_edges_from(
97 [
98 ("s", "u"),
99 ("s", "x"),
100 ("u", "v"),
101 ("u", "x"),
102 ("v", "y"),
103 ("x", "u"),
104 ("x", "v"),
105 ("x", "y"),
106 ("y", "s"),
107 ("y", "v"),
108 ]
109 )
110
111
112 class TestWeightedPath(WeightedTestBase):
113 def test_dijkstra(self):
114 (D, P) = nx.single_source_dijkstra(self.XG, "s")
115 validate_path(self.XG, "s", "v", 9, P["v"])
116 assert D["v"] == 9
117
118 validate_path(
119 self.XG, "s", "v", 9, nx.single_source_dijkstra_path(self.XG, "s")["v"]
120 )
121 assert dict(nx.single_source_dijkstra_path_length(self.XG, "s"))["v"] == 9
122
123 validate_path(
124 self.XG, "s", "v", 9, nx.single_source_dijkstra(self.XG, "s")[1]["v"]
125 )
126 validate_path(
127 self.MXG, "s", "v", 9, nx.single_source_dijkstra_path(self.MXG, "s")["v"]
128 )
129
130 GG = self.XG.to_undirected()
131 # make sure we get lower weight
132 # to_undirected might choose either edge with weight 2 or weight 3
133 GG["u"]["x"]["weight"] = 2
134 (D, P) = nx.single_source_dijkstra(GG, "s")
135 validate_path(GG, "s", "v", 8, P["v"])
136 assert D["v"] == 8 # uses lower weight of 2 on u<->x edge
137 validate_path(GG, "s", "v", 8, nx.dijkstra_path(GG, "s", "v"))
138 assert nx.dijkstra_path_length(GG, "s", "v") == 8
139
140 validate_path(self.XG2, 1, 3, 4, nx.dijkstra_path(self.XG2, 1, 3))
141 validate_path(self.XG3, 0, 3, 15, nx.dijkstra_path(self.XG3, 0, 3))
142 assert nx.dijkstra_path_length(self.XG3, 0, 3) == 15
143 validate_path(self.XG4, 0, 2, 4, nx.dijkstra_path(self.XG4, 0, 2))
144 assert nx.dijkstra_path_length(self.XG4, 0, 2) == 4
145 validate_path(self.MXG4, 0, 2, 4, nx.dijkstra_path(self.MXG4, 0, 2))
146 validate_path(
147 self.G, "s", "v", 2, nx.single_source_dijkstra(self.G, "s", "v")[1]
148 )
149 validate_path(
150 self.G, "s", "v", 2, nx.single_source_dijkstra(self.G, "s")[1]["v"]
151 )
152
153 validate_path(self.G, "s", "v", 2, nx.dijkstra_path(self.G, "s", "v"))
154 assert nx.dijkstra_path_length(self.G, "s", "v") == 2
155
156 # NetworkXError: node s not reachable from moon
157 pytest.raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, "s", "moon")
158 pytest.raises(nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, "s", "moon")
159
160 validate_path(self.cycle, 0, 3, 3, nx.dijkstra_path(self.cycle, 0, 3))
161 validate_path(self.cycle, 0, 4, 3, nx.dijkstra_path(self.cycle, 0, 4))
162
163 assert nx.single_source_dijkstra(self.cycle, 0, 0) == (0, [0])
164
165 def test_bidirectional_dijkstra(self):
166 validate_length_path(
167 self.XG, "s", "v", 9, *nx.bidirectional_dijkstra(self.XG, "s", "v")
168 )
169 validate_length_path(
170 self.G, "s", "v", 2, *nx.bidirectional_dijkstra(self.G, "s", "v")
171 )
172 validate_length_path(
173 self.cycle, 0, 3, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 3)
174 )
175 validate_length_path(
176 self.cycle, 0, 4, 3, *nx.bidirectional_dijkstra(self.cycle, 0, 4)
177 )
178 validate_length_path(
179 self.XG3, 0, 3, 15, *nx.bidirectional_dijkstra(self.XG3, 0, 3)
180 )
181 validate_length_path(
182 self.XG4, 0, 2, 4, *nx.bidirectional_dijkstra(self.XG4, 0, 2)
183 )
184
185 # need more tests here
186 P = nx.single_source_dijkstra_path(self.XG, "s")["v"]
187 validate_path(
188 self.XG,
189 "s",
190 "v",
191 sum(self.XG[u][v]["weight"] for u, v in zip(P[:-1], P[1:])),
192 nx.dijkstra_path(self.XG, "s", "v"),
193 )
194
195 # check absent source
196 G = nx.path_graph(2)
197 pytest.raises(nx.NodeNotFound, nx.bidirectional_dijkstra, G, 3, 0)
198
199 def test_weight_functions(self):
200 def heuristic(*z):
201 return hash(z)
202
203 def getpath(pred, v, s):
204 return [v] if v == s else getpath(pred, pred[v], s) + [v]
205
206 def goldberg_radzik(g, s, t, weight="weight"):
207 pred, dist = nx.goldberg_radzik(g, s, weight=weight)
208 dist = dist[t]
209 return dist, getpath(pred, t, s)
210
211 def astar(g, s, t, weight="weight"):
212 path = nx.astar_path(g, s, t, heuristic, weight=weight)
213 dist = nx.astar_path_length(g, s, t, heuristic, weight=weight)
214 return dist, path
215
216 def vlp(G, s, t, l, F, w):
217 res = F(G, s, t, weight=w)
218 validate_length_path(G, s, t, l, *res, weight=w)
219
220 G = self.cycle
221 s = 6
222 t = 4
223 path = [6] + list(range(t + 1))
224
225 def weight(u, v, _):
226 return 1 + v ** 2
227
228 length = sum(weight(u, v, None) for u, v in pairwise(path))
229 vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
230 vlp(G, s, t, length, nx.single_source_dijkstra, weight)
231 vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
232 vlp(G, s, t, length, goldberg_radzik, weight)
233 vlp(G, s, t, length, astar, weight)
234
235 def weight(u, v, _):
236 return 2 ** (u * v)
237
238 length = sum(weight(u, v, None) for u, v in pairwise(path))
239 vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
240 vlp(G, s, t, length, nx.single_source_dijkstra, weight)
241 vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
242 vlp(G, s, t, length, goldberg_radzik, weight)
243 vlp(G, s, t, length, astar, weight)
244
245 def test_bidirectional_dijkstra_no_path(self):
246 with pytest.raises(nx.NetworkXNoPath):
247 G = nx.Graph()
248 nx.add_path(G, [1, 2, 3])
249 nx.add_path(G, [4, 5, 6])
250 path = nx.bidirectional_dijkstra(G, 1, 6)
251
252 def test_absent_source(self):
253 # the check is in _dijkstra_multisource, but this will provide
254 # regression testing against later changes to any of the "client"
255 # Dijkstra or Bellman-Ford functions
256 G = nx.path_graph(2)
257 for fn in (
258 nx.dijkstra_path,
259 nx.dijkstra_path_length,
260 nx.single_source_dijkstra_path,
261 nx.single_source_dijkstra_path_length,
262 nx.single_source_dijkstra,
263 nx.dijkstra_predecessor_and_distance,
264 ):
265 pytest.raises(nx.NodeNotFound, fn, G, 3, 0)
266
267 def test_dijkstra_predecessor1(self):
268 G = nx.path_graph(4)
269 assert nx.dijkstra_predecessor_and_distance(G, 0) == (
270 {0: [], 1: [0], 2: [1], 3: [2]},
271 {0: 0, 1: 1, 2: 2, 3: 3},
272 )
273
274 def test_dijkstra_predecessor2(self):
275 # 4-cycle
276 G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])
277 pred, dist = nx.dijkstra_predecessor_and_distance(G, (0))
278 assert pred[0] == []
279 assert pred[1] == [0]
280 assert pred[2] in [[1, 3], [3, 1]]
281 assert pred[3] == [0]
282 assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
283
284 def test_dijkstra_predecessor3(self):
285 XG = nx.DiGraph()
286 XG.add_weighted_edges_from(
287 [
288 ("s", "u", 10),
289 ("s", "x", 5),
290 ("u", "v", 1),
291 ("u", "x", 2),
292 ("v", "y", 1),
293 ("x", "u", 3),
294 ("x", "v", 5),
295 ("x", "y", 2),
296 ("y", "s", 7),
297 ("y", "v", 6),
298 ]
299 )
300 (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s")
301 assert P["v"] == ["u"]
302 assert D["v"] == 9
303 (P, D) = nx.dijkstra_predecessor_and_distance(XG, "s", cutoff=8)
304 assert "v" not in D
305
306 def test_single_source_dijkstra_path_length(self):
307 pl = nx.single_source_dijkstra_path_length
308 assert dict(pl(self.MXG4, 0))[2] == 4
309 spl = pl(self.MXG4, 0, cutoff=2)
310 assert 2 not in spl
311
312 def test_bidirectional_dijkstra_multigraph(self):
313 G = nx.MultiGraph()
314 G.add_edge("a", "b", weight=10)
315 G.add_edge("a", "b", weight=100)
316 dp = nx.bidirectional_dijkstra(G, "a", "b")
317 assert dp == (10, ["a", "b"])
318
319 def test_dijkstra_pred_distance_multigraph(self):
320 G = nx.MultiGraph()
321 G.add_edge("a", "b", key="short", foo=5, weight=100)
322 G.add_edge("a", "b", key="long", bar=1, weight=110)
323 p, d = nx.dijkstra_predecessor_and_distance(G, "a")
324 assert p == {"a": [], "b": ["a"]}
325 assert d == {"a": 0, "b": 100}
326
327 def test_negative_edge_cycle(self):
328 G = nx.cycle_graph(5, create_using=nx.DiGraph())
329 assert not nx.negative_edge_cycle(G)
330 G.add_edge(8, 9, weight=-7)
331 G.add_edge(9, 8, weight=3)
332 graph_size = len(G)
333 assert nx.negative_edge_cycle(G)
334 assert graph_size == len(G)
335 pytest.raises(ValueError, nx.single_source_dijkstra_path_length, G, 8)
336 pytest.raises(ValueError, nx.single_source_dijkstra, G, 8)
337 pytest.raises(ValueError, nx.dijkstra_predecessor_and_distance, G, 8)
338 G.add_edge(9, 10)
339 pytest.raises(ValueError, nx.bidirectional_dijkstra, G, 8, 10)
340
341 def test_weight_function(self):
342 """Tests that a callable weight is interpreted as a weight
343 function instead of an edge attribute.
344
345 """
346 # Create a triangle in which the edge from node 0 to node 2 has
347 # a large weight and the other two edges have a small weight.
348 G = nx.complete_graph(3)
349 G.adj[0][2]["weight"] = 10
350 G.adj[0][1]["weight"] = 1
351 G.adj[1][2]["weight"] = 1
352 # The weight function will take the multiplicative inverse of
353 # the weights on the edges. This way, weights that were large
354 # before now become small and vice versa.
355
356 def weight(u, v, d):
357 return 1 / d["weight"]
358
359 # The shortest path from 0 to 2 using the actual weights on the
360 # edges should be [0, 1, 2].
361 distance, path = nx.single_source_dijkstra(G, 0, 2)
362 assert distance == 2
363 assert path == [0, 1, 2]
364 # However, with the above weight function, the shortest path
365 # should be [0, 2], since that has a very small weight.
366 distance, path = nx.single_source_dijkstra(G, 0, 2, weight=weight)
367 assert distance == 1 / 10
368 assert path == [0, 2]
369
370 def test_all_pairs_dijkstra_path(self):
371 cycle = nx.cycle_graph(7)
372 p = dict(nx.all_pairs_dijkstra_path(cycle))
373 assert p[0][3] == [0, 1, 2, 3]
374
375 cycle[1][2]["weight"] = 10
376 p = dict(nx.all_pairs_dijkstra_path(cycle))
377 assert p[0][3] == [0, 6, 5, 4, 3]
378
379 def test_all_pairs_dijkstra_path_length(self):
380 cycle = nx.cycle_graph(7)
381 pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
382 assert pl[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
383
384 cycle[1][2]["weight"] = 10
385 pl = dict(nx.all_pairs_dijkstra_path_length(cycle))
386 assert pl[0] == {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
387
388 def test_all_pairs_dijkstra(self):
389 cycle = nx.cycle_graph(7)
390 out = dict(nx.all_pairs_dijkstra(cycle))
391 assert out[0][0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
392 assert out[0][1][3] == [0, 1, 2, 3]
393
394 cycle[1][2]["weight"] = 10
395 out = dict(nx.all_pairs_dijkstra(cycle))
396 assert out[0][0] == {0: 0, 1: 1, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
397 assert out[0][1][3] == [0, 6, 5, 4, 3]
398
399
400 class TestDijkstraPathLength:
401 """Unit tests for the :func:`networkx.dijkstra_path_length`
402 function.
403
404 """
405
406 def test_weight_function(self):
407 """Tests for computing the length of the shortest path using
408 Dijkstra's algorithm with a user-defined weight function.
409
410 """
411 # Create a triangle in which the edge from node 0 to node 2 has
412 # a large weight and the other two edges have a small weight.
413 G = nx.complete_graph(3)
414 G.adj[0][2]["weight"] = 10
415 G.adj[0][1]["weight"] = 1
416 G.adj[1][2]["weight"] = 1
417 # The weight function will take the multiplicative inverse of
418 # the weights on the edges. This way, weights that were large
419 # before now become small and vice versa.
420
421 def weight(u, v, d):
422 return 1 / d["weight"]
423
424 # The shortest path from 0 to 2 using the actual weights on the
425 # edges should be [0, 1, 2]. However, with the above weight
426 # function, the shortest path should be [0, 2], since that has a
427 # very small weight.
428 length = nx.dijkstra_path_length(G, 0, 2, weight=weight)
429 assert length == 1 / 10
430
431
432 class TestMultiSourceDijkstra:
433 """Unit tests for the multi-source dialect of Dijkstra's shortest
434 path algorithms.
435
436 """
437
438 def test_no_sources(self):
439 with pytest.raises(ValueError):
440 nx.multi_source_dijkstra(nx.Graph(), {})
441
442 def test_path_no_sources(self):
443 with pytest.raises(ValueError):
444 nx.multi_source_dijkstra_path(nx.Graph(), {})
445
446 def test_path_length_no_sources(self):
447 with pytest.raises(ValueError):
448 nx.multi_source_dijkstra_path_length(nx.Graph(), {})
449
450 def test_absent_source(self):
451 G = nx.path_graph(2)
452 for fn in (
453 nx.multi_source_dijkstra_path,
454 nx.multi_source_dijkstra_path_length,
455 nx.multi_source_dijkstra,
456 ):
457 pytest.raises(nx.NodeNotFound, fn, G, [3], 0)
458
459 def test_two_sources(self):
460 edges = [(0, 1, 1), (1, 2, 1), (2, 3, 10), (3, 4, 1)]
461 G = nx.Graph()
462 G.add_weighted_edges_from(edges)
463 sources = {0, 4}
464 distances, paths = nx.multi_source_dijkstra(G, sources)
465 expected_distances = {0: 0, 1: 1, 2: 2, 3: 1, 4: 0}
466 expected_paths = {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [4, 3], 4: [4]}
467 assert distances == expected_distances
468 assert paths == expected_paths
469
470 def test_simple_paths(self):
471 G = nx.path_graph(4)
472 lengths = nx.multi_source_dijkstra_path_length(G, [0])
473 assert lengths == {n: n for n in G}
474 paths = nx.multi_source_dijkstra_path(G, [0])
475 assert paths == {n: list(range(n + 1)) for n in G}
476
477
478 class TestBellmanFordAndGoldbergRadzik(WeightedTestBase):
479 def test_single_node_graph(self):
480 G = nx.DiGraph()
481 G.add_node(0)
482 assert nx.single_source_bellman_ford_path(G, 0) == {0: [0]}
483 assert nx.single_source_bellman_ford_path_length(G, 0) == {0: 0}
484 assert nx.single_source_bellman_ford(G, 0) == ({0: 0}, {0: [0]})
485 assert nx.bellman_ford_predecessor_and_distance(G, 0) == ({0: []}, {0: 0})
486 assert nx.goldberg_radzik(G, 0) == ({0: None}, {0: 0})
487
488 def test_absent_source_bellman_ford(self):
489 # the check is in _bellman_ford; this provides regression testing
490 # against later changes to "client" Bellman-Ford functions
491 G = nx.path_graph(2)
492 for fn in (
493 nx.bellman_ford_predecessor_and_distance,
494 nx.bellman_ford_path,
495 nx.bellman_ford_path_length,
496 nx.single_source_bellman_ford_path,
497 nx.single_source_bellman_ford_path_length,
498 nx.single_source_bellman_ford,
499 ):
500 pytest.raises(nx.NodeNotFound, fn, G, 3, 0)
501
502 def test_absent_source_goldberg_radzik(self):
503 with pytest.raises(nx.NodeNotFound):
504 G = nx.path_graph(2)
505 nx.goldberg_radzik(G, 3, 0)
506
507 def test_negative_weight_cycle_heuristic(self):
508 G = nx.DiGraph()
509 G.add_edge(0, 1, weight=-1)
510 G.add_edge(1, 2, weight=-1)
511 G.add_edge(2, 3, weight=-1)
512 G.add_edge(3, 0, weight=3)
513 assert not nx.negative_edge_cycle(G, heuristic=True)
514 G.add_edge(2, 0, weight=1.999)
515 assert nx.negative_edge_cycle(G, heuristic=True)
516 G.edges[2, 0]["weight"] = 2
517 assert not nx.negative_edge_cycle(G, heuristic=True)
518
519 def test_negative_weight_cycle_consistency(self):
520 import random
521
522 unif = random.uniform
523 for random_seed in range(2): # range(20):
524 random.seed(random_seed)
525 for density in [0.1, 0.9]: # .3, .7, .9]:
526 for N in [1, 10, 20]: # range(1, 60 - int(30 * density)):
527 for max_cost in [1, 90]: # [1, 10, 40, 90]:
528 G = nx.binomial_graph(N, density, seed=4, directed=True)
529 edges = ((u, v, unif(-1, max_cost)) for u, v in G.edges)
530 G.add_weighted_edges_from(edges)
531
532 no_heuristic = nx.negative_edge_cycle(G, heuristic=False)
533 with_heuristic = nx.negative_edge_cycle(G, heuristic=True)
534 assert no_heuristic == with_heuristic
535
536 def test_negative_weight_cycle(self):
537 G = nx.cycle_graph(5, create_using=nx.DiGraph())
538 G.add_edge(1, 2, weight=-7)
539 for i in range(5):
540 pytest.raises(
541 nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, i
542 )
543 pytest.raises(
544 nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, i
545 )
546 pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, i)
547 pytest.raises(
548 nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, i
549 )
550 pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, i)
551 G = nx.cycle_graph(5) # undirected Graph
552 G.add_edge(1, 2, weight=-3)
553 for i in range(5):
554 pytest.raises(
555 nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, i
556 )
557 pytest.raises(
558 nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, i
559 )
560 pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, i)
561 pytest.raises(
562 nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, i
563 )
564 pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, i)
565 G = nx.DiGraph([(1, 1, {"weight": -1})])
566 pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford_path, G, 1)
567 pytest.raises(
568 nx.NetworkXUnbounded, nx.single_source_bellman_ford_path_length, G, 1
569 )
570 pytest.raises(nx.NetworkXUnbounded, nx.single_source_bellman_ford, G, 1)
571 pytest.raises(
572 nx.NetworkXUnbounded, nx.bellman_ford_predecessor_and_distance, G, 1
573 )
574 pytest.raises(nx.NetworkXUnbounded, nx.goldberg_radzik, G, 1)
575 # no negative cycle but negative weight
576 G = nx.cycle_graph(5, create_using=nx.DiGraph())
577 G.add_edge(1, 2, weight=-3)
578 assert nx.single_source_bellman_ford_path(G, 0) == {
579 0: [0],
580 1: [0, 1],
581 2: [0, 1, 2],
582 3: [0, 1, 2, 3],
583 4: [0, 1, 2, 3, 4],
584 }
585 assert nx.single_source_bellman_ford_path_length(G, 0) == {
586 0: 0,
587 1: 1,
588 2: -2,
589 3: -1,
590 4: 0,
591 }
592 assert nx.single_source_bellman_ford(G, 0) == (
593 {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
594 {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]},
595 )
596 assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
597 {0: [], 1: [0], 2: [1], 3: [2], 4: [3]},
598 {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
599 )
600 assert nx.goldberg_radzik(G, 0) == (
601 {0: None, 1: 0, 2: 1, 3: 2, 4: 3},
602 {0: 0, 1: 1, 2: -2, 3: -1, 4: 0},
603 )
604
605 def test_not_connected(self):
606 G = nx.complete_graph(6)
607 G.add_edge(10, 11)
608 G.add_edge(10, 12)
609 assert nx.single_source_bellman_ford_path(G, 0) == {
610 0: [0],
611 1: [0, 1],
612 2: [0, 2],
613 3: [0, 3],
614 4: [0, 4],
615 5: [0, 5],
616 }
617 assert nx.single_source_bellman_ford_path_length(G, 0) == {
618 0: 0,
619 1: 1,
620 2: 1,
621 3: 1,
622 4: 1,
623 5: 1,
624 }
625 assert nx.single_source_bellman_ford(G, 0) == (
626 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
627 {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]},
628 )
629 assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
630 {0: [], 1: [0], 2: [0], 3: [0], 4: [0], 5: [0]},
631 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
632 )
633 assert nx.goldberg_radzik(G, 0) == (
634 {0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
635 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
636 )
637
638 # not connected, with a component not containing the source that
639 # contains a negative cost cycle.
640 G = nx.complete_graph(6)
641 G.add_edges_from(
642 [
643 ("A", "B", {"load": 3}),
644 ("B", "C", {"load": -10}),
645 ("C", "A", {"load": 2}),
646 ]
647 )
648 assert nx.single_source_bellman_ford_path(G, 0, weight="load") == {
649 0: [0],
650 1: [0, 1],
651 2: [0, 2],
652 3: [0, 3],
653 4: [0, 4],
654 5: [0, 5],
655 }
656 assert nx.single_source_bellman_ford_path_length(G, 0, weight="load") == {
657 0: 0,
658 1: 1,
659 2: 1,
660 3: 1,
661 4: 1,
662 5: 1,
663 }
664 assert nx.single_source_bellman_ford(G, 0, weight="load") == (
665 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
666 {0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5]},
667 )
668 assert nx.bellman_ford_predecessor_and_distance(G, 0, weight="load") == (
669 {0: [], 1: [0], 2: [0], 3: [0], 4: [0], 5: [0]},
670 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
671 )
672 assert nx.goldberg_radzik(G, 0, weight="load") == (
673 {0: None, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0},
674 {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1},
675 )
676
677 def test_multigraph(self):
678 assert nx.bellman_ford_path(self.MXG, "s", "v") == ["s", "x", "u", "v"]
679 assert nx.bellman_ford_path_length(self.MXG, "s", "v") == 9
680 assert nx.single_source_bellman_ford_path(self.MXG, "s")["v"] == [
681 "s",
682 "x",
683 "u",
684 "v",
685 ]
686 assert nx.single_source_bellman_ford_path_length(self.MXG, "s")["v"] == 9
687 D, P = nx.single_source_bellman_ford(self.MXG, "s", target="v")
688 assert D == 9
689 assert P == ["s", "x", "u", "v"]
690 P, D = nx.bellman_ford_predecessor_and_distance(self.MXG, "s")
691 assert P["v"] == ["u"]
692 assert D["v"] == 9
693 P, D = nx.goldberg_radzik(self.MXG, "s")
694 assert P["v"] == "u"
695 assert D["v"] == 9
696 assert nx.bellman_ford_path(self.MXG4, 0, 2) == [0, 1, 2]
697 assert nx.bellman_ford_path_length(self.MXG4, 0, 2) == 4
698 assert nx.single_source_bellman_ford_path(self.MXG4, 0)[2] == [0, 1, 2]
699 assert nx.single_source_bellman_ford_path_length(self.MXG4, 0)[2] == 4
700 D, P = nx.single_source_bellman_ford(self.MXG4, 0, target=2)
701 assert D == 4
702 assert P == [0, 1, 2]
703 P, D = nx.bellman_ford_predecessor_and_distance(self.MXG4, 0)
704 assert P[2] == [1]
705 assert D[2] == 4
706 P, D = nx.goldberg_radzik(self.MXG4, 0)
707 assert P[2] == 1
708 assert D[2] == 4
709
710 def test_others(self):
711 assert nx.bellman_ford_path(self.XG, "s", "v") == ["s", "x", "u", "v"]
712 assert nx.bellman_ford_path_length(self.XG, "s", "v") == 9
713 assert nx.single_source_bellman_ford_path(self.XG, "s")["v"] == [
714 "s",
715 "x",
716 "u",
717 "v",
718 ]
719 assert nx.single_source_bellman_ford_path_length(self.XG, "s")["v"] == 9
720 D, P = nx.single_source_bellman_ford(self.XG, "s", target="v")
721 assert D == 9
722 assert P == ["s", "x", "u", "v"]
723 (P, D) = nx.bellman_ford_predecessor_and_distance(self.XG, "s")
724 assert P["v"] == ["u"]
725 assert D["v"] == 9
726 (P, D) = nx.goldberg_radzik(self.XG, "s")
727 assert P["v"] == "u"
728 assert D["v"] == 9
729
730 def test_path_graph(self):
731 G = nx.path_graph(4)
732 assert nx.single_source_bellman_ford_path(G, 0) == {
733 0: [0],
734 1: [0, 1],
735 2: [0, 1, 2],
736 3: [0, 1, 2, 3],
737 }
738 assert nx.single_source_bellman_ford_path_length(G, 0) == {
739 0: 0,
740 1: 1,
741 2: 2,
742 3: 3,
743 }
744 assert nx.single_source_bellman_ford(G, 0) == (
745 {0: 0, 1: 1, 2: 2, 3: 3},
746 {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3]},
747 )
748 assert nx.bellman_ford_predecessor_and_distance(G, 0) == (
749 {0: [], 1: [0], 2: [1], 3: [2]},
750 {0: 0, 1: 1, 2: 2, 3: 3},
751 )
752 assert nx.goldberg_radzik(G, 0) == (
753 {0: None, 1: 0, 2: 1, 3: 2},
754 {0: 0, 1: 1, 2: 2, 3: 3},
755 )
756 assert nx.single_source_bellman_ford_path(G, 3) == {
757 0: [3, 2, 1, 0],
758 1: [3, 2, 1],
759 2: [3, 2],
760 3: [3],
761 }
762 assert nx.single_source_bellman_ford_path_length(G, 3) == {
763 0: 3,
764 1: 2,
765 2: 1,
766 3: 0,
767 }
768 assert nx.single_source_bellman_ford(G, 3) == (
769 {0: 3, 1: 2, 2: 1, 3: 0},
770 {0: [3, 2, 1, 0], 1: [3, 2, 1], 2: [3, 2], 3: [3]},
771 )
772 assert nx.bellman_ford_predecessor_and_distance(G, 3) == (
773 {0: [1], 1: [2], 2: [3], 3: []},
774 {0: 3, 1: 2, 2: 1, 3: 0},
775 )
776 assert nx.goldberg_radzik(G, 3) == (
777 {0: 1, 1: 2, 2: 3, 3: None},
778 {0: 3, 1: 2, 2: 1, 3: 0},
779 )
780
781 def test_4_cycle(self):
782 # 4-cycle
783 G = nx.Graph([(0, 1), (1, 2), (2, 3), (3, 0)])
784 dist, path = nx.single_source_bellman_ford(G, 0)
785 assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
786 assert path[0] == [0]
787 assert path[1] == [0, 1]
788 assert path[2] in [[0, 1, 2], [0, 3, 2]]
789 assert path[3] == [0, 3]
790
791 pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
792 assert pred[0] == []
793 assert pred[1] == [0]
794 assert pred[2] in [[1, 3], [3, 1]]
795 assert pred[3] == [0]
796 assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
797
798 pred, dist = nx.goldberg_radzik(G, 0)
799 assert pred[0] is None
800 assert pred[1] == 0
801 assert pred[2] in [1, 3]
802 assert pred[3] == 0
803 assert dist == {0: 0, 1: 1, 2: 2, 3: 1}
804
805 def test_negative_weight(self):
806 G = nx.DiGraph()
807 G.add_nodes_from("abcd")
808 G.add_edge("a", "d", weight=0)
809 G.add_edge("a", "b", weight=1)
810 G.add_edge("b", "c", weight=-3)
811 G.add_edge("c", "d", weight=1)
812
813 assert nx.bellman_ford_path(G, "a", "d") == ["a", "b", "c", "d"]
814 assert nx.bellman_ford_path_length(G, "a", "d") == -1
815
816 def test_zero_cycle_smoke(self):
817 D = nx.DiGraph()
818 D.add_weighted_edges_from([(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 1, -2)])
819
820 nx.bellman_ford_path(D, 1, 3)
821 nx.dijkstra_path(D, 1, 3)
822 nx.bidirectional_dijkstra(D, 1, 3)
823 # FIXME nx.goldberg_radzik(D, 1)
824
825
826 class TestJohnsonAlgorithm(WeightedTestBase):
827 def test_single_node_graph(self):
828 with pytest.raises(nx.NetworkXError):
829 G = nx.DiGraph()
830 G.add_node(0)
831 nx.johnson(G)
832
833 def test_negative_cycle(self):
834 G = nx.DiGraph()
835 G.add_weighted_edges_from(
836 [
837 ("0", "3", 3),
838 ("0", "1", -5),
839 ("1", "0", -5),
840 ("0", "2", 2),
841 ("1", "2", 4),
842 ("2", "3", 1),
843 ]
844 )
845 pytest.raises(nx.NetworkXUnbounded, nx.johnson, G)
846 G = nx.Graph()
847 G.add_weighted_edges_from(
848 [
849 ("0", "3", 3),
850 ("0", "1", -5),
851 ("1", "0", -5),
852 ("0", "2", 2),
853 ("1", "2", 4),
854 ("2", "3", 1),
855 ]
856 )
857 pytest.raises(nx.NetworkXUnbounded, nx.johnson, G)
858
859 def test_negative_weights(self):
860 G = nx.DiGraph()
861 G.add_weighted_edges_from(
862 [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
863 )
864 paths = nx.johnson(G)
865 assert paths == {
866 "1": {"1": ["1"], "3": ["1", "2", "3"], "2": ["1", "2"]},
867 "0": {
868 "1": ["0", "1"],
869 "0": ["0"],
870 "3": ["0", "1", "2", "3"],
871 "2": ["0", "1", "2"],
872 },
873 "3": {"3": ["3"]},
874 "2": {"3": ["2", "3"], "2": ["2"]},
875 }
876
877 def test_unweighted_graph(self):
878 with pytest.raises(nx.NetworkXError):
879 G = nx.path_graph(5)
880 nx.johnson(G)
881
882 def test_graphs(self):
883 validate_path(self.XG, "s", "v", 9, nx.johnson(self.XG)["s"]["v"])
884 validate_path(self.MXG, "s", "v", 9, nx.johnson(self.MXG)["s"]["v"])
885 validate_path(self.XG2, 1, 3, 4, nx.johnson(self.XG2)[1][3])
886 validate_path(self.XG3, 0, 3, 15, nx.johnson(self.XG3)[0][3])
887 validate_path(self.XG4, 0, 2, 4, nx.johnson(self.XG4)[0][2])
888 validate_path(self.MXG4, 0, 2, 4, nx.johnson(self.MXG4)[0][2])