Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/tests/test_generic.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 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() | |
32 cls.neg_weights.add_edge(0, 1, weight=1) | |
33 cls.neg_weights.add_edge(0, 2, weight=3) | |
34 cls.neg_weights.add_edge(1, 3, weight=1) | |
35 cls.neg_weights.add_edge(2, 3, weight=-2) | |
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) | |
74 assert sp == answer | |
75 # with weights | |
76 sp = nx.shortest_path(nx.path_graph(3), target=1, weight="weight") | |
77 assert sp == answer | |
78 # weights and method specified | |
79 sp = nx.shortest_path( | |
80 nx.path_graph(3), target=1, weight="weight", method="dijkstra" | |
81 ) | |
82 assert sp == answer | |
83 sp = nx.shortest_path( | |
84 nx.path_graph(3), target=1, weight="weight", method="bellman-ford" | |
85 ) | |
86 assert sp == answer | |
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)) | |
117 assert sp == answer | |
118 # with weights | |
119 sp = nx.shortest_path_length(nx.path_graph(3), target=1, weight="weight") | |
120 assert sp == answer | |
121 # weights and method specified | |
122 sp = nx.shortest_path_length( | |
123 nx.path_graph(3), target=1, weight="weight", method="dijkstra" | |
124 ) | |
125 assert sp == answer | |
126 sp = nx.shortest_path_length( | |
127 nx.path_graph(3), target=1, weight="weight", method="bellman-ford" | |
128 ) | |
129 assert sp == answer | |
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() | |
223 nx.add_path(G, range(3)) | |
224 nx.add_path(G, range(3, 5)) | |
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) | |
257 G.add_node(4) | |
258 list(nx.all_shortest_paths(G, 0, 4)) | |
259 | |
260 def test_bad_method(self): | |
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() | |
267 nx.add_path(g, [0, 1, 3]) | |
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() | |
298 nx.add_cycle(G, range(7), weight=2) | |
299 ans = nx.average_shortest_path_length(G, weight="weight") | |
300 assert almost_equal(ans, 4) | |
301 G = nx.Graph() | |
302 nx.add_path(G, range(5), weight=2) | |
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() | |
308 nx.add_cycle(G, range(7), weight=2) | |
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() | |
319 nx.add_path(G, range(5), weight=2) | |
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() | |
331 g.add_nodes_from(range(3)) | |
332 g.add_edge(0, 1) | |
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 | |
342 For more information, see issue #1960. | |
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 | |
352 def test_bad_method(self): | |
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() | |
370 nx.add_cycle(G, range(7), weight=2) | |
371 ans = nx.average_shortest_path_length( | |
372 G, weight="weight", method="floyd-warshall-numpy" | |
373 ) | |
374 npt.assert_almost_equal(ans, 4) | |
375 | |
376 G = nx.Graph() | |
377 nx.add_path(G, range(5), weight=2) | |
378 ans = nx.average_shortest_path_length( | |
379 G, weight="weight", method="floyd-warshall-numpy" | |
380 ) | |
381 npt.assert_almost_equal(ans, 4) |