Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.simple_paths

# -*- coding: utf-8 -*-
#    Sergio Nery Simoes <sergionery@gmail.com>
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 <sergionery@gmail.com>',
'Aric Hagberg <aric.hagberg@gmail.com>',
'Andrey Paramonov',
'Jordi Torrents <jordi.t21@gmail.com>'])

__all__ = [
'all_simple_paths',
'is_simple_path',
'shortest_simple_paths',
]

[docs]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)))
[docs]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 : node Ending node for 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)] 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 not in G: raise nx.NodeNotFound('target node %s not in graph' % target) if cutoff is None: cutoff = len(G) - 1 if G.is_multigraph(): return _all_simple_paths_multigraph(G, source, target, cutoff=cutoff) else: return _all_simple_paths_graph(G, source, target, cutoff=cutoff)
def _all_simple_paths_graph(G, source, target, cutoff=None): if cutoff < 1: return visited = [source] stack = [iter(G[source])] while stack: children = stack[-1] child = next(children, None) if child is None: stack.pop() visited.pop() elif len(visited) < cutoff: if child == target: yield visited + [target] elif child not in visited: visited.append(child) stack.append(iter(G[child])) else: # len(visited) == cutoff: if child == target or target in children: yield visited + [target] stack.pop() visited.pop() def _all_simple_paths_multigraph(G, source, target, cutoff=None): if cutoff < 1: return visited = [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.pop() elif len(visited) < cutoff: if child == target: yield visited + [target] elif child not in visited: visited.append(child) stack.append((v for u, v in G.edges(child))) else: # len(visited) == cutoff: count = ([child] + list(children)).count(target) for i in range(count): yield visited + [target] stack.pop() visited.pop()
[docs]@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 allawed. 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])) ignore_nodes.add(root[-1]) 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 if listB: path = listB.pop() yield path listA.append(path) prev_path = path else: break