aboutsummaryrefslogtreecommitdiff
path: root/.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py
diff options
context:
space:
mode:
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py')
-rw-r--r--.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py950
1 files changed, 950 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py
new file mode 100644
index 00000000..3605522f
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/simple_paths.py
@@ -0,0 +1,950 @@
+from heapq import heappop, heappush
+from itertools import count
+
+import networkx as nx
+from networkx.algorithms.shortest_paths.weighted import _weight_function
+from networkx.utils import not_implemented_for, pairwise
+
+__all__ = [
+ "all_simple_paths",
+ "is_simple_path",
+ "shortest_simple_paths",
+ "all_simple_edge_paths",
+]
+
+
+@nx._dispatchable
+def is_simple_path(G, nodes):
+ """Returns True if and only if `nodes` form a simple path in `G`.
+
+ A *simple path* in a graph is a nonempty sequence of nodes in which
+ no node appears more than once in the sequence, and each adjacent
+ pair of nodes in the sequence is adjacent in the graph.
+
+ Parameters
+ ----------
+ G : graph
+ A NetworkX graph.
+ nodes : list
+ A list of one or more nodes in the graph `G`.
+
+ Returns
+ -------
+ bool
+ Whether the given list of nodes represents a simple path in `G`.
+
+ Notes
+ -----
+ An empty list of nodes is not a path but a list of one node is a
+ path. Here's an explanation why.
+
+ This function operates on *node paths*. One could also consider
+ *edge paths*. There is a bijection between node paths and edge
+ paths.
+
+ The *length of a path* is the number of edges in the path, so a list
+ of nodes of length *n* corresponds to a path of length *n* - 1.
+ Thus the smallest edge path would be a list of zero edges, the empty
+ path. This corresponds to a list of one node.
+
+ To convert between a node path and an edge path, you can use code
+ like the following::
+
+ >>> from networkx.utils import pairwise
+ >>> nodes = [0, 1, 2, 3]
+ >>> edges = list(pairwise(nodes))
+ >>> edges
+ [(0, 1), (1, 2), (2, 3)]
+ >>> nodes = [edges[0][0]] + [v for u, v in edges]
+ >>> nodes
+ [0, 1, 2, 3]
+
+ Examples
+ --------
+ >>> G = nx.cycle_graph(4)
+ >>> nx.is_simple_path(G, [2, 3, 0])
+ True
+ >>> nx.is_simple_path(G, [0, 2])
+ False
+
+ """
+ # The empty list is not a valid path. Could also return
+ # NetworkXPointlessConcept here.
+ if len(nodes) == 0:
+ return False
+
+ # If the list is a single node, just check that the node is actually
+ # in the graph.
+ if len(nodes) == 1:
+ return nodes[0] in G
+
+ # check that all nodes in the list are in the graph, if at least one
+ # is not in the graph, then this is not a simple path
+ if not all(n in G for n in nodes):
+ return False
+
+ # If the list contains repeated nodes, then it's not a simple path
+ if len(set(nodes)) != len(nodes):
+ return False
+
+ # Test that each adjacent pair of nodes is adjacent.
+ return all(v in G[u] for u, v in pairwise(nodes))
+
+
+@nx._dispatchable
+def all_simple_paths(G, source, target, cutoff=None):
+ """Generate all simple paths in the graph G from source to target.
+
+ A simple path is a path with no repeated nodes.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ source : node
+ Starting node for path
+
+ target : nodes
+ Single node or iterable of nodes at which to end path
+
+ cutoff : integer, optional
+ Depth to stop the search. Only paths of length <= cutoff are returned.
+
+ Returns
+ -------
+ path_generator: generator
+ A generator that produces lists of simple paths. If there are no paths
+ between the source and target within the given cutoff the generator
+ produces no output. If it is possible to traverse the same sequence of
+ nodes in multiple ways, namely through parallel edges, then it will be
+ returned multiple times (once for each viable edge combination).
+
+ Examples
+ --------
+ This iterator generates lists of nodes::
+
+ >>> G = nx.complete_graph(4)
+ >>> for path in nx.all_simple_paths(G, source=0, target=3):
+ ... print(path)
+ ...
+ [0, 1, 2, 3]
+ [0, 1, 3]
+ [0, 2, 1, 3]
+ [0, 2, 3]
+ [0, 3]
+
+ You can generate only those paths that are shorter than a certain
+ length by using the `cutoff` keyword argument::
+
+ >>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)
+ >>> print(list(paths))
+ [[0, 1, 3], [0, 2, 3], [0, 3]]
+
+ To get each path as the corresponding list of edges, you can use the
+ :func:`networkx.utils.pairwise` helper function::
+
+ >>> paths = nx.all_simple_paths(G, source=0, target=3)
+ >>> for path in map(nx.utils.pairwise, paths):
+ ... print(list(path))
+ [(0, 1), (1, 2), (2, 3)]
+ [(0, 1), (1, 3)]
+ [(0, 2), (2, 1), (1, 3)]
+ [(0, 2), (2, 3)]
+ [(0, 3)]
+
+ Pass an iterable of nodes as target to generate all paths ending in any of several nodes::
+
+ >>> G = nx.complete_graph(4)
+ >>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]):
+ ... print(path)
+ ...
+ [0, 1, 2]
+ [0, 1, 2, 3]
+ [0, 1, 3]
+ [0, 1, 3, 2]
+ [0, 2]
+ [0, 2, 1, 3]
+ [0, 2, 3]
+ [0, 3]
+ [0, 3, 1, 2]
+ [0, 3, 2]
+
+ The singleton path from ``source`` to itself is considered a simple path and is
+ included in the results:
+
+ >>> G = nx.empty_graph(5)
+ >>> list(nx.all_simple_paths(G, source=0, target=0))
+ [[0]]
+
+ >>> G = nx.path_graph(3)
+ >>> list(nx.all_simple_paths(G, source=0, target={0, 1, 2}))
+ [[0], [0, 1], [0, 1, 2]]
+
+ Iterate over each path from the root nodes to the leaf nodes in a
+ directed acyclic graph using a functional programming approach::
+
+ >>> from itertools import chain
+ >>> from itertools import product
+ >>> from itertools import starmap
+ >>> from functools import partial
+ >>>
+ >>> chaini = chain.from_iterable
+ >>>
+ >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
+ >>> roots = (v for v, d in G.in_degree() if d == 0)
+ >>> leaves = (v for v, d in G.out_degree() if d == 0)
+ >>> all_paths = partial(nx.all_simple_paths, G)
+ >>> list(chaini(starmap(all_paths, product(roots, leaves))))
+ [[0, 1, 2], [0, 3, 2]]
+
+ The same list computed using an iterative approach::
+
+ >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
+ >>> roots = (v for v, d in G.in_degree() if d == 0)
+ >>> leaves = (v for v, d in G.out_degree() if d == 0)
+ >>> all_paths = []
+ >>> for root in roots:
+ ... for leaf in leaves:
+ ... paths = nx.all_simple_paths(G, root, leaf)
+ ... all_paths.extend(paths)
+ >>> all_paths
+ [[0, 1, 2], [0, 3, 2]]
+
+ Iterate over each path from the root nodes to the leaf nodes in a
+ directed acyclic graph passing all leaves together to avoid unnecessary
+ compute::
+
+ >>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])
+ >>> roots = (v for v, d in G.in_degree() if d == 0)
+ >>> leaves = [v for v, d in G.out_degree() if d == 0]
+ >>> all_paths = []
+ >>> for root in roots:
+ ... paths = nx.all_simple_paths(G, root, leaves)
+ ... all_paths.extend(paths)
+ >>> all_paths
+ [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]
+
+ If parallel edges offer multiple ways to traverse a given sequence of
+ nodes, this sequence of nodes will be returned multiple times:
+
+ >>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)])
+ >>> list(nx.all_simple_paths(G, 0, 2))
+ [[0, 1, 2], [0, 1, 2]]
+
+ Notes
+ -----
+ This algorithm uses a modified depth-first search to generate the
+ paths [1]_. A single path can be found in $O(V+E)$ time but the
+ number of simple paths in a graph can be very large, e.g. $O(n!)$ in
+ the complete graph of order $n$.
+
+ This function does not check that a path exists between `source` and
+ `target`. For large graphs, this may result in very long runtimes.
+ Consider using `has_path` to check that a path exists between `source` and
+ `target` before calling this function on large graphs.
+
+ References
+ ----------
+ .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
+ Addison Wesley Professional, 3rd ed., 2001.
+
+ See Also
+ --------
+ all_shortest_paths, shortest_path, has_path
+
+ """
+ for edge_path in all_simple_edge_paths(G, source, target, cutoff):
+ yield [source] + [edge[1] for edge in edge_path]
+
+
+@nx._dispatchable
+def all_simple_edge_paths(G, source, target, cutoff=None):
+ """Generate lists of edges for all simple paths in G from source to target.
+
+ A simple path is a path with no repeated nodes.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ source : node
+ Starting node for path
+
+ target : nodes
+ Single node or iterable of nodes at which to end path
+
+ cutoff : integer, optional
+ Depth to stop the search. Only paths of length <= cutoff are returned.
+
+ Returns
+ -------
+ path_generator: generator
+ A generator that produces lists of simple paths. If there are no paths
+ between the source and target within the given cutoff the generator
+ produces no output.
+ For multigraphs, the list of edges have elements of the form `(u,v,k)`.
+ Where `k` corresponds to the edge key.
+
+ Examples
+ --------
+
+ Print the simple path edges of a Graph::
+
+ >>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
+ >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
+ ... print(path)
+ [(1, 2), (2, 4)]
+ [(1, 3), (3, 4)]
+
+ Print the simple path edges of a MultiGraph. Returned edges come with
+ their associated keys::
+
+ >>> mg = nx.MultiGraph()
+ >>> mg.add_edge(1, 2, key="k0")
+ 'k0'
+ >>> mg.add_edge(1, 2, key="k1")
+ 'k1'
+ >>> mg.add_edge(2, 3, key="k0")
+ 'k0'
+ >>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
+ ... print(path)
+ [(1, 2, 'k0'), (2, 3, 'k0')]
+ [(1, 2, 'k1'), (2, 3, 'k0')]
+
+ When ``source`` is one of the targets, the empty path starting and ending at
+ ``source`` without traversing any edge is considered a valid simple edge path
+ and is included in the results:
+
+ >>> G = nx.Graph()
+ >>> G.add_node(0)
+ >>> paths = list(nx.all_simple_edge_paths(G, 0, 0))
+ >>> for path in paths:
+ ... print(path)
+ []
+ >>> len(paths)
+ 1
+
+
+ Notes
+ -----
+ This algorithm uses a modified depth-first search to generate the
+ paths [1]_. A single path can be found in $O(V+E)$ time but the
+ number of simple paths in a graph can be very large, e.g. $O(n!)$ in
+ the complete graph of order $n$.
+
+ References
+ ----------
+ .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
+ Addison Wesley Professional, 3rd ed., 2001.
+
+ See Also
+ --------
+ all_shortest_paths, shortest_path, all_simple_paths
+
+ """
+ if source not in G:
+ raise nx.NodeNotFound(f"source node {source} not in graph")
+
+ if target in G:
+ targets = {target}
+ else:
+ try:
+ targets = set(target)
+ except TypeError as err:
+ raise nx.NodeNotFound(f"target node {target} not in graph") from err
+
+ cutoff = cutoff if cutoff is not None else len(G) - 1
+
+ if cutoff >= 0 and targets:
+ yield from _all_simple_edge_paths(G, source, targets, cutoff)
+
+
+def _all_simple_edge_paths(G, source, targets, cutoff):
+ # We simulate recursion with a stack, keeping the current path being explored
+ # and the outgoing edge iterators at each point in the stack.
+ # To avoid unnecessary checks, the loop is structured in a way such that a path
+ # is considered for yielding only after a new node/edge is added.
+ # We bootstrap the search by adding a dummy iterator to the stack that only yields
+ # a dummy edge to source (so that the trivial path has a chance of being included).
+
+ get_edges = (
+ (lambda node: G.edges(node, keys=True))
+ if G.is_multigraph()
+ else (lambda node: G.edges(node))
+ )
+
+ # The current_path is a dictionary that maps nodes in the path to the edge that was
+ # used to enter that node (instead of a list of edges) because we want both a fast
+ # membership test for nodes in the path and the preservation of insertion order.
+ current_path = {None: None}
+ stack = [iter([(None, source)])]
+
+ while stack:
+ # 1. Try to extend the current path.
+ next_edge = next((e for e in stack[-1] if e[1] not in current_path), None)
+ if next_edge is None:
+ # All edges of the last node in the current path have been explored.
+ stack.pop()
+ current_path.popitem()
+ continue
+ previous_node, next_node, *_ = next_edge
+
+ # 2. Check if we've reached a target.
+ if next_node in targets:
+ yield (list(current_path.values()) + [next_edge])[2:] # remove dummy edge
+
+ # 3. Only expand the search through the next node if it makes sense.
+ if len(current_path) - 1 < cutoff and (
+ targets - current_path.keys() - {next_node}
+ ):
+ current_path[next_node] = next_edge
+ stack.append(iter(get_edges(next_node)))
+
+
+@not_implemented_for("multigraph")
+@nx._dispatchable(edge_attrs="weight")
+def shortest_simple_paths(G, source, target, weight=None):
+ """Generate all simple paths in the graph G from source to target,
+ starting from shortest ones.
+
+ A simple path is a path with no repeated nodes.
+
+ If a weighted shortest path search is to be used, no negative weights
+ are allowed.
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ source : node
+ Starting node for path
+
+ target : node
+ Ending node for path
+
+ weight : string or function
+ If it is a string, it is the name of the edge attribute to be
+ used as a weight.
+
+ If it is a function, the weight of an edge is the value returned
+ by the function. The function must accept exactly three positional
+ arguments: the two endpoints of an edge and the dictionary of edge
+ attributes for that edge. The function must return a number or None.
+ The weight function can be used to hide edges by returning None.
+ So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+ will find the shortest red path.
+
+ If None all edges are considered to have unit weight. Default
+ value None.
+
+ Returns
+ -------
+ path_generator: generator
+ A generator that produces lists of simple paths, in order from
+ shortest to longest.
+
+ Raises
+ ------
+ NetworkXNoPath
+ If no path exists between source and target.
+
+ NetworkXError
+ If source or target nodes are not in the input graph.
+
+ NetworkXNotImplemented
+ If the input graph is a Multi[Di]Graph.
+
+ Examples
+ --------
+
+ >>> G = nx.cycle_graph(7)
+ >>> paths = list(nx.shortest_simple_paths(G, 0, 3))
+ >>> print(paths)
+ [[0, 1, 2, 3], [0, 6, 5, 4, 3]]
+
+ You can use this function to efficiently compute the k shortest/best
+ paths between two nodes.
+
+ >>> from itertools import islice
+ >>> def k_shortest_paths(G, source, target, k, weight=None):
+ ... return list(
+ ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)
+ ... )
+ >>> for path in k_shortest_paths(G, 0, 3, 2):
+ ... print(path)
+ [0, 1, 2, 3]
+ [0, 6, 5, 4, 3]
+
+ Notes
+ -----
+ This procedure is based on algorithm by Jin Y. Yen [1]_. Finding
+ the first $K$ paths requires $O(KN^3)$ operations.
+
+ See Also
+ --------
+ all_shortest_paths
+ shortest_path
+ all_simple_paths
+
+ References
+ ----------
+ .. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a
+ Network", Management Science, Vol. 17, No. 11, Theory Series
+ (Jul., 1971), pp. 712-716.
+
+ """
+ if source not in G:
+ raise nx.NodeNotFound(f"source node {source} not in graph")
+
+ if target not in G:
+ raise nx.NodeNotFound(f"target node {target} not in graph")
+
+ if weight is None:
+ length_func = len
+ shortest_path_func = _bidirectional_shortest_path
+ else:
+ wt = _weight_function(G, weight)
+
+ def length_func(path):
+ return sum(
+ wt(u, v, G.get_edge_data(u, v)) for (u, v) in zip(path, path[1:])
+ )
+
+ shortest_path_func = _bidirectional_dijkstra
+
+ listA = []
+ listB = PathBuffer()
+ prev_path = None
+ while True:
+ if not prev_path:
+ length, path = shortest_path_func(G, source, target, weight=weight)
+ listB.push(length, path)
+ else:
+ ignore_nodes = set()
+ ignore_edges = set()
+ for i in range(1, len(prev_path)):
+ root = prev_path[:i]
+ root_length = length_func(root)
+ for path in listA:
+ if path[:i] == root:
+ ignore_edges.add((path[i - 1], path[i]))
+ try:
+ length, spur = shortest_path_func(
+ G,
+ root[-1],
+ target,
+ ignore_nodes=ignore_nodes,
+ ignore_edges=ignore_edges,
+ weight=weight,
+ )
+ path = root[:-1] + spur
+ listB.push(root_length + length, path)
+ except nx.NetworkXNoPath:
+ pass
+ ignore_nodes.add(root[-1])
+
+ if listB:
+ path = listB.pop()
+ yield path
+ listA.append(path)
+ prev_path = path
+ else:
+ break
+
+
+class PathBuffer:
+ def __init__(self):
+ self.paths = set()
+ self.sortedpaths = []
+ self.counter = count()
+
+ def __len__(self):
+ return len(self.sortedpaths)
+
+ def push(self, cost, path):
+ hashable_path = tuple(path)
+ if hashable_path not in self.paths:
+ heappush(self.sortedpaths, (cost, next(self.counter), path))
+ self.paths.add(hashable_path)
+
+ def pop(self):
+ (cost, num, path) = heappop(self.sortedpaths)
+ hashable_path = tuple(path)
+ self.paths.remove(hashable_path)
+ return path
+
+
+def _bidirectional_shortest_path(
+ G, source, target, ignore_nodes=None, ignore_edges=None, weight=None
+):
+ """Returns the shortest path between source and target ignoring
+ nodes and edges in the containers ignore_nodes and ignore_edges.
+
+ This is a custom modification of the standard bidirectional shortest
+ path implementation at networkx.algorithms.unweighted
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ source : node
+ starting node for path
+
+ target : node
+ ending node for path
+
+ ignore_nodes : container of nodes
+ nodes to ignore, optional
+
+ ignore_edges : container of edges
+ edges to ignore, optional
+
+ weight : None
+ This function accepts a weight argument for convenience of
+ shortest_simple_paths function. It will be ignored.
+
+ Returns
+ -------
+ path: list
+ List of nodes in a path from source to target.
+
+ Raises
+ ------
+ NetworkXNoPath
+ If no path exists between source and target.
+
+ See Also
+ --------
+ shortest_path
+
+ """
+ # call helper to do the real work
+ results = _bidirectional_pred_succ(G, source, target, ignore_nodes, ignore_edges)
+ pred, succ, w = results
+
+ # build path from pred+w+succ
+ path = []
+ # from w to target
+ while w is not None:
+ path.append(w)
+ w = succ[w]
+ # from source to w
+ w = pred[path[0]]
+ while w is not None:
+ path.insert(0, w)
+ w = pred[w]
+
+ return len(path), path
+
+
+def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=None):
+ """Bidirectional shortest path helper.
+ Returns (pred,succ,w) where
+ pred is a dictionary of predecessors from w to the source, and
+ succ is a dictionary of successors from w to the target.
+ """
+ # does BFS from both source and target and meets in the middle
+ if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
+ raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
+ if target == source:
+ return ({target: None}, {source: None}, source)
+
+ # handle either directed or undirected
+ if G.is_directed():
+ Gpred = G.predecessors
+ Gsucc = G.successors
+ else:
+ Gpred = G.neighbors
+ Gsucc = G.neighbors
+
+ # support optional nodes filter
+ if ignore_nodes:
+
+ def filter_iter(nodes):
+ def iterate(v):
+ for w in nodes(v):
+ if w not in ignore_nodes:
+ yield w
+
+ return iterate
+
+ Gpred = filter_iter(Gpred)
+ Gsucc = filter_iter(Gsucc)
+
+ # support optional edges filter
+ if ignore_edges:
+ if G.is_directed():
+
+ def filter_pred_iter(pred_iter):
+ def iterate(v):
+ for w in pred_iter(v):
+ if (w, v) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ def filter_succ_iter(succ_iter):
+ def iterate(v):
+ for w in succ_iter(v):
+ if (v, w) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ Gpred = filter_pred_iter(Gpred)
+ Gsucc = filter_succ_iter(Gsucc)
+
+ else:
+
+ def filter_iter(nodes):
+ def iterate(v):
+ for w in nodes(v):
+ if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ Gpred = filter_iter(Gpred)
+ Gsucc = filter_iter(Gsucc)
+
+ # predecessor and successors in search
+ pred = {source: None}
+ succ = {target: None}
+
+ # initialize fringes, start with forward
+ forward_fringe = [source]
+ reverse_fringe = [target]
+
+ while forward_fringe and reverse_fringe:
+ if len(forward_fringe) <= len(reverse_fringe):
+ this_level = forward_fringe
+ forward_fringe = []
+ for v in this_level:
+ for w in Gsucc(v):
+ if w not in pred:
+ forward_fringe.append(w)
+ pred[w] = v
+ if w in succ:
+ # found path
+ return pred, succ, w
+ else:
+ this_level = reverse_fringe
+ reverse_fringe = []
+ for v in this_level:
+ for w in Gpred(v):
+ if w not in succ:
+ succ[w] = v
+ reverse_fringe.append(w)
+ if w in pred:
+ # found path
+ return pred, succ, w
+
+ raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
+
+
+def _bidirectional_dijkstra(
+ G, source, target, weight="weight", ignore_nodes=None, ignore_edges=None
+):
+ """Dijkstra's algorithm for shortest paths using bidirectional search.
+
+ This function returns the shortest path between source and target
+ ignoring nodes and edges in the containers ignore_nodes and
+ ignore_edges.
+
+ This is a custom modification of the standard Dijkstra bidirectional
+ shortest path implementation at networkx.algorithms.weighted
+
+ Parameters
+ ----------
+ G : NetworkX graph
+
+ source : node
+ Starting node.
+
+ target : node
+ Ending node.
+
+ weight: string, function, optional (default='weight')
+ Edge data key or weight function corresponding to the edge weight
+ If this is a function, the weight of an edge is the value
+ returned by the function. The function must accept exactly three
+ positional arguments: the two endpoints of an edge and the
+ dictionary of edge attributes for that edge. The function must
+ return a number or None to indicate a hidden edge.
+
+ ignore_nodes : container of nodes
+ nodes to ignore, optional
+
+ ignore_edges : container of edges
+ edges to ignore, optional
+
+ Returns
+ -------
+ length : number
+ Shortest path length.
+
+ Returns a tuple of two dictionaries keyed by node.
+ The first dictionary stores distance from the source.
+ The second stores the path from the source to that node.
+
+ Raises
+ ------
+ NetworkXNoPath
+ If no path exists between source and target.
+
+ Notes
+ -----
+ Edge weight attributes must be numerical.
+ Distances are calculated as sums of weighted edges traversed.
+
+ The weight function can be used to hide edges by returning None.
+ So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
+ will find the shortest red path.
+
+ In practice bidirectional Dijkstra is much more than twice as fast as
+ ordinary Dijkstra.
+
+ Ordinary Dijkstra expands nodes in a sphere-like manner from the
+ source. The radius of this sphere will eventually be the length
+ of the shortest path. Bidirectional Dijkstra will expand nodes
+ from both the source and the target, making two spheres of half
+ this radius. Volume of the first sphere is pi*r*r while the
+ others are 2*pi*r/2*r/2, making up half the volume.
+
+ This algorithm is not guaranteed to work if edge weights
+ are negative or are floating point numbers
+ (overflows and roundoff errors can cause problems).
+
+ See Also
+ --------
+ shortest_path
+ shortest_path_length
+ """
+ if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
+ raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
+ if source == target:
+ if source not in G:
+ raise nx.NodeNotFound(f"Node {source} not in graph")
+ return (0, [source])
+
+ # handle either directed or undirected
+ if G.is_directed():
+ Gpred = G.predecessors
+ Gsucc = G.successors
+ else:
+ Gpred = G.neighbors
+ Gsucc = G.neighbors
+
+ # support optional nodes filter
+ if ignore_nodes:
+
+ def filter_iter(nodes):
+ def iterate(v):
+ for w in nodes(v):
+ if w not in ignore_nodes:
+ yield w
+
+ return iterate
+
+ Gpred = filter_iter(Gpred)
+ Gsucc = filter_iter(Gsucc)
+
+ # support optional edges filter
+ if ignore_edges:
+ if G.is_directed():
+
+ def filter_pred_iter(pred_iter):
+ def iterate(v):
+ for w in pred_iter(v):
+ if (w, v) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ def filter_succ_iter(succ_iter):
+ def iterate(v):
+ for w in succ_iter(v):
+ if (v, w) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ Gpred = filter_pred_iter(Gpred)
+ Gsucc = filter_succ_iter(Gsucc)
+
+ else:
+
+ def filter_iter(nodes):
+ def iterate(v):
+ for w in nodes(v):
+ if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
+ yield w
+
+ return iterate
+
+ Gpred = filter_iter(Gpred)
+ Gsucc = filter_iter(Gsucc)
+
+ wt = _weight_function(G, weight)
+ push = heappush
+ pop = heappop
+ # Init: Forward Backward
+ dists = [{}, {}] # dictionary of final distances
+ paths = [{source: [source]}, {target: [target]}] # dictionary of paths
+ fringe = [[], []] # heap of (distance, node) tuples for
+ # extracting next node to expand
+ seen = [{source: 0}, {target: 0}] # dictionary of distances to
+ # nodes seen
+ c = count()
+ # initialize fringe heap
+ push(fringe[0], (0, next(c), source))
+ push(fringe[1], (0, next(c), target))
+ # neighs for extracting correct neighbor information
+ neighs = [Gsucc, Gpred]
+ # variables to hold shortest discovered path
+ # finaldist = 1e30000
+ finalpath = []
+ dir = 1
+ while fringe[0] and fringe[1]:
+ # choose direction
+ # dir == 0 is forward direction and dir == 1 is back
+ dir = 1 - dir
+ # extract closest to expand
+ (dist, _, v) = pop(fringe[dir])
+ if v in dists[dir]:
+ # Shortest path to v has already been found
+ continue
+ # update distance
+ dists[dir][v] = dist # equal to seen[dir][v]
+ if v in dists[1 - dir]:
+ # if we have scanned v in both directions we are done
+ # we have now discovered the shortest path
+ return (finaldist, finalpath)
+
+ for w in neighs[dir](v):
+ if dir == 0: # forward
+ minweight = wt(v, w, G.get_edge_data(v, w))
+ else: # back, must remember to change v,w->w,v
+ minweight = wt(w, v, G.get_edge_data(w, v))
+ if minweight is None:
+ continue
+ vwLength = dists[dir][v] + minweight
+
+ if w in dists[dir]:
+ if vwLength < dists[dir][w]:
+ raise ValueError("Contradictory paths found: negative weights?")
+ elif w not in seen[dir] or vwLength < seen[dir][w]:
+ # relaxing
+ seen[dir][w] = vwLength
+ push(fringe[dir], (vwLength, next(c), w))
+ paths[dir][w] = paths[dir][v] + [w]
+ if w in seen[0] and w in seen[1]:
+ # see if this path is better than the already
+ # discovered shortest path
+ totaldist = seen[0][w] + seen[1][w]
+ if finalpath == [] or finaldist > totaldist:
+ finaldist = totaldist
+ revpath = paths[1][w][:]
+ revpath.reverse()
+ finalpath = paths[0][w] + revpath[1:]
+ raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
generated by cgit v1.2.3 (git 2.47.1) at 2025-07-27 07:55:49 +0000