Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/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 """ | |
2 Compute the shortest paths and path lengths between nodes in the graph. | |
3 | |
4 These algorithms work with undirected and directed graphs. | |
5 | |
6 """ | |
7 | |
8 import networkx as nx | |
9 | |
10 __all__ = [ | |
11 "shortest_path", | |
12 "all_shortest_paths", | |
13 "shortest_path_length", | |
14 "average_shortest_path_length", | |
15 "has_path", | |
16 ] | |
17 | |
18 | |
19 def has_path(G, source, target): | |
20 """Returns *True* if *G* has a path from *source* to *target*. | |
21 | |
22 Parameters | |
23 ---------- | |
24 G : NetworkX graph | |
25 | |
26 source : node | |
27 Starting node for path | |
28 | |
29 target : node | |
30 Ending node for path | |
31 """ | |
32 try: | |
33 nx.shortest_path(G, source, target) | |
34 except nx.NetworkXNoPath: | |
35 return False | |
36 return True | |
37 | |
38 | |
39 def shortest_path(G, source=None, target=None, weight=None, method="dijkstra"): | |
40 """Compute shortest paths in the graph. | |
41 | |
42 Parameters | |
43 ---------- | |
44 G : NetworkX graph | |
45 | |
46 source : node, optional | |
47 Starting node for path. If not specified, compute shortest | |
48 paths for each possible starting node. | |
49 | |
50 target : node, optional | |
51 Ending node for path. If not specified, compute shortest | |
52 paths to all possible nodes. | |
53 | |
54 weight : None or string, optional (default = None) | |
55 If None, every edge has weight/distance/cost 1. | |
56 If a string, use this edge attribute as the edge weight. | |
57 Any edge attribute not present defaults to 1. | |
58 | |
59 method : string, optional (default = 'dijkstra') | |
60 The algorithm to use to compute the path. | |
61 Supported options: 'dijkstra', 'bellman-ford'. | |
62 Other inputs produce a ValueError. | |
63 If `weight` is None, unweighted graph methods are used, and this | |
64 suggestion is ignored. | |
65 | |
66 Returns | |
67 ------- | |
68 path: list or dictionary | |
69 All returned paths include both the source and target in the path. | |
70 | |
71 If the source and target are both specified, return a single list | |
72 of nodes in a shortest path from the source to the target. | |
73 | |
74 If only the source is specified, return a dictionary keyed by | |
75 targets with a list of nodes in a shortest path from the source | |
76 to one of the targets. | |
77 | |
78 If only the target is specified, return a dictionary keyed by | |
79 sources with a list of nodes in a shortest path from one of the | |
80 sources to the target. | |
81 | |
82 If neither the source nor target are specified return a dictionary | |
83 of dictionaries with path[source][target]=[list of nodes in path]. | |
84 | |
85 Raises | |
86 ------ | |
87 NodeNotFound | |
88 If `source` is not in `G`. | |
89 | |
90 ValueError | |
91 If `method` is not among the supported options. | |
92 | |
93 Examples | |
94 -------- | |
95 >>> G = nx.path_graph(5) | |
96 >>> print(nx.shortest_path(G, source=0, target=4)) | |
97 [0, 1, 2, 3, 4] | |
98 >>> p = nx.shortest_path(G, source=0) # target not specified | |
99 >>> p[4] | |
100 [0, 1, 2, 3, 4] | |
101 >>> p = nx.shortest_path(G, target=4) # source not specified | |
102 >>> p[0] | |
103 [0, 1, 2, 3, 4] | |
104 >>> p = nx.shortest_path(G) # source, target not specified | |
105 >>> p[0][4] | |
106 [0, 1, 2, 3, 4] | |
107 | |
108 Notes | |
109 ----- | |
110 There may be more than one shortest path between a source and target. | |
111 This returns only one of them. | |
112 | |
113 See Also | |
114 -------- | |
115 all_pairs_shortest_path() | |
116 all_pairs_dijkstra_path() | |
117 all_pairs_bellman_ford_path() | |
118 single_source_shortest_path() | |
119 single_source_dijkstra_path() | |
120 single_source_bellman_ford_path() | |
121 """ | |
122 if method not in ("dijkstra", "bellman-ford"): | |
123 # so we don't need to check in each branch later | |
124 raise ValueError(f"method not supported: {method}") | |
125 method = "unweighted" if weight is None else method | |
126 if source is None: | |
127 if target is None: | |
128 # Find paths between all pairs. | |
129 if method == "unweighted": | |
130 paths = dict(nx.all_pairs_shortest_path(G)) | |
131 elif method == "dijkstra": | |
132 paths = dict(nx.all_pairs_dijkstra_path(G, weight=weight)) | |
133 else: # method == 'bellman-ford': | |
134 paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight)) | |
135 else: | |
136 # Find paths from all nodes co-accessible to the target. | |
137 if G.is_directed(): | |
138 G = G.reverse(copy=False) | |
139 if method == "unweighted": | |
140 paths = nx.single_source_shortest_path(G, target) | |
141 elif method == "dijkstra": | |
142 paths = nx.single_source_dijkstra_path(G, target, weight=weight) | |
143 else: # method == 'bellman-ford': | |
144 paths = nx.single_source_bellman_ford_path(G, target, weight=weight) | |
145 # Now flip the paths so they go from a source to the target. | |
146 for target in paths: | |
147 paths[target] = list(reversed(paths[target])) | |
148 else: | |
149 if target is None: | |
150 # Find paths to all nodes accessible from the source. | |
151 if method == "unweighted": | |
152 paths = nx.single_source_shortest_path(G, source) | |
153 elif method == "dijkstra": | |
154 paths = nx.single_source_dijkstra_path(G, source, weight=weight) | |
155 else: # method == 'bellman-ford': | |
156 paths = nx.single_source_bellman_ford_path(G, source, weight=weight) | |
157 else: | |
158 # Find shortest source-target path. | |
159 if method == "unweighted": | |
160 paths = nx.bidirectional_shortest_path(G, source, target) | |
161 elif method == "dijkstra": | |
162 paths = nx.dijkstra_path(G, source, target, weight) | |
163 else: # method == 'bellman-ford': | |
164 paths = nx.bellman_ford_path(G, source, target, weight) | |
165 return paths | |
166 | |
167 | |
168 def shortest_path_length(G, source=None, target=None, weight=None, method="dijkstra"): | |
169 """Compute shortest path lengths in the graph. | |
170 | |
171 Parameters | |
172 ---------- | |
173 G : NetworkX graph | |
174 | |
175 source : node, optional | |
176 Starting node for path. | |
177 If not specified, compute shortest path lengths using all nodes as | |
178 source nodes. | |
179 | |
180 target : node, optional | |
181 Ending node for path. | |
182 If not specified, compute shortest path lengths using all nodes as | |
183 target nodes. | |
184 | |
185 weight : None or string, optional (default = None) | |
186 If None, every edge has weight/distance/cost 1. | |
187 If a string, use this edge attribute as the edge weight. | |
188 Any edge attribute not present defaults to 1. | |
189 | |
190 method : string, optional (default = 'dijkstra') | |
191 The algorithm to use to compute the path length. | |
192 Supported options: 'dijkstra', 'bellman-ford'. | |
193 Other inputs produce a ValueError. | |
194 If `weight` is None, unweighted graph methods are used, and this | |
195 suggestion is ignored. | |
196 | |
197 Returns | |
198 ------- | |
199 length: int or iterator | |
200 If the source and target are both specified, return the length of | |
201 the shortest path from the source to the target. | |
202 | |
203 If only the source is specified, return a dict keyed by target | |
204 to the shortest path length from the source to that target. | |
205 | |
206 If only the target is specified, return a dict keyed by source | |
207 to the shortest path length from that source to the target. | |
208 | |
209 If neither the source nor target are specified, return an iterator | |
210 over (source, dictionary) where dictionary is keyed by target to | |
211 shortest path length from source to that target. | |
212 | |
213 Raises | |
214 ------ | |
215 NodeNotFound | |
216 If `source` is not in `G`. | |
217 | |
218 NetworkXNoPath | |
219 If no path exists between source and target. | |
220 | |
221 ValueError | |
222 If `method` is not among the supported options. | |
223 | |
224 Examples | |
225 -------- | |
226 >>> G = nx.path_graph(5) | |
227 >>> nx.shortest_path_length(G, source=0, target=4) | |
228 4 | |
229 >>> p = nx.shortest_path_length(G, source=0) # target not specified | |
230 >>> p[4] | |
231 4 | |
232 >>> p = nx.shortest_path_length(G, target=4) # source not specified | |
233 >>> p[0] | |
234 4 | |
235 >>> p = dict(nx.shortest_path_length(G)) # source,target not specified | |
236 >>> p[0][4] | |
237 4 | |
238 | |
239 Notes | |
240 ----- | |
241 The length of the path is always 1 less than the number of nodes involved | |
242 in the path since the length measures the number of edges followed. | |
243 | |
244 For digraphs this returns the shortest directed path length. To find path | |
245 lengths in the reverse direction use G.reverse(copy=False) first to flip | |
246 the edge orientation. | |
247 | |
248 See Also | |
249 -------- | |
250 all_pairs_shortest_path_length() | |
251 all_pairs_dijkstra_path_length() | |
252 all_pairs_bellman_ford_path_length() | |
253 single_source_shortest_path_length() | |
254 single_source_dijkstra_path_length() | |
255 single_source_bellman_ford_path_length() | |
256 """ | |
257 if method not in ("dijkstra", "bellman-ford"): | |
258 # so we don't need to check in each branch later | |
259 raise ValueError(f"method not supported: {method}") | |
260 method = "unweighted" if weight is None else method | |
261 if source is None: | |
262 if target is None: | |
263 # Find paths between all pairs. | |
264 if method == "unweighted": | |
265 paths = nx.all_pairs_shortest_path_length(G) | |
266 elif method == "dijkstra": | |
267 paths = nx.all_pairs_dijkstra_path_length(G, weight=weight) | |
268 else: # method == 'bellman-ford': | |
269 paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight) | |
270 else: | |
271 # Find paths from all nodes co-accessible to the target. | |
272 if G.is_directed(): | |
273 G = G.reverse(copy=False) | |
274 if method == "unweighted": | |
275 path_length = nx.single_source_shortest_path_length | |
276 paths = path_length(G, target) | |
277 elif method == "dijkstra": | |
278 path_length = nx.single_source_dijkstra_path_length | |
279 paths = path_length(G, target, weight=weight) | |
280 else: # method == 'bellman-ford': | |
281 path_length = nx.single_source_bellman_ford_path_length | |
282 paths = path_length(G, target, weight=weight) | |
283 else: | |
284 if target is None: | |
285 # Find paths to all nodes accessible from the source. | |
286 if method == "unweighted": | |
287 paths = nx.single_source_shortest_path_length(G, source) | |
288 elif method == "dijkstra": | |
289 path_length = nx.single_source_dijkstra_path_length | |
290 paths = path_length(G, source, weight=weight) | |
291 else: # method == 'bellman-ford': | |
292 path_length = nx.single_source_bellman_ford_path_length | |
293 paths = path_length(G, source, weight=weight) | |
294 else: | |
295 # Find shortest source-target path. | |
296 if method == "unweighted": | |
297 p = nx.bidirectional_shortest_path(G, source, target) | |
298 paths = len(p) - 1 | |
299 elif method == "dijkstra": | |
300 paths = nx.dijkstra_path_length(G, source, target, weight) | |
301 else: # method == 'bellman-ford': | |
302 paths = nx.bellman_ford_path_length(G, source, target, weight) | |
303 return paths | |
304 | |
305 | |
306 def average_shortest_path_length(G, weight=None, method=None): | |
307 r"""Returns the average shortest path length. | |
308 | |
309 The average shortest path length is | |
310 | |
311 .. math:: | |
312 | |
313 a =\sum_{s,t \in V} \frac{d(s, t)}{n(n-1)} | |
314 | |
315 where `V` is the set of nodes in `G`, | |
316 `d(s, t)` is the shortest path from `s` to `t`, | |
317 and `n` is the number of nodes in `G`. | |
318 | |
319 Parameters | |
320 ---------- | |
321 G : NetworkX graph | |
322 | |
323 weight : None or string, optional (default = None) | |
324 If None, every edge has weight/distance/cost 1. | |
325 If a string, use this edge attribute as the edge weight. | |
326 Any edge attribute not present defaults to 1. | |
327 | |
328 method : string, optional (default = 'unweighted' or 'djikstra') | |
329 The algorithm to use to compute the path lengths. | |
330 Supported options are 'unweighted', 'dijkstra', 'bellman-ford', | |
331 'floyd-warshall' and 'floyd-warshall-numpy'. | |
332 Other method values produce a ValueError. | |
333 The default method is 'unweighted' if `weight` is None, | |
334 otherwise the default method is 'dijkstra'. | |
335 | |
336 Raises | |
337 ------ | |
338 NetworkXPointlessConcept | |
339 If `G` is the null graph (that is, the graph on zero nodes). | |
340 | |
341 NetworkXError | |
342 If `G` is not connected (or not weakly connected, in the case | |
343 of a directed graph). | |
344 | |
345 ValueError | |
346 If `method` is not among the supported options. | |
347 | |
348 Examples | |
349 -------- | |
350 >>> G = nx.path_graph(5) | |
351 >>> nx.average_shortest_path_length(G) | |
352 2.0 | |
353 | |
354 For disconnected graphs, you can compute the average shortest path | |
355 length for each component | |
356 | |
357 >>> G = nx.Graph([(1, 2), (3, 4)]) | |
358 >>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)): | |
359 ... print(nx.average_shortest_path_length(C)) | |
360 1.0 | |
361 1.0 | |
362 | |
363 """ | |
364 single_source_methods = ["unweighted", "dijkstra", "bellman-ford"] | |
365 all_pairs_methods = ["floyd-warshall", "floyd-warshall-numpy"] | |
366 supported_methods = single_source_methods + all_pairs_methods | |
367 | |
368 if method is None: | |
369 method = "unweighted" if weight is None else "dijkstra" | |
370 if method not in supported_methods: | |
371 raise ValueError(f"method not supported: {method}") | |
372 | |
373 n = len(G) | |
374 # For the special case of the null graph, raise an exception, since | |
375 # there are no paths in the null graph. | |
376 if n == 0: | |
377 msg = ( | |
378 "the null graph has no paths, thus there is no average" | |
379 "shortest path length" | |
380 ) | |
381 raise nx.NetworkXPointlessConcept(msg) | |
382 # For the special case of the trivial graph, return zero immediately. | |
383 if n == 1: | |
384 return 0 | |
385 # Shortest path length is undefined if the graph is disconnected. | |
386 if G.is_directed() and not nx.is_weakly_connected(G): | |
387 raise nx.NetworkXError("Graph is not weakly connected.") | |
388 if not G.is_directed() and not nx.is_connected(G): | |
389 raise nx.NetworkXError("Graph is not connected.") | |
390 | |
391 # Compute all-pairs shortest paths. | |
392 def path_length(v): | |
393 if method == "unweighted": | |
394 return nx.single_source_shortest_path_length(G, v) | |
395 elif method == "dijkstra": | |
396 return nx.single_source_dijkstra_path_length(G, v, weight=weight) | |
397 elif method == "bellman-ford": | |
398 return nx.single_source_bellman_ford_path_length(G, v, weight=weight) | |
399 | |
400 if method in single_source_methods: | |
401 # Sum the distances for each (ordered) pair of source and target node. | |
402 s = sum(l for u in G for l in path_length(u).values()) | |
403 else: | |
404 if method == "floyd-warshall": | |
405 all_pairs = nx.floyd_warshall(G, weight=weight) | |
406 s = sum([sum(t.values()) for t in all_pairs.values()]) | |
407 elif method == "floyd-warshall-numpy": | |
408 s = nx.floyd_warshall_numpy(G, weight=weight).sum() | |
409 return s / (n * (n - 1)) | |
410 | |
411 | |
412 def all_shortest_paths(G, source, target, weight=None, method="dijkstra"): | |
413 """Compute all shortest simple paths in the graph. | |
414 | |
415 Parameters | |
416 ---------- | |
417 G : NetworkX graph | |
418 | |
419 source : node | |
420 Starting node for path. | |
421 | |
422 target : node | |
423 Ending node for path. | |
424 | |
425 weight : None or string, optional (default = None) | |
426 If None, every edge has weight/distance/cost 1. | |
427 If a string, use this edge attribute as the edge weight. | |
428 Any edge attribute not present defaults to 1. | |
429 | |
430 method : string, optional (default = 'dijkstra') | |
431 The algorithm to use to compute the path lengths. | |
432 Supported options: 'dijkstra', 'bellman-ford'. | |
433 Other inputs produce a ValueError. | |
434 If `weight` is None, unweighted graph methods are used, and this | |
435 suggestion is ignored. | |
436 | |
437 Returns | |
438 ------- | |
439 paths : generator of lists | |
440 A generator of all paths between source and target. | |
441 | |
442 Raises | |
443 ------ | |
444 ValueError | |
445 If `method` is not among the supported options. | |
446 | |
447 NetworkXNoPath | |
448 If `target` cannot be reached from `source`. | |
449 | |
450 Examples | |
451 -------- | |
452 >>> G = nx.Graph() | |
453 >>> nx.add_path(G, [0, 1, 2]) | |
454 >>> nx.add_path(G, [0, 10, 2]) | |
455 >>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)]) | |
456 [[0, 1, 2], [0, 10, 2]] | |
457 | |
458 Notes | |
459 ----- | |
460 There may be many shortest paths between the source and target. If G | |
461 contains zero-weight cycles, this function will not produce all shortest | |
462 paths because doing so would produce infinitely many paths of unbounded | |
463 length -- instead, we only produce the shortest simple paths. | |
464 | |
465 See Also | |
466 -------- | |
467 shortest_path() | |
468 single_source_shortest_path() | |
469 all_pairs_shortest_path() | |
470 """ | |
471 method = "unweighted" if weight is None else method | |
472 if method == "unweighted": | |
473 pred = nx.predecessor(G, source) | |
474 elif method == "dijkstra": | |
475 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight) | |
476 elif method == "bellman-ford": | |
477 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight) | |
478 else: | |
479 raise ValueError(f"method not supported: {method}") | |
480 | |
481 return _build_paths_from_predecessors({source}, target, pred) | |
482 | |
483 | |
484 def _build_paths_from_predecessors(sources, target, pred): | |
485 """Compute all simple paths to target, given the predecessors found in | |
486 pred, terminating when any source in sources is found. | |
487 | |
488 Parameters | |
489 ---------- | |
490 sources : set | |
491 Starting nodes for path. | |
492 | |
493 target : node | |
494 Ending node for path. | |
495 | |
496 pred : dict | |
497 A dictionary of predecessor lists, keyed by node | |
498 | |
499 Returns | |
500 ------- | |
501 paths : generator of lists | |
502 A generator of all paths between source and target. | |
503 | |
504 Raises | |
505 ------ | |
506 NetworkXNoPath | |
507 If `target` cannot be reached from `source`. | |
508 | |
509 Notes | |
510 ----- | |
511 There may be many paths between the sources and target. If there are | |
512 cycles among the predecessors, this function will not produce all | |
513 possible paths because doing so would produce infinitely many paths | |
514 of unbounded length -- instead, we only produce simple paths. | |
515 | |
516 See Also | |
517 -------- | |
518 shortest_path() | |
519 single_source_shortest_path() | |
520 all_pairs_shortest_path() | |
521 all_shortest_paths() | |
522 bellman_ford_path() | |
523 """ | |
524 if target not in pred: | |
525 raise nx.NetworkXNoPath( | |
526 f"Target {target} cannot be reached" f"from given sources" | |
527 ) | |
528 | |
529 seen = {target} | |
530 stack = [[target, 0]] | |
531 top = 0 | |
532 while top >= 0: | |
533 node, i = stack[top] | |
534 if node in sources: | |
535 yield [p for p, n in reversed(stack[: top + 1])] | |
536 if len(pred[node]) > i: | |
537 stack[top][1] = i + 1 | |
538 next = pred[node][i] | |
539 if next in seen: | |
540 continue | |
541 else: | |
542 seen.add(next) | |
543 top += 1 | |
544 if top == len(stack): | |
545 stack.append([next, 0]) | |
546 else: | |
547 stack[top][:] = [next, 0] | |
548 else: | |
549 seen.discard(node) | |
550 top -= 1 |