Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/shortest_paths/generic.py: 11%
168 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Compute the shortest paths and path lengths between nodes in the graph.
4These algorithms work with undirected and directed graphs.
6"""
7import warnings
9import networkx as nx
11__all__ = [
12 "shortest_path",
13 "all_shortest_paths",
14 "single_source_all_shortest_paths",
15 "all_pairs_all_shortest_paths",
16 "shortest_path_length",
17 "average_shortest_path_length",
18 "has_path",
19]
22@nx._dispatch
23def has_path(G, source, target):
24 """Returns *True* if *G* has a path from *source* to *target*.
26 Parameters
27 ----------
28 G : NetworkX graph
30 source : node
31 Starting node for path
33 target : node
34 Ending node for path
35 """
36 try:
37 nx.shortest_path(G, source, target)
38 except nx.NetworkXNoPath:
39 return False
40 return True
43@nx._dispatch(edge_attrs="weight")
44def shortest_path(G, source=None, target=None, weight=None, method="dijkstra"):
45 """Compute shortest paths in the graph.
47 Parameters
48 ----------
49 G : NetworkX graph
51 source : node, optional
52 Starting node for path. If not specified, compute shortest
53 paths for each possible starting node.
55 target : node, optional
56 Ending node for path. If not specified, compute shortest
57 paths to all possible nodes.
59 weight : None, string or function, optional (default = None)
60 If None, every edge has weight/distance/cost 1.
61 If a string, use this edge attribute as the edge weight.
62 Any edge attribute not present defaults to 1.
63 If this is a function, the weight of an edge is the value
64 returned by the function. The function must accept exactly
65 three positional arguments: the two endpoints of an edge and
66 the dictionary of edge attributes for that edge.
67 The function must return a number.
69 method : string, optional (default = 'dijkstra')
70 The algorithm to use to compute the path.
71 Supported options: 'dijkstra', 'bellman-ford'.
72 Other inputs produce a ValueError.
73 If `weight` is None, unweighted graph methods are used, and this
74 suggestion is ignored.
76 Returns
77 -------
78 path: list or dictionary
79 All returned paths include both the source and target in the path.
81 If the source and target are both specified, return a single list
82 of nodes in a shortest path from the source to the target.
84 If only the source is specified, return a dictionary keyed by
85 targets with a list of nodes in a shortest path from the source
86 to one of the targets.
88 If only the target is specified, return a dictionary keyed by
89 sources with a list of nodes in a shortest path from one of the
90 sources to the target.
92 If neither the source nor target are specified return a dictionary
93 of dictionaries with path[source][target]=[list of nodes in path].
95 Raises
96 ------
97 NodeNotFound
98 If `source` is not in `G`.
100 ValueError
101 If `method` is not among the supported options.
103 Examples
104 --------
105 >>> G = nx.path_graph(5)
106 >>> print(nx.shortest_path(G, source=0, target=4))
107 [0, 1, 2, 3, 4]
108 >>> p = nx.shortest_path(G, source=0) # target not specified
109 >>> p[3] # shortest path from source=0 to target=3
110 [0, 1, 2, 3]
111 >>> p = nx.shortest_path(G, target=4) # source not specified
112 >>> p[1] # shortest path from source=1 to target=4
113 [1, 2, 3, 4]
114 >>> p = nx.shortest_path(G) # source, target not specified
115 >>> p[2][4] # shortest path from source=2 to target=4
116 [2, 3, 4]
118 Notes
119 -----
120 There may be more than one shortest path between a source and target.
121 This returns only one of them.
123 See Also
124 --------
125 all_pairs_shortest_path
126 all_pairs_dijkstra_path
127 all_pairs_bellman_ford_path
128 single_source_shortest_path
129 single_source_dijkstra_path
130 single_source_bellman_ford_path
131 """
132 if method not in ("dijkstra", "bellman-ford"):
133 # so we don't need to check in each branch later
134 raise ValueError(f"method not supported: {method}")
135 method = "unweighted" if weight is None else method
136 if source is None:
137 if target is None:
138 msg = "shortest_path for all_pairs will return an iterator in v3.3"
139 warnings.warn(msg, DeprecationWarning)
141 # Find paths between all pairs.
142 if method == "unweighted":
143 paths = dict(nx.all_pairs_shortest_path(G))
144 elif method == "dijkstra":
145 paths = dict(nx.all_pairs_dijkstra_path(G, weight=weight))
146 else: # method == 'bellman-ford':
147 paths = dict(nx.all_pairs_bellman_ford_path(G, weight=weight))
148 else:
149 # Find paths from all nodes co-accessible to the target.
150 if G.is_directed():
151 G = G.reverse(copy=False)
152 if method == "unweighted":
153 paths = nx.single_source_shortest_path(G, target)
154 elif method == "dijkstra":
155 paths = nx.single_source_dijkstra_path(G, target, weight=weight)
156 else: # method == 'bellman-ford':
157 paths = nx.single_source_bellman_ford_path(G, target, weight=weight)
158 # Now flip the paths so they go from a source to the target.
159 for target in paths:
160 paths[target] = list(reversed(paths[target]))
161 else:
162 if target is None:
163 # Find paths to all nodes accessible from the source.
164 if method == "unweighted":
165 paths = nx.single_source_shortest_path(G, source)
166 elif method == "dijkstra":
167 paths = nx.single_source_dijkstra_path(G, source, weight=weight)
168 else: # method == 'bellman-ford':
169 paths = nx.single_source_bellman_ford_path(G, source, weight=weight)
170 else:
171 # Find shortest source-target path.
172 if method == "unweighted":
173 paths = nx.bidirectional_shortest_path(G, source, target)
174 elif method == "dijkstra":
175 _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
176 else: # method == 'bellman-ford':
177 paths = nx.bellman_ford_path(G, source, target, weight)
178 return paths
181@nx._dispatch(edge_attrs="weight")
182def shortest_path_length(G, source=None, target=None, weight=None, method="dijkstra"):
183 """Compute shortest path lengths in the graph.
185 Parameters
186 ----------
187 G : NetworkX graph
189 source : node, optional
190 Starting node for path.
191 If not specified, compute shortest path lengths using all nodes as
192 source nodes.
194 target : node, optional
195 Ending node for path.
196 If not specified, compute shortest path lengths using all nodes as
197 target nodes.
199 weight : None, string or function, optional (default = None)
200 If None, every edge has weight/distance/cost 1.
201 If a string, use this edge attribute as the edge weight.
202 Any edge attribute not present defaults to 1.
203 If this is a function, the weight of an edge is the value
204 returned by the function. The function must accept exactly
205 three positional arguments: the two endpoints of an edge and
206 the dictionary of edge attributes for that edge.
207 The function must return a number.
209 method : string, optional (default = 'dijkstra')
210 The algorithm to use to compute the path length.
211 Supported options: 'dijkstra', 'bellman-ford'.
212 Other inputs produce a ValueError.
213 If `weight` is None, unweighted graph methods are used, and this
214 suggestion is ignored.
216 Returns
217 -------
218 length: int or iterator
219 If the source and target are both specified, return the length of
220 the shortest path from the source to the target.
222 If only the source is specified, return a dict keyed by target
223 to the shortest path length from the source to that target.
225 If only the target is specified, return a dict keyed by source
226 to the shortest path length from that source to the target.
228 If neither the source nor target are specified, return an iterator
229 over (source, dictionary) where dictionary is keyed by target to
230 shortest path length from source to that target.
232 Raises
233 ------
234 NodeNotFound
235 If `source` is not in `G`.
237 NetworkXNoPath
238 If no path exists between source and target.
240 ValueError
241 If `method` is not among the supported options.
243 Examples
244 --------
245 >>> G = nx.path_graph(5)
246 >>> nx.shortest_path_length(G, source=0, target=4)
247 4
248 >>> p = nx.shortest_path_length(G, source=0) # target not specified
249 >>> p[4]
250 4
251 >>> p = nx.shortest_path_length(G, target=4) # source not specified
252 >>> p[0]
253 4
254 >>> p = dict(nx.shortest_path_length(G)) # source,target not specified
255 >>> p[0][4]
256 4
258 Notes
259 -----
260 The length of the path is always 1 less than the number of nodes involved
261 in the path since the length measures the number of edges followed.
263 For digraphs this returns the shortest directed path length. To find path
264 lengths in the reverse direction use G.reverse(copy=False) first to flip
265 the edge orientation.
267 See Also
268 --------
269 all_pairs_shortest_path_length
270 all_pairs_dijkstra_path_length
271 all_pairs_bellman_ford_path_length
272 single_source_shortest_path_length
273 single_source_dijkstra_path_length
274 single_source_bellman_ford_path_length
275 """
276 if method not in ("dijkstra", "bellman-ford"):
277 # so we don't need to check in each branch later
278 raise ValueError(f"method not supported: {method}")
279 method = "unweighted" if weight is None else method
280 if source is None:
281 if target is None:
282 # Find paths between all pairs.
283 if method == "unweighted":
284 paths = nx.all_pairs_shortest_path_length(G)
285 elif method == "dijkstra":
286 paths = nx.all_pairs_dijkstra_path_length(G, weight=weight)
287 else: # method == 'bellman-ford':
288 paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
289 else:
290 # Find paths from all nodes co-accessible to the target.
291 if G.is_directed():
292 G = G.reverse(copy=False)
293 if method == "unweighted":
294 path_length = nx.single_source_shortest_path_length
295 paths = path_length(G, target)
296 elif method == "dijkstra":
297 path_length = nx.single_source_dijkstra_path_length
298 paths = path_length(G, target, weight=weight)
299 else: # method == 'bellman-ford':
300 path_length = nx.single_source_bellman_ford_path_length
301 paths = path_length(G, target, weight=weight)
302 else:
303 if target is None:
304 # Find paths to all nodes accessible from the source.
305 if method == "unweighted":
306 paths = nx.single_source_shortest_path_length(G, source)
307 elif method == "dijkstra":
308 path_length = nx.single_source_dijkstra_path_length
309 paths = path_length(G, source, weight=weight)
310 else: # method == 'bellman-ford':
311 path_length = nx.single_source_bellman_ford_path_length
312 paths = path_length(G, source, weight=weight)
313 else:
314 # Find shortest source-target path.
315 if method == "unweighted":
316 p = nx.bidirectional_shortest_path(G, source, target)
317 paths = len(p) - 1
318 elif method == "dijkstra":
319 paths = nx.dijkstra_path_length(G, source, target, weight)
320 else: # method == 'bellman-ford':
321 paths = nx.bellman_ford_path_length(G, source, target, weight)
322 return paths
325@nx._dispatch(edge_attrs="weight")
326def average_shortest_path_length(G, weight=None, method=None):
327 r"""Returns the average shortest path length.
329 The average shortest path length is
331 .. math::
333 a =\sum_{\substack{s,t \in V \\ s\neq t}} \frac{d(s, t)}{n(n-1)}
335 where `V` is the set of nodes in `G`,
336 `d(s, t)` is the shortest path from `s` to `t`,
337 and `n` is the number of nodes in `G`.
339 .. versionchanged:: 3.0
340 An exception is raised for directed graphs that are not strongly
341 connected.
343 Parameters
344 ----------
345 G : NetworkX graph
347 weight : None, string or function, optional (default = None)
348 If None, every edge has weight/distance/cost 1.
349 If a string, use this edge attribute as the edge weight.
350 Any edge attribute not present defaults to 1.
351 If this is a function, the weight of an edge is the value
352 returned by the function. The function must accept exactly
353 three positional arguments: the two endpoints of an edge and
354 the dictionary of edge attributes for that edge.
355 The function must return a number.
357 method : string, optional (default = 'unweighted' or 'dijkstra')
358 The algorithm to use to compute the path lengths.
359 Supported options are 'unweighted', 'dijkstra', 'bellman-ford',
360 'floyd-warshall' and 'floyd-warshall-numpy'.
361 Other method values produce a ValueError.
362 The default method is 'unweighted' if `weight` is None,
363 otherwise the default method is 'dijkstra'.
365 Raises
366 ------
367 NetworkXPointlessConcept
368 If `G` is the null graph (that is, the graph on zero nodes).
370 NetworkXError
371 If `G` is not connected (or not strongly connected, in the case
372 of a directed graph).
374 ValueError
375 If `method` is not among the supported options.
377 Examples
378 --------
379 >>> G = nx.path_graph(5)
380 >>> nx.average_shortest_path_length(G)
381 2.0
383 For disconnected graphs, you can compute the average shortest path
384 length for each component
386 >>> G = nx.Graph([(1, 2), (3, 4)])
387 >>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
388 ... print(nx.average_shortest_path_length(C))
389 1.0
390 1.0
392 """
393 single_source_methods = ["unweighted", "dijkstra", "bellman-ford"]
394 all_pairs_methods = ["floyd-warshall", "floyd-warshall-numpy"]
395 supported_methods = single_source_methods + all_pairs_methods
397 if method is None:
398 method = "unweighted" if weight is None else "dijkstra"
399 if method not in supported_methods:
400 raise ValueError(f"method not supported: {method}")
402 n = len(G)
403 # For the special case of the null graph, raise an exception, since
404 # there are no paths in the null graph.
405 if n == 0:
406 msg = (
407 "the null graph has no paths, thus there is no average "
408 "shortest path length"
409 )
410 raise nx.NetworkXPointlessConcept(msg)
411 # For the special case of the trivial graph, return zero immediately.
412 if n == 1:
413 return 0
414 # Shortest path length is undefined if the graph is not strongly connected.
415 if G.is_directed() and not nx.is_strongly_connected(G):
416 raise nx.NetworkXError("Graph is not strongly connected.")
417 # Shortest path length is undefined if the graph is not connected.
418 if not G.is_directed() and not nx.is_connected(G):
419 raise nx.NetworkXError("Graph is not connected.")
421 # Compute all-pairs shortest paths.
422 def path_length(v):
423 if method == "unweighted":
424 return nx.single_source_shortest_path_length(G, v)
425 elif method == "dijkstra":
426 return nx.single_source_dijkstra_path_length(G, v, weight=weight)
427 elif method == "bellman-ford":
428 return nx.single_source_bellman_ford_path_length(G, v, weight=weight)
430 if method in single_source_methods:
431 # Sum the distances for each (ordered) pair of source and target node.
432 s = sum(l for u in G for l in path_length(u).values())
433 else:
434 if method == "floyd-warshall":
435 all_pairs = nx.floyd_warshall(G, weight=weight)
436 s = sum(sum(t.values()) for t in all_pairs.values())
437 elif method == "floyd-warshall-numpy":
438 s = nx.floyd_warshall_numpy(G, weight=weight).sum()
439 return s / (n * (n - 1))
442@nx._dispatch(edge_attrs="weight")
443def all_shortest_paths(G, source, target, weight=None, method="dijkstra"):
444 """Compute all shortest simple paths in the graph.
446 Parameters
447 ----------
448 G : NetworkX graph
450 source : node
451 Starting node for path.
453 target : node
454 Ending node for path.
456 weight : None, string or function, optional (default = None)
457 If None, every edge has weight/distance/cost 1.
458 If a string, use this edge attribute as the edge weight.
459 Any edge attribute not present defaults to 1.
460 If this is a function, the weight of an edge is the value
461 returned by the function. The function must accept exactly
462 three positional arguments: the two endpoints of an edge and
463 the dictionary of edge attributes for that edge.
464 The function must return a number.
466 method : string, optional (default = 'dijkstra')
467 The algorithm to use to compute the path lengths.
468 Supported options: 'dijkstra', 'bellman-ford'.
469 Other inputs produce a ValueError.
470 If `weight` is None, unweighted graph methods are used, and this
471 suggestion is ignored.
473 Returns
474 -------
475 paths : generator of lists
476 A generator of all paths between source and target.
478 Raises
479 ------
480 ValueError
481 If `method` is not among the supported options.
483 NetworkXNoPath
484 If `target` cannot be reached from `source`.
486 Examples
487 --------
488 >>> G = nx.Graph()
489 >>> nx.add_path(G, [0, 1, 2])
490 >>> nx.add_path(G, [0, 10, 2])
491 >>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])
492 [[0, 1, 2], [0, 10, 2]]
494 Notes
495 -----
496 There may be many shortest paths between the source and target. If G
497 contains zero-weight cycles, this function will not produce all shortest
498 paths because doing so would produce infinitely many paths of unbounded
499 length -- instead, we only produce the shortest simple paths.
501 See Also
502 --------
503 shortest_path
504 single_source_shortest_path
505 all_pairs_shortest_path
506 """
507 method = "unweighted" if weight is None else method
508 if method == "unweighted":
509 pred = nx.predecessor(G, source)
510 elif method == "dijkstra":
511 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
512 elif method == "bellman-ford":
513 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
514 else:
515 raise ValueError(f"method not supported: {method}")
517 return _build_paths_from_predecessors({source}, target, pred)
520@nx._dispatch(edge_attrs="weight")
521def single_source_all_shortest_paths(G, source, weight=None, method="dijkstra"):
522 """Compute all shortest simple paths from the given source in the graph.
524 Parameters
525 ----------
526 G : NetworkX graph
528 source : node
529 Starting node for path.
531 weight : None, string or function, optional (default = None)
532 If None, every edge has weight/distance/cost 1.
533 If a string, use this edge attribute as the edge weight.
534 Any edge attribute not present defaults to 1.
535 If this is a function, the weight of an edge is the value
536 returned by the function. The function must accept exactly
537 three positional arguments: the two endpoints of an edge and
538 the dictionary of edge attributes for that edge.
539 The function must return a number.
541 method : string, optional (default = 'dijkstra')
542 The algorithm to use to compute the path lengths.
543 Supported options: 'dijkstra', 'bellman-ford'.
544 Other inputs produce a ValueError.
545 If `weight` is None, unweighted graph methods are used, and this
546 suggestion is ignored.
548 Returns
549 -------
550 paths : generator of dictionary
551 A generator of all paths between source and all nodes in the graph.
553 Raises
554 ------
555 ValueError
556 If `method` is not among the supported options.
558 Examples
559 --------
560 >>> G = nx.Graph()
561 >>> nx.add_path(G, [0, 1, 2, 3, 0])
562 >>> dict(nx.single_source_all_shortest_paths(G, source=0))
563 {0: [[0]], 1: [[0, 1]], 2: [[0, 1, 2], [0, 3, 2]], 3: [[0, 3]]}
565 Notes
566 -----
567 There may be many shortest paths between the source and target. If G
568 contains zero-weight cycles, this function will not produce all shortest
569 paths because doing so would produce infinitely many paths of unbounded
570 length -- instead, we only produce the shortest simple paths.
572 See Also
573 --------
574 shortest_path
575 all_shortest_paths
576 single_source_shortest_path
577 all_pairs_shortest_path
578 all_pairs_all_shortest_paths
579 """
580 method = "unweighted" if weight is None else method
581 if method == "unweighted":
582 pred = nx.predecessor(G, source)
583 elif method == "dijkstra":
584 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
585 elif method == "bellman-ford":
586 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
587 else:
588 raise ValueError(f"method not supported: {method}")
589 for n in G:
590 try:
591 yield n, list(_build_paths_from_predecessors({source}, n, pred))
592 except nx.NetworkXNoPath:
593 pass
596@nx._dispatch(edge_attrs="weight")
597def all_pairs_all_shortest_paths(G, weight=None, method="dijkstra"):
598 """Compute all shortest paths between all nodes.
600 Parameters
601 ----------
602 G : NetworkX graph
604 weight : None, string or function, optional (default = None)
605 If None, every edge has weight/distance/cost 1.
606 If a string, use this edge attribute as the edge weight.
607 Any edge attribute not present defaults to 1.
608 If this is a function, the weight of an edge is the value
609 returned by the function. The function must accept exactly
610 three positional arguments: the two endpoints of an edge and
611 the dictionary of edge attributes for that edge.
612 The function must return a number.
614 method : string, optional (default = 'dijkstra')
615 The algorithm to use to compute the path lengths.
616 Supported options: 'dijkstra', 'bellman-ford'.
617 Other inputs produce a ValueError.
618 If `weight` is None, unweighted graph methods are used, and this
619 suggestion is ignored.
621 Returns
622 -------
623 paths : generator of dictionary
624 Dictionary of arrays, keyed by source and target, of all shortest paths.
626 Raises
627 ------
628 ValueError
629 If `method` is not among the supported options.
631 Examples
632 --------
633 >>> G = nx.cycle_graph(4)
634 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][2]
635 [[0, 1, 2], [0, 3, 2]]
636 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][3]
637 [[0, 3]]
639 Notes
640 -----
641 There may be multiple shortest paths with equal lengths. Unlike
642 all_pairs_shortest_path, this method returns all shortest paths.
644 See Also
645 --------
646 all_pairs_shortest_path
647 single_source_all_shortest_paths
648 """
649 for n in G:
650 yield n, dict(
651 single_source_all_shortest_paths(G, n, weight=weight, method=method)
652 )
655def _build_paths_from_predecessors(sources, target, pred):
656 """Compute all simple paths to target, given the predecessors found in
657 pred, terminating when any source in sources is found.
659 Parameters
660 ----------
661 sources : set
662 Starting nodes for path.
664 target : node
665 Ending node for path.
667 pred : dict
668 A dictionary of predecessor lists, keyed by node
670 Returns
671 -------
672 paths : generator of lists
673 A generator of all paths between source and target.
675 Raises
676 ------
677 NetworkXNoPath
678 If `target` cannot be reached from `source`.
680 Notes
681 -----
682 There may be many paths between the sources and target. If there are
683 cycles among the predecessors, this function will not produce all
684 possible paths because doing so would produce infinitely many paths
685 of unbounded length -- instead, we only produce simple paths.
687 See Also
688 --------
689 shortest_path
690 single_source_shortest_path
691 all_pairs_shortest_path
692 all_shortest_paths
693 bellman_ford_path
694 """
695 if target not in pred:
696 raise nx.NetworkXNoPath(f"Target {target} cannot be reached from given sources")
698 seen = {target}
699 stack = [[target, 0]]
700 top = 0
701 while top >= 0:
702 node, i = stack[top]
703 if node in sources:
704 yield [p for p, n in reversed(stack[: top + 1])]
705 if len(pred[node]) > i:
706 stack[top][1] = i + 1
707 next = pred[node][i]
708 if next in seen:
709 continue
710 else:
711 seen.add(next)
712 top += 1
713 if top == len(stack):
714 stack.append([next, 0])
715 else:
716 stack[top][:] = [next, 0]
717 else:
718 seen.discard(node)
719 top -= 1