graph_tool.topology.all_paths#

graph_tool.topology.all_paths(g, source, target, cutoff=None, edges=False)[source]#

Return an iterator over all paths from source to target.

Parameters:
gGraph

Graph to be used.

sourceVertex

Source vertex of the search.

targetVertex

Target vertex of the search.

cutoffint (optional, default: None)

Maximum path length.

edgesbool (optional, default: False)

If True, the returned iterator is over edge descriptors.

Returns:
path_iteratoriterator over a sequence of integers (or Edge)

Iterator over sequences of vertices from source to target in the path. If edges == True, the iterator is over sequences of edge descriptors (Edge).

Notes

The algorithm uses a depth-first search to find all the paths.

The total number of paths between any two vertices can be quite large, possibly scaling as \(O(V!)\).

Examples

>>> g = gt.collection.data["football"]
>>> for path in gt.all_paths(g, 13, 2, cutoff=2):
...     print(path)
[13  2]
[13 15  2]
[13 60  2]
[13 64  2]
[ 13 100   2]
[ 13 106   2]