Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/simple_paths.py: 8%
352 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1from heapq import heappop, heappush
2from itertools import count
4import networkx as nx
5from networkx.algorithms.shortest_paths.weighted import _weight_function
6from networkx.utils import not_implemented_for, pairwise
8__all__ = [
9 "all_simple_paths",
10 "is_simple_path",
11 "shortest_simple_paths",
12 "all_simple_edge_paths",
13]
16@nx._dispatch
17def is_simple_path(G, nodes):
18 """Returns True if and only if `nodes` form a simple path in `G`.
20 A *simple path* in a graph is a nonempty sequence of nodes in which
21 no node appears more than once in the sequence, and each adjacent
22 pair of nodes in the sequence is adjacent in the graph.
24 Parameters
25 ----------
26 G : graph
27 A NetworkX graph.
28 nodes : list
29 A list of one or more nodes in the graph `G`.
31 Returns
32 -------
33 bool
34 Whether the given list of nodes represents a simple path in `G`.
36 Notes
37 -----
38 An empty list of nodes is not a path but a list of one node is a
39 path. Here's an explanation why.
41 This function operates on *node paths*. One could also consider
42 *edge paths*. There is a bijection between node paths and edge
43 paths.
45 The *length of a path* is the number of edges in the path, so a list
46 of nodes of length *n* corresponds to a path of length *n* - 1.
47 Thus the smallest edge path would be a list of zero edges, the empty
48 path. This corresponds to a list of one node.
50 To convert between a node path and an edge path, you can use code
51 like the following::
53 >>> from networkx.utils import pairwise
54 >>> nodes = [0, 1, 2, 3]
55 >>> edges = list(pairwise(nodes))
56 >>> edges
57 [(0, 1), (1, 2), (2, 3)]
58 >>> nodes = [edges[0][0]] + [v for u, v in edges]
59 >>> nodes
60 [0, 1, 2, 3]
62 Examples
63 --------
64 >>> G = nx.cycle_graph(4)
65 >>> nx.is_simple_path(G, [2, 3, 0])
66 True
67 >>> nx.is_simple_path(G, [0, 2])
68 False
70 """
71 # The empty list is not a valid path. Could also return
72 # NetworkXPointlessConcept here.
73 if len(nodes) == 0:
74 return False
76 # If the list is a single node, just check that the node is actually
77 # in the graph.
78 if len(nodes) == 1:
79 return nodes[0] in G
81 # check that all nodes in the list are in the graph, if at least one
82 # is not in the graph, then this is not a simple path
83 if not all(n in G for n in nodes):
84 return False
86 # If the list contains repeated nodes, then it's not a simple path
87 if len(set(nodes)) != len(nodes):
88 return False
90 # Test that each adjacent pair of nodes is adjacent.
91 return all(v in G[u] for u, v in pairwise(nodes))
94@nx._dispatch
95def all_simple_paths(G, source, target, cutoff=None):
96 """Generate all simple paths in the graph G from source to target.
98 A simple path is a path with no repeated nodes.
100 Parameters
101 ----------
102 G : NetworkX graph
104 source : node
105 Starting node for path
107 target : nodes
108 Single node or iterable of nodes at which to end path
110 cutoff : integer, optional
111 Depth to stop the search. Only paths of length <= cutoff are returned.
113 Returns
114 -------
115 path_generator: generator
116 A generator that produces lists of simple paths. If there are no paths
117 between the source and target within the given cutoff the generator
118 produces no output. If it is possible to traverse the same sequence of
119 nodes in multiple ways, namely through parallel edges, then it will be
120 returned multiple times (once for each viable edge combination).
122 Examples
123 --------
124 This iterator generates lists of nodes::
126 >>> G = nx.complete_graph(4)
127 >>> for path in nx.all_simple_paths(G, source=0, target=3):
128 ... print(path)
129 ...
130 [0, 1, 2, 3]
131 [0, 1, 3]
132 [0, 2, 1, 3]
133 [0, 2, 3]
134 [0, 3]
136 You can generate only those paths that are shorter than a certain
137 length by using the `cutoff` keyword argument::
139 >>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)
140 >>> print(list(paths))
141 [[0, 1, 3], [0, 2, 3], [0, 3]]
143 To get each path as the corresponding list of edges, you can use the
144 :func:`networkx.utils.pairwise` helper function::
146 >>> paths = nx.all_simple_paths(G, source=0, target=3)
147 >>> for path in map(nx.utils.pairwise, paths):
148 ... print(list(path))
149 [(0, 1), (1, 2), (2, 3)]
150 [(0, 1), (1, 3)]
151 [(0, 2), (2, 1), (1, 3)]
152 [(0, 2), (2, 3)]
153 [(0, 3)]
155 Pass an iterable of nodes as target to generate all paths ending in any of several nodes::
157 >>> G = nx.complete_graph(4)
158 >>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]):
159 ... print(path)
160 ...
161 [0, 1, 2]
162 [0, 1, 2, 3]
163 [0, 1, 3]
164 [0, 1, 3, 2]
165 [0, 2]
166 [0, 2, 1, 3]
167 [0, 2, 3]
168 [0, 3]
169 [0, 3, 1, 2]
170 [0, 3, 2]
172 Iterate over each path from the root nodes to the leaf nodes in a
173 directed acyclic graph using a functional programming approach::
175 >>> from itertools import chain
176 >>> from itertools import product
177 >>> from itertools import starmap
178 >>> from functools import partial
179 >>>
180 >>> chaini = chain.from_iterable
181 >>>
182 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
183 >>> roots = (v for v, d in G.in_degree() if d == 0)
184 >>> leaves = (v for v, d in G.out_degree() if d == 0)
185 >>> all_paths = partial(nx.all_simple_paths, G)
186 >>> list(chaini(starmap(all_paths, product(roots, leaves))))
187 [[0, 1, 2], [0, 3, 2]]
189 The same list computed using an iterative approach::
191 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
192 >>> roots = (v for v, d in G.in_degree() if d == 0)
193 >>> leaves = (v for v, d in G.out_degree() if d == 0)
194 >>> all_paths = []
195 >>> for root in roots:
196 ... for leaf in leaves:
197 ... paths = nx.all_simple_paths(G, root, leaf)
198 ... all_paths.extend(paths)
199 >>> all_paths
200 [[0, 1, 2], [0, 3, 2]]
202 Iterate over each path from the root nodes to the leaf nodes in a
203 directed acyclic graph passing all leaves together to avoid unnecessary
204 compute::
206 >>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])
207 >>> roots = (v for v, d in G.in_degree() if d == 0)
208 >>> leaves = [v for v, d in G.out_degree() if d == 0]
209 >>> all_paths = []
210 >>> for root in roots:
211 ... paths = nx.all_simple_paths(G, root, leaves)
212 ... all_paths.extend(paths)
213 >>> all_paths
214 [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]
216 If parallel edges offer multiple ways to traverse a given sequence of
217 nodes, this sequence of nodes will be returned multiple times:
219 >>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)])
220 >>> list(nx.all_simple_paths(G, 0, 2))
221 [[0, 1, 2], [0, 1, 2]]
223 Notes
224 -----
225 This algorithm uses a modified depth-first search to generate the
226 paths [1]_. A single path can be found in $O(V+E)$ time but the
227 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
228 the complete graph of order $n$.
230 This function does not check that a path exists between `source` and
231 `target`. For large graphs, this may result in very long runtimes.
232 Consider using `has_path` to check that a path exists between `source` and
233 `target` before calling this function on large graphs.
235 References
236 ----------
237 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
238 Addison Wesley Professional, 3rd ed., 2001.
240 See Also
241 --------
242 all_shortest_paths, shortest_path, has_path
244 """
245 if source not in G:
246 raise nx.NodeNotFound(f"source node {source} not in graph")
247 if target in G:
248 targets = {target}
249 else:
250 try:
251 targets = set(target)
252 except TypeError as err:
253 raise nx.NodeNotFound(f"target node {target} not in graph") from err
254 if source in targets:
255 return _empty_generator()
256 if cutoff is None:
257 cutoff = len(G) - 1
258 if cutoff < 1:
259 return _empty_generator()
260 if G.is_multigraph():
261 return _all_simple_paths_multigraph(G, source, targets, cutoff)
262 else:
263 return _all_simple_paths_graph(G, source, targets, cutoff)
266def _empty_generator():
267 yield from ()
270def _all_simple_paths_graph(G, source, targets, cutoff):
271 visited = {source: True}
272 stack = [iter(G[source])]
273 while stack:
274 children = stack[-1]
275 child = next(children, None)
276 if child is None:
277 stack.pop()
278 visited.popitem()
279 elif len(visited) < cutoff:
280 if child in visited:
281 continue
282 if child in targets:
283 yield list(visited) + [child]
284 visited[child] = True
285 if targets - set(visited.keys()): # expand stack until find all targets
286 stack.append(iter(G[child]))
287 else:
288 visited.popitem() # maybe other ways to child
289 else: # len(visited) == cutoff:
290 for target in (targets & (set(children) | {child})) - set(visited.keys()):
291 yield list(visited) + [target]
292 stack.pop()
293 visited.popitem()
296def _all_simple_paths_multigraph(G, source, targets, cutoff):
297 visited = {source: True}
298 stack = [(v for u, v in G.edges(source))]
299 while stack:
300 children = stack[-1]
301 child = next(children, None)
302 if child is None:
303 stack.pop()
304 visited.popitem()
305 elif len(visited) < cutoff:
306 if child in visited:
307 continue
308 if child in targets:
309 yield list(visited) + [child]
310 visited[child] = True
311 if targets - set(visited.keys()):
312 stack.append((v for u, v in G.edges(child)))
313 else:
314 visited.popitem()
315 else: # len(visited) == cutoff:
316 for target in targets - set(visited.keys()):
317 count = ([child] + list(children)).count(target)
318 for i in range(count):
319 yield list(visited) + [target]
320 stack.pop()
321 visited.popitem()
324@nx._dispatch
325def all_simple_edge_paths(G, source, target, cutoff=None):
326 """Generate lists of edges for all simple paths in G from source to target.
328 A simple path is a path with no repeated nodes.
330 Parameters
331 ----------
332 G : NetworkX graph
334 source : node
335 Starting node for path
337 target : nodes
338 Single node or iterable of nodes at which to end path
340 cutoff : integer, optional
341 Depth to stop the search. Only paths of length <= cutoff are returned.
343 Returns
344 -------
345 path_generator: generator
346 A generator that produces lists of simple paths. If there are no paths
347 between the source and target within the given cutoff the generator
348 produces no output.
349 For multigraphs, the list of edges have elements of the form `(u,v,k)`.
350 Where `k` corresponds to the edge key.
352 Examples
353 --------
355 Print the simple path edges of a Graph::
357 >>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
358 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
359 ... print(path)
360 [(1, 2), (2, 4)]
361 [(1, 3), (3, 4)]
363 Print the simple path edges of a MultiGraph. Returned edges come with
364 their associated keys::
366 >>> mg = nx.MultiGraph()
367 >>> mg.add_edge(1, 2, key="k0")
368 'k0'
369 >>> mg.add_edge(1, 2, key="k1")
370 'k1'
371 >>> mg.add_edge(2, 3, key="k0")
372 'k0'
373 >>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
374 ... print(path)
375 [(1, 2, 'k0'), (2, 3, 'k0')]
376 [(1, 2, 'k1'), (2, 3, 'k0')]
379 Notes
380 -----
381 This algorithm uses a modified depth-first search to generate the
382 paths [1]_. A single path can be found in $O(V+E)$ time but the
383 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
384 the complete graph of order $n$.
386 References
387 ----------
388 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
389 Addison Wesley Professional, 3rd ed., 2001.
391 See Also
392 --------
393 all_shortest_paths, shortest_path, all_simple_paths
395 """
396 if source not in G:
397 raise nx.NodeNotFound("source node %s not in graph" % source)
398 if target in G:
399 targets = {target}
400 else:
401 try:
402 targets = set(target)
403 except TypeError:
404 raise nx.NodeNotFound("target node %s not in graph" % target)
405 if source in targets:
406 return []
407 if cutoff is None:
408 cutoff = len(G) - 1
409 if cutoff < 1:
410 return []
411 if G.is_multigraph():
412 for simp_path in _all_simple_edge_paths_multigraph(G, source, targets, cutoff):
413 yield simp_path
414 else:
415 for simp_path in _all_simple_paths_graph(G, source, targets, cutoff):
416 yield list(zip(simp_path[:-1], simp_path[1:]))
419def _all_simple_edge_paths_multigraph(G, source, targets, cutoff):
420 if not cutoff or cutoff < 1:
421 return []
422 visited = [source]
423 stack = [iter(G.edges(source, keys=True))]
425 while stack:
426 children = stack[-1]
427 child = next(children, None)
428 if child is None:
429 stack.pop()
430 visited.pop()
431 elif len(visited) < cutoff:
432 if child[1] in targets:
433 yield visited[1:] + [child]
434 elif child[1] not in [v[0] for v in visited[1:]]:
435 visited.append(child)
436 stack.append(iter(G.edges(child[1], keys=True)))
437 else: # len(visited) == cutoff:
438 for u, v, k in [child] + list(children):
439 if v in targets:
440 yield visited[1:] + [(u, v, k)]
441 stack.pop()
442 visited.pop()
445@not_implemented_for("multigraph")
446@nx._dispatch(edge_attrs="weight")
447def shortest_simple_paths(G, source, target, weight=None):
448 """Generate all simple paths in the graph G from source to target,
449 starting from shortest ones.
451 A simple path is a path with no repeated nodes.
453 If a weighted shortest path search is to be used, no negative weights
454 are allowed.
456 Parameters
457 ----------
458 G : NetworkX graph
460 source : node
461 Starting node for path
463 target : node
464 Ending node for path
466 weight : string or function
467 If it is a string, it is the name of the edge attribute to be
468 used as a weight.
470 If it is a function, the weight of an edge is the value returned
471 by the function. The function must accept exactly three positional
472 arguments: the two endpoints of an edge and the dictionary of edge
473 attributes for that edge. The function must return a number.
475 If None all edges are considered to have unit weight. Default
476 value None.
478 Returns
479 -------
480 path_generator: generator
481 A generator that produces lists of simple paths, in order from
482 shortest to longest.
484 Raises
485 ------
486 NetworkXNoPath
487 If no path exists between source and target.
489 NetworkXError
490 If source or target nodes are not in the input graph.
492 NetworkXNotImplemented
493 If the input graph is a Multi[Di]Graph.
495 Examples
496 --------
498 >>> G = nx.cycle_graph(7)
499 >>> paths = list(nx.shortest_simple_paths(G, 0, 3))
500 >>> print(paths)
501 [[0, 1, 2, 3], [0, 6, 5, 4, 3]]
503 You can use this function to efficiently compute the k shortest/best
504 paths between two nodes.
506 >>> from itertools import islice
507 >>> def k_shortest_paths(G, source, target, k, weight=None):
508 ... return list(
509 ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)
510 ... )
511 >>> for path in k_shortest_paths(G, 0, 3, 2):
512 ... print(path)
513 [0, 1, 2, 3]
514 [0, 6, 5, 4, 3]
516 Notes
517 -----
518 This procedure is based on algorithm by Jin Y. Yen [1]_. Finding
519 the first $K$ paths requires $O(KN^3)$ operations.
521 See Also
522 --------
523 all_shortest_paths
524 shortest_path
525 all_simple_paths
527 References
528 ----------
529 .. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a
530 Network", Management Science, Vol. 17, No. 11, Theory Series
531 (Jul., 1971), pp. 712-716.
533 """
534 if source not in G:
535 raise nx.NodeNotFound(f"source node {source} not in graph")
537 if target not in G:
538 raise nx.NodeNotFound(f"target node {target} not in graph")
540 if weight is None:
541 length_func = len
542 shortest_path_func = _bidirectional_shortest_path
543 else:
544 wt = _weight_function(G, weight)
546 def length_func(path):
547 return sum(
548 wt(u, v, G.get_edge_data(u, v)) for (u, v) in zip(path, path[1:])
549 )
551 shortest_path_func = _bidirectional_dijkstra
553 listA = []
554 listB = PathBuffer()
555 prev_path = None
556 while True:
557 if not prev_path:
558 length, path = shortest_path_func(G, source, target, weight=weight)
559 listB.push(length, path)
560 else:
561 ignore_nodes = set()
562 ignore_edges = set()
563 for i in range(1, len(prev_path)):
564 root = prev_path[:i]
565 root_length = length_func(root)
566 for path in listA:
567 if path[:i] == root:
568 ignore_edges.add((path[i - 1], path[i]))
569 try:
570 length, spur = shortest_path_func(
571 G,
572 root[-1],
573 target,
574 ignore_nodes=ignore_nodes,
575 ignore_edges=ignore_edges,
576 weight=weight,
577 )
578 path = root[:-1] + spur
579 listB.push(root_length + length, path)
580 except nx.NetworkXNoPath:
581 pass
582 ignore_nodes.add(root[-1])
584 if listB:
585 path = listB.pop()
586 yield path
587 listA.append(path)
588 prev_path = path
589 else:
590 break
593class PathBuffer:
594 def __init__(self):
595 self.paths = set()
596 self.sortedpaths = []
597 self.counter = count()
599 def __len__(self):
600 return len(self.sortedpaths)
602 def push(self, cost, path):
603 hashable_path = tuple(path)
604 if hashable_path not in self.paths:
605 heappush(self.sortedpaths, (cost, next(self.counter), path))
606 self.paths.add(hashable_path)
608 def pop(self):
609 (cost, num, path) = heappop(self.sortedpaths)
610 hashable_path = tuple(path)
611 self.paths.remove(hashable_path)
612 return path
615def _bidirectional_shortest_path(
616 G, source, target, ignore_nodes=None, ignore_edges=None, weight=None
617):
618 """Returns the shortest path between source and target ignoring
619 nodes and edges in the containers ignore_nodes and ignore_edges.
621 This is a custom modification of the standard bidirectional shortest
622 path implementation at networkx.algorithms.unweighted
624 Parameters
625 ----------
626 G : NetworkX graph
628 source : node
629 starting node for path
631 target : node
632 ending node for path
634 ignore_nodes : container of nodes
635 nodes to ignore, optional
637 ignore_edges : container of edges
638 edges to ignore, optional
640 weight : None
641 This function accepts a weight argument for convenience of
642 shortest_simple_paths function. It will be ignored.
644 Returns
645 -------
646 path: list
647 List of nodes in a path from source to target.
649 Raises
650 ------
651 NetworkXNoPath
652 If no path exists between source and target.
654 See Also
655 --------
656 shortest_path
658 """
659 # call helper to do the real work
660 results = _bidirectional_pred_succ(G, source, target, ignore_nodes, ignore_edges)
661 pred, succ, w = results
663 # build path from pred+w+succ
664 path = []
665 # from w to target
666 while w is not None:
667 path.append(w)
668 w = succ[w]
669 # from source to w
670 w = pred[path[0]]
671 while w is not None:
672 path.insert(0, w)
673 w = pred[w]
675 return len(path), path
678def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=None):
679 """Bidirectional shortest path helper.
680 Returns (pred,succ,w) where
681 pred is a dictionary of predecessors from w to the source, and
682 succ is a dictionary of successors from w to the target.
683 """
684 # does BFS from both source and target and meets in the middle
685 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
686 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
687 if target == source:
688 return ({target: None}, {source: None}, source)
690 # handle either directed or undirected
691 if G.is_directed():
692 Gpred = G.predecessors
693 Gsucc = G.successors
694 else:
695 Gpred = G.neighbors
696 Gsucc = G.neighbors
698 # support optional nodes filter
699 if ignore_nodes:
701 def filter_iter(nodes):
702 def iterate(v):
703 for w in nodes(v):
704 if w not in ignore_nodes:
705 yield w
707 return iterate
709 Gpred = filter_iter(Gpred)
710 Gsucc = filter_iter(Gsucc)
712 # support optional edges filter
713 if ignore_edges:
714 if G.is_directed():
716 def filter_pred_iter(pred_iter):
717 def iterate(v):
718 for w in pred_iter(v):
719 if (w, v) not in ignore_edges:
720 yield w
722 return iterate
724 def filter_succ_iter(succ_iter):
725 def iterate(v):
726 for w in succ_iter(v):
727 if (v, w) not in ignore_edges:
728 yield w
730 return iterate
732 Gpred = filter_pred_iter(Gpred)
733 Gsucc = filter_succ_iter(Gsucc)
735 else:
737 def filter_iter(nodes):
738 def iterate(v):
739 for w in nodes(v):
740 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
741 yield w
743 return iterate
745 Gpred = filter_iter(Gpred)
746 Gsucc = filter_iter(Gsucc)
748 # predecessor and successors in search
749 pred = {source: None}
750 succ = {target: None}
752 # initialize fringes, start with forward
753 forward_fringe = [source]
754 reverse_fringe = [target]
756 while forward_fringe and reverse_fringe:
757 if len(forward_fringe) <= len(reverse_fringe):
758 this_level = forward_fringe
759 forward_fringe = []
760 for v in this_level:
761 for w in Gsucc(v):
762 if w not in pred:
763 forward_fringe.append(w)
764 pred[w] = v
765 if w in succ:
766 # found path
767 return pred, succ, w
768 else:
769 this_level = reverse_fringe
770 reverse_fringe = []
771 for v in this_level:
772 for w in Gpred(v):
773 if w not in succ:
774 succ[w] = v
775 reverse_fringe.append(w)
776 if w in pred:
777 # found path
778 return pred, succ, w
780 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
783def _bidirectional_dijkstra(
784 G, source, target, weight="weight", ignore_nodes=None, ignore_edges=None
785):
786 """Dijkstra's algorithm for shortest paths using bidirectional search.
788 This function returns the shortest path between source and target
789 ignoring nodes and edges in the containers ignore_nodes and
790 ignore_edges.
792 This is a custom modification of the standard Dijkstra bidirectional
793 shortest path implementation at networkx.algorithms.weighted
795 Parameters
796 ----------
797 G : NetworkX graph
799 source : node
800 Starting node.
802 target : node
803 Ending node.
805 weight: string, function, optional (default='weight')
806 Edge data key or weight function corresponding to the edge weight
808 ignore_nodes : container of nodes
809 nodes to ignore, optional
811 ignore_edges : container of edges
812 edges to ignore, optional
814 Returns
815 -------
816 length : number
817 Shortest path length.
819 Returns a tuple of two dictionaries keyed by node.
820 The first dictionary stores distance from the source.
821 The second stores the path from the source to that node.
823 Raises
824 ------
825 NetworkXNoPath
826 If no path exists between source and target.
828 Notes
829 -----
830 Edge weight attributes must be numerical.
831 Distances are calculated as sums of weighted edges traversed.
833 In practice bidirectional Dijkstra is much more than twice as fast as
834 ordinary Dijkstra.
836 Ordinary Dijkstra expands nodes in a sphere-like manner from the
837 source. The radius of this sphere will eventually be the length
838 of the shortest path. Bidirectional Dijkstra will expand nodes
839 from both the source and the target, making two spheres of half
840 this radius. Volume of the first sphere is pi*r*r while the
841 others are 2*pi*r/2*r/2, making up half the volume.
843 This algorithm is not guaranteed to work if edge weights
844 are negative or are floating point numbers
845 (overflows and roundoff errors can cause problems).
847 See Also
848 --------
849 shortest_path
850 shortest_path_length
851 """
852 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
853 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
854 if source == target:
855 if source not in G:
856 raise nx.NodeNotFound(f"Node {source} not in graph")
857 return (0, [source])
859 # handle either directed or undirected
860 if G.is_directed():
861 Gpred = G.predecessors
862 Gsucc = G.successors
863 else:
864 Gpred = G.neighbors
865 Gsucc = G.neighbors
867 # support optional nodes filter
868 if ignore_nodes:
870 def filter_iter(nodes):
871 def iterate(v):
872 for w in nodes(v):
873 if w not in ignore_nodes:
874 yield w
876 return iterate
878 Gpred = filter_iter(Gpred)
879 Gsucc = filter_iter(Gsucc)
881 # support optional edges filter
882 if ignore_edges:
883 if G.is_directed():
885 def filter_pred_iter(pred_iter):
886 def iterate(v):
887 for w in pred_iter(v):
888 if (w, v) not in ignore_edges:
889 yield w
891 return iterate
893 def filter_succ_iter(succ_iter):
894 def iterate(v):
895 for w in succ_iter(v):
896 if (v, w) not in ignore_edges:
897 yield w
899 return iterate
901 Gpred = filter_pred_iter(Gpred)
902 Gsucc = filter_succ_iter(Gsucc)
904 else:
906 def filter_iter(nodes):
907 def iterate(v):
908 for w in nodes(v):
909 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
910 yield w
912 return iterate
914 Gpred = filter_iter(Gpred)
915 Gsucc = filter_iter(Gsucc)
917 push = heappush
918 pop = heappop
919 # Init: Forward Backward
920 dists = [{}, {}] # dictionary of final distances
921 paths = [{source: [source]}, {target: [target]}] # dictionary of paths
922 fringe = [[], []] # heap of (distance, node) tuples for
923 # extracting next node to expand
924 seen = [{source: 0}, {target: 0}] # dictionary of distances to
925 # nodes seen
926 c = count()
927 # initialize fringe heap
928 push(fringe[0], (0, next(c), source))
929 push(fringe[1], (0, next(c), target))
930 # neighs for extracting correct neighbor information
931 neighs = [Gsucc, Gpred]
932 # variables to hold shortest discovered path
933 # finaldist = 1e30000
934 finalpath = []
935 dir = 1
936 while fringe[0] and fringe[1]:
937 # choose direction
938 # dir == 0 is forward direction and dir == 1 is back
939 dir = 1 - dir
940 # extract closest to expand
941 (dist, _, v) = pop(fringe[dir])
942 if v in dists[dir]:
943 # Shortest path to v has already been found
944 continue
945 # update distance
946 dists[dir][v] = dist # equal to seen[dir][v]
947 if v in dists[1 - dir]:
948 # if we have scanned v in both directions we are done
949 # we have now discovered the shortest path
950 return (finaldist, finalpath)
952 wt = _weight_function(G, weight)
953 for w in neighs[dir](v):
954 if dir == 0: # forward
955 minweight = wt(v, w, G.get_edge_data(v, w))
956 vwLength = dists[dir][v] + minweight
957 else: # back, must remember to change v,w->w,v
958 minweight = wt(w, v, G.get_edge_data(w, v))
959 vwLength = dists[dir][v] + minweight
961 if w in dists[dir]:
962 if vwLength < dists[dir][w]:
963 raise ValueError("Contradictory paths found: negative weights?")
964 elif w not in seen[dir] or vwLength < seen[dir][w]:
965 # relaxing
966 seen[dir][w] = vwLength
967 push(fringe[dir], (vwLength, next(c), w))
968 paths[dir][w] = paths[dir][v] + [w]
969 if w in seen[0] and w in seen[1]:
970 # see if this path is better than the already
971 # discovered shortest path
972 totaldist = seen[0][w] + seen[1][w]
973 if finalpath == [] or finaldist > totaldist:
974 finaldist = totaldist
975 revpath = paths[1][w][:]
976 revpath.reverse()
977 finalpath = paths[0][w] + revpath[1:]
978 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")