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
GNetworkX graph
sourcenode

Starting node for path

targetnodes

Single node or iterable of nodes at which to end path

cutoffinteger, 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.

See also

all_shortest_paths, shortest_path

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.

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]]