Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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._dispatchable
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._dispatchable
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 The singleton path from ``source`` to itself is considered a simple path and is
173 included in the results:
175 >>> G = nx.empty_graph(5)
176 >>> list(nx.all_simple_paths(G, source=0, target=0))
177 [[0]]
179 >>> G = nx.path_graph(3)
180 >>> list(nx.all_simple_paths(G, source=0, target={0, 1, 2}))
181 [[0], [0, 1], [0, 1, 2]]
183 Iterate over each path from the root nodes to the leaf nodes in a
184 directed acyclic graph using a functional programming approach::
186 >>> from itertools import chain
187 >>> from itertools import product
188 >>> from itertools import starmap
189 >>> from functools import partial
190 >>>
191 >>> chaini = chain.from_iterable
192 >>>
193 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
194 >>> roots = (v for v, d in G.in_degree() if d == 0)
195 >>> leaves = (v for v, d in G.out_degree() if d == 0)
196 >>> all_paths = partial(nx.all_simple_paths, G)
197 >>> list(chaini(starmap(all_paths, product(roots, leaves))))
198 [[0, 1, 2], [0, 3, 2]]
200 The same list computed using an iterative approach::
202 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
203 >>> roots = (v for v, d in G.in_degree() if d == 0)
204 >>> leaves = (v for v, d in G.out_degree() if d == 0)
205 >>> all_paths = []
206 >>> for root in roots:
207 ... for leaf in leaves:
208 ... paths = nx.all_simple_paths(G, root, leaf)
209 ... all_paths.extend(paths)
210 >>> all_paths
211 [[0, 1, 2], [0, 3, 2]]
213 Iterate over each path from the root nodes to the leaf nodes in a
214 directed acyclic graph passing all leaves together to avoid unnecessary
215 compute::
217 >>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])
218 >>> roots = (v for v, d in G.in_degree() if d == 0)
219 >>> leaves = [v for v, d in G.out_degree() if d == 0]
220 >>> all_paths = []
221 >>> for root in roots:
222 ... paths = nx.all_simple_paths(G, root, leaves)
223 ... all_paths.extend(paths)
224 >>> all_paths
225 [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]
227 If parallel edges offer multiple ways to traverse a given sequence of
228 nodes, this sequence of nodes will be returned multiple times:
230 >>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)])
231 >>> list(nx.all_simple_paths(G, 0, 2))
232 [[0, 1, 2], [0, 1, 2]]
234 Notes
235 -----
236 This algorithm uses a modified depth-first search to generate the
237 paths [1]_. A single path can be found in $O(V+E)$ time but the
238 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
239 the complete graph of order $n$.
241 This function does not check that a path exists between `source` and
242 `target`. For large graphs, this may result in very long runtimes.
243 Consider using `has_path` to check that a path exists between `source` and
244 `target` before calling this function on large graphs.
246 References
247 ----------
248 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
249 Addison Wesley Professional, 3rd ed., 2001.
251 See Also
252 --------
253 all_shortest_paths, shortest_path, has_path
255 """
256 for edge_path in all_simple_edge_paths(G, source, target, cutoff):
257 yield [source] + [edge[1] for edge in edge_path]
260@nx._dispatchable
261def all_simple_edge_paths(G, source, target, cutoff=None):
262 """Generate lists of edges for all simple paths in G from source to target.
264 A simple path is a path with no repeated nodes.
266 Parameters
267 ----------
268 G : NetworkX graph
270 source : node
271 Starting node for path
273 target : nodes
274 Single node or iterable of nodes at which to end path
276 cutoff : integer, optional
277 Depth to stop the search. Only paths of length <= cutoff are returned.
279 Returns
280 -------
281 path_generator: generator
282 A generator that produces lists of simple paths. If there are no paths
283 between the source and target within the given cutoff the generator
284 produces no output.
285 For multigraphs, the list of edges have elements of the form `(u,v,k)`.
286 Where `k` corresponds to the edge key.
288 Examples
289 --------
291 Print the simple path edges of a Graph::
293 >>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
294 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
295 ... print(path)
296 [(1, 2), (2, 4)]
297 [(1, 3), (3, 4)]
299 Print the simple path edges of a MultiGraph. Returned edges come with
300 their associated keys::
302 >>> mg = nx.MultiGraph()
303 >>> mg.add_edge(1, 2, key="k0")
304 'k0'
305 >>> mg.add_edge(1, 2, key="k1")
306 'k1'
307 >>> mg.add_edge(2, 3, key="k0")
308 'k0'
309 >>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
310 ... print(path)
311 [(1, 2, 'k0'), (2, 3, 'k0')]
312 [(1, 2, 'k1'), (2, 3, 'k0')]
314 When ``source`` is one of the targets, the empty path starting and ending at
315 ``source`` without traversing any edge is considered a valid simple edge path
316 and is included in the results:
318 >>> G = nx.Graph()
319 >>> G.add_node(0)
320 >>> paths = list(nx.all_simple_edge_paths(G, 0, 0))
321 >>> for path in paths:
322 ... print(path)
323 []
324 >>> len(paths)
325 1
328 Notes
329 -----
330 This algorithm uses a modified depth-first search to generate the
331 paths [1]_. A single path can be found in $O(V+E)$ time but the
332 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
333 the complete graph of order $n$.
335 References
336 ----------
337 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
338 Addison Wesley Professional, 3rd ed., 2001.
340 See Also
341 --------
342 all_shortest_paths, shortest_path, all_simple_paths
344 """
345 if source not in G:
346 raise nx.NodeNotFound(f"source node {source} not in graph")
348 if target in G:
349 targets = {target}
350 else:
351 try:
352 targets = set(target)
353 except TypeError as err:
354 raise nx.NodeNotFound(f"target node {target} not in graph") from err
356 cutoff = cutoff if cutoff is not None else len(G) - 1
358 if cutoff >= 0 and targets:
359 yield from _all_simple_edge_paths(G, source, targets, cutoff)
362def _all_simple_edge_paths(G, source, targets, cutoff):
363 # We simulate recursion with a stack, keeping the current path being explored
364 # and the outgoing edge iterators at each point in the stack.
365 # To avoid unnecessary checks, the loop is structured in a way such that a path
366 # is considered for yielding only after a new node/edge is added.
367 # We bootstrap the search by adding a dummy iterator to the stack that only yields
368 # a dummy edge to source (so that the trivial path has a chance of being included).
370 get_edges = (
371 (lambda node: G.edges(node, keys=True))
372 if G.is_multigraph()
373 else (lambda node: G.edges(node))
374 )
376 # The current_path is a dictionary that maps nodes in the path to the edge that was
377 # used to enter that node (instead of a list of edges) because we want both a fast
378 # membership test for nodes in the path and the preservation of insertion order.
379 current_path = {None: None}
380 stack = [iter([(None, source)])]
382 while stack:
383 # 1. Try to extend the current path.
384 next_edge = next((e for e in stack[-1] if e[1] not in current_path), None)
385 if next_edge is None:
386 # All edges of the last node in the current path have been explored.
387 stack.pop()
388 current_path.popitem()
389 continue
390 previous_node, next_node, *_ = next_edge
392 # 2. Check if we've reached a target.
393 if next_node in targets:
394 yield (list(current_path.values()) + [next_edge])[2:] # remove dummy edge
396 # 3. Only expand the search through the next node if it makes sense.
397 if len(current_path) - 1 < cutoff and (
398 targets - current_path.keys() - {next_node}
399 ):
400 current_path[next_node] = next_edge
401 stack.append(iter(get_edges(next_node)))
404@not_implemented_for("multigraph")
405@nx._dispatchable(edge_attrs="weight")
406def shortest_simple_paths(G, source, target, weight=None):
407 """Generate all simple paths in the graph G from source to target,
408 starting from shortest ones.
410 A simple path is a path with no repeated nodes.
412 If a weighted shortest path search is to be used, no negative weights
413 are allowed.
415 Parameters
416 ----------
417 G : NetworkX graph
419 source : node
420 Starting node for path
422 target : node
423 Ending node for path
425 weight : string or function
426 If it is a string, it is the name of the edge attribute to be
427 used as a weight.
429 If it is a function, the weight of an edge is the value returned
430 by the function. The function must accept exactly three positional
431 arguments: the two endpoints of an edge and the dictionary of edge
432 attributes for that edge. The function must return a number or None.
433 The weight function can be used to hide edges by returning None.
434 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
435 will find the shortest red path.
437 If None all edges are considered to have unit weight. Default
438 value None.
440 Returns
441 -------
442 path_generator: generator
443 A generator that produces lists of simple paths, in order from
444 shortest to longest.
446 Raises
447 ------
448 NetworkXNoPath
449 If no path exists between source and target.
451 NetworkXError
452 If source or target nodes are not in the input graph.
454 NetworkXNotImplemented
455 If the input graph is a Multi[Di]Graph.
457 Examples
458 --------
460 >>> G = nx.cycle_graph(7)
461 >>> paths = list(nx.shortest_simple_paths(G, 0, 3))
462 >>> print(paths)
463 [[0, 1, 2, 3], [0, 6, 5, 4, 3]]
465 You can use this function to efficiently compute the k shortest/best
466 paths between two nodes.
468 >>> from itertools import islice
469 >>> def k_shortest_paths(G, source, target, k, weight=None):
470 ... return list(
471 ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)
472 ... )
473 >>> for path in k_shortest_paths(G, 0, 3, 2):
474 ... print(path)
475 [0, 1, 2, 3]
476 [0, 6, 5, 4, 3]
478 Notes
479 -----
480 This procedure is based on algorithm by Jin Y. Yen [1]_. Finding
481 the first $K$ paths requires $O(KN^3)$ operations.
483 See Also
484 --------
485 all_shortest_paths
486 shortest_path
487 all_simple_paths
489 References
490 ----------
491 .. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a
492 Network", Management Science, Vol. 17, No. 11, Theory Series
493 (Jul., 1971), pp. 712-716.
495 """
496 if source not in G:
497 raise nx.NodeNotFound(f"source node {source} not in graph")
499 if target not in G:
500 raise nx.NodeNotFound(f"target node {target} not in graph")
502 if weight is None:
503 length_func = len
504 shortest_path_func = _bidirectional_shortest_path
505 else:
506 wt = _weight_function(G, weight)
508 def length_func(path):
509 return sum(
510 wt(u, v, G.get_edge_data(u, v)) for (u, v) in zip(path, path[1:])
511 )
513 shortest_path_func = _bidirectional_dijkstra
515 listA = []
516 listB = PathBuffer()
517 prev_path = None
518 while True:
519 if not prev_path:
520 length, path = shortest_path_func(G, source, target, weight=weight)
521 listB.push(length, path)
522 else:
523 ignore_nodes = set()
524 ignore_edges = set()
525 for i in range(1, len(prev_path)):
526 root = prev_path[:i]
527 root_length = length_func(root)
528 for path in listA:
529 if path[:i] == root:
530 ignore_edges.add((path[i - 1], path[i]))
531 try:
532 length, spur = shortest_path_func(
533 G,
534 root[-1],
535 target,
536 ignore_nodes=ignore_nodes,
537 ignore_edges=ignore_edges,
538 weight=weight,
539 )
540 path = root[:-1] + spur
541 listB.push(root_length + length, path)
542 except nx.NetworkXNoPath:
543 pass
544 ignore_nodes.add(root[-1])
546 if listB:
547 path = listB.pop()
548 yield path
549 listA.append(path)
550 prev_path = path
551 else:
552 break
555class PathBuffer:
556 def __init__(self):
557 self.paths = set()
558 self.sortedpaths = []
559 self.counter = count()
561 def __len__(self):
562 return len(self.sortedpaths)
564 def push(self, cost, path):
565 hashable_path = tuple(path)
566 if hashable_path not in self.paths:
567 heappush(self.sortedpaths, (cost, next(self.counter), path))
568 self.paths.add(hashable_path)
570 def pop(self):
571 (cost, num, path) = heappop(self.sortedpaths)
572 hashable_path = tuple(path)
573 self.paths.remove(hashable_path)
574 return path
577def _bidirectional_shortest_path(
578 G, source, target, ignore_nodes=None, ignore_edges=None, weight=None
579):
580 """Returns the shortest path between source and target ignoring
581 nodes and edges in the containers ignore_nodes and ignore_edges.
583 This is a custom modification of the standard bidirectional shortest
584 path implementation at networkx.algorithms.unweighted
586 Parameters
587 ----------
588 G : NetworkX graph
590 source : node
591 starting node for path
593 target : node
594 ending node for path
596 ignore_nodes : container of nodes
597 nodes to ignore, optional
599 ignore_edges : container of edges
600 edges to ignore, optional
602 weight : None
603 This function accepts a weight argument for convenience of
604 shortest_simple_paths function. It will be ignored.
606 Returns
607 -------
608 path: list
609 List of nodes in a path from source to target.
611 Raises
612 ------
613 NetworkXNoPath
614 If no path exists between source and target.
616 See Also
617 --------
618 shortest_path
620 """
621 # call helper to do the real work
622 results = _bidirectional_pred_succ(G, source, target, ignore_nodes, ignore_edges)
623 pred, succ, w = results
625 # build path from pred+w+succ
626 path = []
627 # from w to target
628 while w is not None:
629 path.append(w)
630 w = succ[w]
631 # from source to w
632 w = pred[path[0]]
633 while w is not None:
634 path.insert(0, w)
635 w = pred[w]
637 return len(path), path
640def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=None):
641 """Bidirectional shortest path helper.
642 Returns (pred,succ,w) where
643 pred is a dictionary of predecessors from w to the source, and
644 succ is a dictionary of successors from w to the target.
645 """
646 # does BFS from both source and target and meets in the middle
647 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
648 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
649 if target == source:
650 return ({target: None}, {source: None}, source)
652 # handle either directed or undirected
653 if G.is_directed():
654 Gpred = G.predecessors
655 Gsucc = G.successors
656 else:
657 Gpred = G.neighbors
658 Gsucc = G.neighbors
660 # support optional nodes filter
661 if ignore_nodes:
663 def filter_iter(nodes):
664 def iterate(v):
665 for w in nodes(v):
666 if w not in ignore_nodes:
667 yield w
669 return iterate
671 Gpred = filter_iter(Gpred)
672 Gsucc = filter_iter(Gsucc)
674 # support optional edges filter
675 if ignore_edges:
676 if G.is_directed():
678 def filter_pred_iter(pred_iter):
679 def iterate(v):
680 for w in pred_iter(v):
681 if (w, v) not in ignore_edges:
682 yield w
684 return iterate
686 def filter_succ_iter(succ_iter):
687 def iterate(v):
688 for w in succ_iter(v):
689 if (v, w) not in ignore_edges:
690 yield w
692 return iterate
694 Gpred = filter_pred_iter(Gpred)
695 Gsucc = filter_succ_iter(Gsucc)
697 else:
699 def filter_iter(nodes):
700 def iterate(v):
701 for w in nodes(v):
702 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
703 yield w
705 return iterate
707 Gpred = filter_iter(Gpred)
708 Gsucc = filter_iter(Gsucc)
710 # predecessor and successors in search
711 pred = {source: None}
712 succ = {target: None}
714 # initialize fringes, start with forward
715 forward_fringe = [source]
716 reverse_fringe = [target]
718 while forward_fringe and reverse_fringe:
719 if len(forward_fringe) <= len(reverse_fringe):
720 this_level = forward_fringe
721 forward_fringe = []
722 for v in this_level:
723 for w in Gsucc(v):
724 if w not in pred:
725 forward_fringe.append(w)
726 pred[w] = v
727 if w in succ:
728 # found path
729 return pred, succ, w
730 else:
731 this_level = reverse_fringe
732 reverse_fringe = []
733 for v in this_level:
734 for w in Gpred(v):
735 if w not in succ:
736 succ[w] = v
737 reverse_fringe.append(w)
738 if w in pred:
739 # found path
740 return pred, succ, w
742 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
745def _bidirectional_dijkstra(
746 G, source, target, weight="weight", ignore_nodes=None, ignore_edges=None
747):
748 """Dijkstra's algorithm for shortest paths using bidirectional search.
750 This function returns the shortest path between source and target
751 ignoring nodes and edges in the containers ignore_nodes and
752 ignore_edges.
754 This is a custom modification of the standard Dijkstra bidirectional
755 shortest path implementation at networkx.algorithms.weighted
757 Parameters
758 ----------
759 G : NetworkX graph
761 source : node
762 Starting node.
764 target : node
765 Ending node.
767 weight: string, function, optional (default='weight')
768 Edge data key or weight function corresponding to the edge weight
769 If this is a function, the weight of an edge is the value
770 returned by the function. The function must accept exactly three
771 positional arguments: the two endpoints of an edge and the
772 dictionary of edge attributes for that edge. The function must
773 return a number or None to indicate a hidden edge.
775 ignore_nodes : container of nodes
776 nodes to ignore, optional
778 ignore_edges : container of edges
779 edges to ignore, optional
781 Returns
782 -------
783 length : number
784 Shortest path length.
786 Returns a tuple of two dictionaries keyed by node.
787 The first dictionary stores distance from the source.
788 The second stores the path from the source to that node.
790 Raises
791 ------
792 NetworkXNoPath
793 If no path exists between source and target.
795 Notes
796 -----
797 Edge weight attributes must be numerical.
798 Distances are calculated as sums of weighted edges traversed.
800 The weight function can be used to hide edges by returning None.
801 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
802 will find the shortest red path.
804 In practice bidirectional Dijkstra is much more than twice as fast as
805 ordinary Dijkstra.
807 Ordinary Dijkstra expands nodes in a sphere-like manner from the
808 source. The radius of this sphere will eventually be the length
809 of the shortest path. Bidirectional Dijkstra will expand nodes
810 from both the source and the target, making two spheres of half
811 this radius. Volume of the first sphere is pi*r*r while the
812 others are 2*pi*r/2*r/2, making up half the volume.
814 This algorithm is not guaranteed to work if edge weights
815 are negative or are floating point numbers
816 (overflows and roundoff errors can cause problems).
818 See Also
819 --------
820 shortest_path
821 shortest_path_length
822 """
823 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
824 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
825 if source == target:
826 if source not in G:
827 raise nx.NodeNotFound(f"Node {source} not in graph")
828 return (0, [source])
830 # handle either directed or undirected
831 if G.is_directed():
832 Gpred = G.predecessors
833 Gsucc = G.successors
834 else:
835 Gpred = G.neighbors
836 Gsucc = G.neighbors
838 # support optional nodes filter
839 if ignore_nodes:
841 def filter_iter(nodes):
842 def iterate(v):
843 for w in nodes(v):
844 if w not in ignore_nodes:
845 yield w
847 return iterate
849 Gpred = filter_iter(Gpred)
850 Gsucc = filter_iter(Gsucc)
852 # support optional edges filter
853 if ignore_edges:
854 if G.is_directed():
856 def filter_pred_iter(pred_iter):
857 def iterate(v):
858 for w in pred_iter(v):
859 if (w, v) not in ignore_edges:
860 yield w
862 return iterate
864 def filter_succ_iter(succ_iter):
865 def iterate(v):
866 for w in succ_iter(v):
867 if (v, w) not in ignore_edges:
868 yield w
870 return iterate
872 Gpred = filter_pred_iter(Gpred)
873 Gsucc = filter_succ_iter(Gsucc)
875 else:
877 def filter_iter(nodes):
878 def iterate(v):
879 for w in nodes(v):
880 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
881 yield w
883 return iterate
885 Gpred = filter_iter(Gpred)
886 Gsucc = filter_iter(Gsucc)
888 wt = _weight_function(G, weight)
889 # Init: Forward Backward
890 dists = [{}, {}] # dictionary of final distances
891 paths = [{source: [source]}, {target: [target]}] # dictionary of paths
892 fringe = [[], []] # heap of (distance, node) tuples for
893 # extracting next node to expand
894 seen = [{source: 0}, {target: 0}] # dictionary of distances to
895 # nodes seen
896 c = count()
897 # initialize fringe heap
898 heappush(fringe[0], (0, next(c), source))
899 heappush(fringe[1], (0, next(c), target))
900 # neighs for extracting correct neighbor information
901 neighs = [Gsucc, Gpred]
902 # variables to hold shortest discovered path
903 # finaldist = 1e30000
904 finalpath = []
905 dir = 1
906 while fringe[0] and fringe[1]:
907 # choose direction
908 # dir == 0 is forward direction and dir == 1 is back
909 dir = 1 - dir
910 # extract closest to expand
911 (dist, _, v) = heappop(fringe[dir])
912 if v in dists[dir]:
913 # Shortest path to v has already been found
914 continue
915 # update distance
916 dists[dir][v] = dist # equal to seen[dir][v]
917 if v in dists[1 - dir]:
918 # if we have scanned v in both directions we are done
919 # we have now discovered the shortest path
920 return (finaldist, finalpath)
922 for w in neighs[dir](v):
923 if dir == 0: # forward
924 minweight = wt(v, w, G.get_edge_data(v, w))
925 else: # back, must remember to change v,w->w,v
926 minweight = wt(w, v, G.get_edge_data(w, v))
927 if minweight is None:
928 continue
929 vwLength = dists[dir][v] + minweight
931 if w in dists[dir]:
932 if vwLength < dists[dir][w]:
933 raise ValueError("Contradictory paths found: negative weights?")
934 elif w not in seen[dir] or vwLength < seen[dir][w]:
935 # relaxing
936 seen[dir][w] = vwLength
937 heappush(fringe[dir], (vwLength, next(c), w))
938 paths[dir][w] = paths[dir][v] + [w]
939 if w in seen[0] and w in seen[1]:
940 # see if this path is better than the already
941 # discovered shortest path
942 totaldist = seen[0][w] + seen[1][w]
943 if finalpath == [] or finaldist > totaldist:
944 finaldist = totaldist
945 revpath = paths[1][w][:]
946 revpath.reverse()
947 finalpath = paths[0][w] + revpath[1:]
948 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")