networkx.algorithms.simple_paths.all_simple_paths¶
-
all_simple_paths
(G, source, target, cutoff=None)[source]¶ 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 – 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.
- Return type
generator
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
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()