Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / simple_paths.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2012 by ``` ```# Sergio Nery Simoes ``` ```# All rights reserved. ``` ```# BSD license. ``` ```import collections ``` ```from heapq import heappush, heappop ``` ```from itertools import count ``` ```import networkx as nx ``` ```from networkx.utils import not_implemented_for ``` ```from networkx.utils import pairwise ``` ```__author__ = """\n""".join(['Sérgio Nery Simões ', ``` ``` 'Aric Hagberg ', ``` ``` 'Andrey Paramonov', ``` ``` 'Jordi Torrents ']) ``` ```__all__ = [ ``` ``` 'all_simple_paths', ``` ``` 'is_simple_path', ``` ``` 'shortest_simple_paths', ``` ```] ``` ```def is_simple_path(G, nodes): ``` ``` """Returns True if and only if the given 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 ``` ``` ---------- ``` ``` 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 ``` ``` ----- ``` ``` A list of zero nodes is not a path and 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 ``` ``` # Test that no node appears more than once, and that each ``` ``` # adjacent pair of nodes is adjacent. ``` ``` return (len(set(nodes)) == len(nodes) and ``` ``` all(v in G[u] for u, v in pairwise(nodes))) ``` ```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. ``` ``` ``` ``` 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] ``` ``` ``` ``` 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]] ``` ``` ``` ``` 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 ``` ``` ``` ``` """ ``` ``` if source not in G: ``` ``` raise nx.NodeNotFound('source node %s not in graph' % source) ``` ``` if target in G: ``` ``` targets = {target} ``` ``` else: ``` ``` try: ``` ``` targets = set(target) ``` ``` except TypeError: ``` ``` raise nx.NodeNotFound('target node %s not in graph' % target) ``` ``` if source in targets: ``` ``` return [] ``` ``` if cutoff is None: ``` ``` cutoff = len(G) - 1 ``` ``` if cutoff < 1: ``` ``` return [] ``` ``` if G.is_multigraph(): ``` ``` return _all_simple_paths_multigraph(G, source, targets, cutoff) ``` ``` else: ``` ``` return _all_simple_paths_graph(G, source, targets, cutoff) ``` ```def _all_simple_paths_graph(G, source, targets, cutoff): ``` ``` visited = collections.OrderedDict.fromkeys([source]) ``` ``` stack = [iter(G[source])] ``` ``` while stack: ``` ``` children = stack[-1] ``` ``` child = next(children, None) ``` ``` if child is None: ``` ``` stack.pop() ``` ``` visited.popitem() ``` ``` elif len(visited) < cutoff: ``` ``` if child in visited: ``` ``` continue ``` ``` if child in targets: ``` ``` yield list(visited) + [child] ``` ``` visited[child] = None ``` ``` if targets - set(visited.keys()): # expand stack until find all targets ``` ``` stack.append(iter(G[child])) ``` ``` else: ``` ``` visited.popitem() # maybe other ways to child ``` ``` else: # len(visited) == cutoff: ``` ``` for target in (targets & (set(children) | {child})) - set(visited.keys()): ``` ``` yield list(visited) + [target] ``` ``` stack.pop() ``` ``` visited.popitem() ``` ```def _all_simple_paths_multigraph(G, source, targets, cutoff): ``` ``` visited = collections.OrderedDict.fromkeys([source]) ``` ``` stack = [(v for u, v in G.edges(source))] ``` ``` while stack: ``` ``` children = stack[-1] ``` ``` child = next(children, None) ``` ``` if child is None: ``` ``` stack.pop() ``` ``` visited.popitem() ``` ``` elif len(visited) < cutoff: ``` ``` if child in visited: ``` ``` continue ``` ``` if child in targets: ``` ``` yield list(visited) + [child] ``` ``` visited[child] = None ``` ``` if targets - set(visited.keys()): ``` ``` stack.append((v for u, v in G.edges(child))) ``` ``` else: ``` ``` visited.popitem() ``` ``` else: # len(visited) == cutoff: ``` ``` for target in targets - set(visited.keys()): ``` ``` count = ([child] + list(children)).count(target) ``` ``` for i in range(count): ``` ``` yield list(visited) + [target] ``` ``` stack.pop() ``` ``` visited.popitem() ``` ```@not_implemented_for('multigraph') ``` ```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 ``` ``` Name of the edge attribute to be used as a weight. 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('source node %s not in graph' % source) ``` ``` if target not in G: ``` ``` raise nx.NodeNotFound('target node %s not in graph' % target) ``` ``` if weight is None: ``` ``` length_func = len ``` ``` shortest_path_func = _bidirectional_shortest_path ``` ``` else: ``` ``` def length_func(path): ``` ``` return sum(G.adj[u][v][weight] for (u, v) in zip(path, path[1:])) ``` ``` shortest_path_func = _bidirectional_dijkstra ``` ``` listA = list() ``` ``` 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(object): ``` ``` def __init__(self): ``` ``` self.paths = set() ``` ``` self.sortedpaths = list() ``` ``` 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("No path between %s and %s." % (source, 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) ``` ``` # predecesssor 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("No path between %s and %s." % (source, 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, optional (default='weight') ``` ``` Edge data key corresponding to the edge weight ``` ``` ``` ``` 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. ``` ``` ``` ``` 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("No path between %s and %s." % (source, target)) ``` ``` if source == target: ``` ``` 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) ``` ``` 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 ``` ``` if G.is_multigraph(): ``` ``` minweight = min((dd.get(weight, 1) ``` ``` for k, dd in G[v][w].items())) ``` ``` else: ``` ``` minweight = G[v][w].get(weight, 1) ``` ``` vwLength = dists[dir][v] + minweight # G[v][w].get(weight,1) ``` ``` else: # back, must remember to change v,w->w,v ``` ``` if G.is_multigraph(): ``` ``` minweight = min((dd.get(weight, 1) ``` ``` for k, dd in G[w][v].items())) ``` ``` else: ``` ``` minweight = G[w][v].get(weight, 1) ``` ``` vwLength = dists[dir][v] + minweight # G[w][v].get(weight,1) ``` ``` 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 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("No path between %s and %s." % (source, target)) ```