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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 import pytest
2
3
4 import networkx as nx
5 from networkx.testing import almost_equal
6
7
8 def validate_grid_path(r, c, s, t, p):
9 assert isinstance(p, list)
10 assert p[0] == s
11 assert p[-1] == t
12 s = ((s - 1) // c, (s - 1) % c)
13 t = ((t - 1) // c, (t - 1) % c)
14 assert len(p) == abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1
15 p = [((u - 1) // c, (u - 1) % c) for u in p]
16 for u in p:
17 assert 0 <= u[0] < r
18 assert 0 <= u[1] < c
19 for u, v in zip(p[:-1], p[1:]):
20 assert (abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)]
21
22
23 class TestGenericPath:
24 @classmethod
25 def setup_class(cls):
26 from networkx import convert_node_labels_to_integers as cnlti
27
28 cls.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
29 cls.cycle = nx.cycle_graph(7)
30 cls.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
31 cls.neg_weights = nx.DiGraph()
36
37 def test_shortest_path(self):
38 assert nx.shortest_path(self.cycle, 0, 3) == [0, 1, 2, 3]
39 assert nx.shortest_path(self.cycle, 0, 4) == [0, 6, 5, 4]
40 validate_grid_path(4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12))
41 assert nx.shortest_path(self.directed_cycle, 0, 3) == [0, 1, 2, 3]
42 # now with weights
43 assert nx.shortest_path(self.cycle, 0, 3, weight="weight") == [0, 1, 2, 3]
44 assert nx.shortest_path(self.cycle, 0, 4, weight="weight") == [0, 6, 5, 4]
45 validate_grid_path(
46 4, 4, 1, 12, nx.shortest_path(self.grid, 1, 12, weight="weight")
47 )
48 assert nx.shortest_path(self.directed_cycle, 0, 3, weight="weight") == [
49 0,
50 1,
51 2,
52 3,
53 ]
54 # weights and method specified
55 assert nx.shortest_path(
56 self.directed_cycle, 0, 3, weight="weight", method="dijkstra"
57 ) == [0, 1, 2, 3]
58 assert nx.shortest_path(
59 self.directed_cycle, 0, 3, weight="weight", method="bellman-ford"
60 ) == [0, 1, 2, 3]
61 # when Dijkstra's will probably (depending on precise implementation)
62 # incorrectly return [0, 1, 3] instead
63 assert nx.shortest_path(
64 self.neg_weights, 0, 3, weight="weight", method="bellman-ford"
65 ) == [0, 2, 3]
66 # confirm bad method rejection
67 pytest.raises(ValueError, nx.shortest_path, self.cycle, method="SPAM")
68 # confirm absent source rejection
69 pytest.raises(nx.NodeNotFound, nx.shortest_path, self.cycle, 8)
70
71 def test_shortest_path_target(self):
72 answer = {0: [0, 1], 1: [1], 2: [2, 1]}
73 sp = nx.shortest_path(nx.path_graph(3), target=1)
75 # with weights
76 sp = nx.shortest_path(nx.path_graph(3), target=1, weight="weight")
78 # weights and method specified
79 sp = nx.shortest_path(
80 nx.path_graph(3), target=1, weight="weight", method="dijkstra"
81 )
83 sp = nx.shortest_path(
84 nx.path_graph(3), target=1, weight="weight", method="bellman-ford"
85 )
87
88 def test_shortest_path_length(self):
89 assert nx.shortest_path_length(self.cycle, 0, 3) == 3
90 assert nx.shortest_path_length(self.grid, 1, 12) == 5
91 assert nx.shortest_path_length(self.directed_cycle, 0, 4) == 4
92 # now with weights
93 assert nx.shortest_path_length(self.cycle, 0, 3, weight="weight") == 3
94 assert nx.shortest_path_length(self.grid, 1, 12, weight="weight") == 5
95 assert nx.shortest_path_length(self.directed_cycle, 0, 4, weight="weight") == 4
96 # weights and method specified
97 assert (
98 nx.shortest_path_length(
99 self.cycle, 0, 3, weight="weight", method="dijkstra"
100 )
101 == 3
102 )
103 assert (
104 nx.shortest_path_length(
105 self.cycle, 0, 3, weight="weight", method="bellman-ford"
106 )
107 == 3
108 )
109 # confirm bad method rejection
110 pytest.raises(ValueError, nx.shortest_path_length, self.cycle, method="SPAM")
111 # confirm absent source rejection
112 pytest.raises(nx.NodeNotFound, nx.shortest_path_length, self.cycle, 8)
113
114 def test_shortest_path_length_target(self):
115 answer = {0: 1, 1: 0, 2: 1}
116 sp = dict(nx.shortest_path_length(nx.path_graph(3), target=1))
118 # with weights
119 sp = nx.shortest_path_length(nx.path_graph(3), target=1, weight="weight")
121 # weights and method specified
122 sp = nx.shortest_path_length(
123 nx.path_graph(3), target=1, weight="weight", method="dijkstra"
124 )
126 sp = nx.shortest_path_length(
127 nx.path_graph(3), target=1, weight="weight", method="bellman-ford"
128 )
130
131 def test_single_source_shortest_path(self):
132 p = nx.shortest_path(self.cycle, 0)
133 assert p[3] == [0, 1, 2, 3]
134 assert p == nx.single_source_shortest_path(self.cycle, 0)
135 p = nx.shortest_path(self.grid, 1)
136 validate_grid_path(4, 4, 1, 12, p[12])
137 # now with weights
138 p = nx.shortest_path(self.cycle, 0, weight="weight")
139 assert p[3] == [0, 1, 2, 3]
140 assert p == nx.single_source_dijkstra_path(self.cycle, 0)
141 p = nx.shortest_path(self.grid, 1, weight="weight")
142 validate_grid_path(4, 4, 1, 12, p[12])
143 # weights and method specified
144 p = nx.shortest_path(self.cycle, 0, method="dijkstra", weight="weight")
145 assert p[3] == [0, 1, 2, 3]
146 assert p == nx.single_source_shortest_path(self.cycle, 0)
147 p = nx.shortest_path(self.cycle, 0, method="bellman-ford", weight="weight")
148 assert p[3] == [0, 1, 2, 3]
149 assert p == nx.single_source_shortest_path(self.cycle, 0)
150
151 def test_single_source_shortest_path_length(self):
152 ans = dict(nx.shortest_path_length(self.cycle, 0))
153 assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
154 assert ans == dict(nx.single_source_shortest_path_length(self.cycle, 0))
155 ans = dict(nx.shortest_path_length(self.grid, 1))
156 assert ans[16] == 6
157 # now with weights
158 ans = dict(nx.shortest_path_length(self.cycle, 0, weight="weight"))
159 assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
160 assert ans == dict(nx.single_source_dijkstra_path_length(self.cycle, 0))
161 ans = dict(nx.shortest_path_length(self.grid, 1, weight="weight"))
162 assert ans[16] == 6
163 # weights and method specified
164 ans = dict(
165 nx.shortest_path_length(self.cycle, 0, weight="weight", method="dijkstra")
166 )
167 assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
168 assert ans == dict(nx.single_source_dijkstra_path_length(self.cycle, 0))
169 ans = dict(
170 nx.shortest_path_length(
171 self.cycle, 0, weight="weight", method="bellman-ford"
172 )
173 )
174 assert ans == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
175 assert ans == dict(nx.single_source_bellman_ford_path_length(self.cycle, 0))
176
177 def test_all_pairs_shortest_path(self):
178 p = nx.shortest_path(self.cycle)
179 assert p[0][3] == [0, 1, 2, 3]
180 assert p == dict(nx.all_pairs_shortest_path(self.cycle))
181 p = nx.shortest_path(self.grid)
182 validate_grid_path(4, 4, 1, 12, p[1][12])
183 # now with weights
184 p = nx.shortest_path(self.cycle, weight="weight")
185 assert p[0][3] == [0, 1, 2, 3]
186 assert p == dict(nx.all_pairs_dijkstra_path(self.cycle))
187 p = nx.shortest_path(self.grid, weight="weight")
188 validate_grid_path(4, 4, 1, 12, p[1][12])
189 # weights and method specified
190 p = nx.shortest_path(self.cycle, weight="weight", method="dijkstra")
191 assert p[0][3] == [0, 1, 2, 3]
192 assert p == dict(nx.all_pairs_dijkstra_path(self.cycle))
193 p = nx.shortest_path(self.cycle, weight="weight", method="bellman-ford")
194 assert p[0][3] == [0, 1, 2, 3]
195 assert p == dict(nx.all_pairs_bellman_ford_path(self.cycle))
196
197 def test_all_pairs_shortest_path_length(self):
198 ans = dict(nx.shortest_path_length(self.cycle))
199 assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
200 assert ans == dict(nx.all_pairs_shortest_path_length(self.cycle))
201 ans = dict(nx.shortest_path_length(self.grid))
202 assert ans[1][16] == 6
203 # now with weights
204 ans = dict(nx.shortest_path_length(self.cycle, weight="weight"))
205 assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
206 assert ans == dict(nx.all_pairs_dijkstra_path_length(self.cycle))
207 ans = dict(nx.shortest_path_length(self.grid, weight="weight"))
208 assert ans[1][16] == 6
209 # weights and method specified
210 ans = dict(
211 nx.shortest_path_length(self.cycle, weight="weight", method="dijkstra")
212 )
213 assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
214 assert ans == dict(nx.all_pairs_dijkstra_path_length(self.cycle))
215 ans = dict(
216 nx.shortest_path_length(self.cycle, weight="weight", method="bellman-ford")
217 )
218 assert ans[0] == {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
219 assert ans == dict(nx.all_pairs_bellman_ford_path_length(self.cycle))
220
221 def test_has_path(self):
222 G = nx.Graph()
225 assert nx.has_path(G, 0, 2)
226 assert not nx.has_path(G, 0, 4)
227
228 def test_all_shortest_paths(self):
229 G = nx.Graph()
230 nx.add_path(G, [0, 1, 2, 3])
231 nx.add_path(G, [0, 10, 20, 3])
232 assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(nx.all_shortest_paths(G, 0, 3))
233 # with weights
234 G = nx.Graph()
235 nx.add_path(G, [0, 1, 2, 3])
236 nx.add_path(G, [0, 10, 20, 3])
237 assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
238 nx.all_shortest_paths(G, 0, 3, weight="weight")
239 )
240 # weights and method specified
241 G = nx.Graph()
242 nx.add_path(G, [0, 1, 2, 3])
243 nx.add_path(G, [0, 10, 20, 3])
244 assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
245 nx.all_shortest_paths(G, 0, 3, weight="weight", method="dijkstra")
246 )
247 G = nx.Graph()
248 nx.add_path(G, [0, 1, 2, 3])
249 nx.add_path(G, [0, 10, 20, 3])
250 assert [[0, 1, 2, 3], [0, 10, 20, 3]] == sorted(
251 nx.all_shortest_paths(G, 0, 3, weight="weight", method="bellman-ford")
252 )
253
254 def test_all_shortest_paths_raise(self):
255 with pytest.raises(nx.NetworkXNoPath):
256 G = nx.path_graph(4)
258 list(nx.all_shortest_paths(G, 0, 4))
259
261 with pytest.raises(ValueError):
262 G = nx.path_graph(2)
263 list(nx.all_shortest_paths(G, 0, 1, weight="weight", method="SPAM"))
264
265 def test_all_shortest_paths_zero_weight_edge(self):
266 g = nx.Graph()
268 nx.add_path(g, [0, 1, 2, 3])
269 g.edges[1, 2]["weight"] = 0
270 paths30d = list(
271 nx.all_shortest_paths(g, 3, 0, weight="weight", method="dijkstra")
272 )
273 paths03d = list(
274 nx.all_shortest_paths(g, 0, 3, weight="weight", method="dijkstra")
275 )
276 paths30b = list(
277 nx.all_shortest_paths(g, 3, 0, weight="weight", method="bellman-ford")
278 )
279 paths03b = list(
280 nx.all_shortest_paths(g, 0, 3, weight="weight", method="bellman-ford")
281 )
282 assert sorted(paths03d) == sorted(p[::-1] for p in paths30d)
283 assert sorted(paths03d) == sorted(p[::-1] for p in paths30b)
284 assert sorted(paths03b) == sorted(p[::-1] for p in paths30b)
285
286
287 class TestAverageShortestPathLength:
288 def test_cycle_graph(self):
289 ans = nx.average_shortest_path_length(nx.cycle_graph(7))
290 assert almost_equal(ans, 2)
291
292 def test_path_graph(self):
293 ans = nx.average_shortest_path_length(nx.path_graph(5))
294 assert almost_equal(ans, 2)
295
296 def test_weighted(self):
297 G = nx.Graph()
299 ans = nx.average_shortest_path_length(G, weight="weight")
300 assert almost_equal(ans, 4)
301 G = nx.Graph()
303 ans = nx.average_shortest_path_length(G, weight="weight")
304 assert almost_equal(ans, 4)
305
306 def test_specified_methods(self):
307 G = nx.Graph()
309 ans = nx.average_shortest_path_length(G, weight="weight", method="dijkstra")
310 assert almost_equal(ans, 4)
311 ans = nx.average_shortest_path_length(G, weight="weight", method="bellman-ford")
312 assert almost_equal(ans, 4)
313 ans = nx.average_shortest_path_length(
314 G, weight="weight", method="floyd-warshall"
315 )
316 assert almost_equal(ans, 4)
317
318 G = nx.Graph()
320 ans = nx.average_shortest_path_length(G, weight="weight", method="dijkstra")
321 assert almost_equal(ans, 4)
322 ans = nx.average_shortest_path_length(G, weight="weight", method="bellman-ford")
323 assert almost_equal(ans, 4)
324 ans = nx.average_shortest_path_length(
325 G, weight="weight", method="floyd-warshall"
326 )
327 assert almost_equal(ans, 4)
328
329 def test_disconnected(self):
330 g = nx.Graph()
333 pytest.raises(nx.NetworkXError, nx.average_shortest_path_length, g)
334 g = g.to_directed()
335 pytest.raises(nx.NetworkXError, nx.average_shortest_path_length, g)
336
337 def test_trivial_graph(self):
338 """Tests that the trivial graph has average path length zero,
339 since there is exactly one path of length zero in the trivial
340 graph.
341
343
344 """
345 G = nx.trivial_graph()
346 assert nx.average_shortest_path_length(G) == 0
347
348 def test_null_graph(self):
349 with pytest.raises(nx.NetworkXPointlessConcept):
350 nx.average_shortest_path_length(nx.null_graph())
351
353 with pytest.raises(ValueError):
354 G = nx.path_graph(2)
355 nx.average_shortest_path_length(G, weight="weight", method="SPAM")
356
357
358 class TestAverageShortestPathLengthNumpy:
359 @classmethod
360 def setup_class(cls):
361 global numpy
362 global npt
363 import pytest
364
365 numpy = pytest.importorskip("numpy")
366 npt = pytest.importorskip("numpy.testing")
367
368 def test_specified_methods_numpy(self):
369 G = nx.Graph()