NetworkX

Previous topic

all_simple_paths

Next topic

Swap

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 : 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.

See also

shortest_path

Notes

This algorithm uses a modified depth-first search to generate the paths [R198]. 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

[R198](1, 2) R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.

Examples

>>> G = nx.path_graph(5)
>>> for path in nx.all_simple_paths(G, source=0, target=4):
...    print(path)
[0, 1, 2, 3, 4]
>>> G = nx.Graph()
>>> G.add_path([1,2,3])
>>> G.add_path([1,20,3])
>>> paths = nx.all_simple_paths(G, source=1, target=3)
>>> print(list(paths))
[[1, 2, 3], [1, 20, 3]]