all_shortest_paths

graph_tool.topology.all_shortest_paths(g, source, target, dist_map=None, pred_map=None, all_preds_map=None, epsilon=1e-08, edges=False, **kwargs)

Return an iterator over all shortest paths from source to target.

Parameters:

gGraph

Graph to be used.

sourceVertex

Source vertex of the search.

targetVertex

Target vertex of the search.

dist_mapVertexPropertyMap (optional, default: None)

Vertex property map with the distances from source to all other vertices.

pred_mapVertexPropertyMap (optional, default: None)

Vertex property map with the predecessors in the search tree. If this is provided, the shortest paths are not computed, and are obtained directly from this map.

all_preds_mapVertexPropertyMap (optional, default: None)

Vector-valued vertex property map with all possible predecessors in the search tree. If this is provided, the shortest paths are obtained directly from this map.

epsilonfloat (optional, default: 1e-8)

Maximum relative difference between distances to be considered “equal”, in case floating-point weights are used.

edgesbool (optional, default: False)

If True, the returned iterator is over edge descriptors.

**kwargsKeyword parameter list

The remaining parameters will be passed to shortest_distance().

Returns:

path_iteratoriterator over a sequence of integers

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

Notes

The paths are computed in the same manner as in shortest_distance(), which is used internally.

If both dist_map and pred_map are provided, the shortest_distance() is not called.

Examples

>>> g = gt.collection.data["pgp-strong-2009"]
>>> for path in gt.all_shortest_paths(g, 92, 45):
...     print(path)
[  92  107 2176 7027   26   21   45]
[  92  107 2176 7033   26   21   45]
[  92   82   94 5877 5879   34   45]
[  92   89   94 5877 5879   34   45]