graph_tool.topology.random_shortest_path

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

Return a random shortest path from source to target, uniformly sampled from all paths of equal length.

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.

nsamplesint (optional, default: 1)

Number of paths to sample.

iteratorbool (optional, default: False)

If True, an iterator is returned.

**kwargsKeyword parameter list

The remaining parameters will be passed to shortest_path().

Returns:

pathnumpy.ndarray, or list of numpy.ndarray or iterator over numpy.ndarray

Sequence of vertices from source to target in the shortest path. If nsamples > 1 a list (or iterator) over paths is returned.

Notes

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

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

Examples

>>> g = gt.collection.data["pgp-strong-2009"]
>>> path = gt.random_shortest_path(g, 92, 45)
>>> print(path)
[  92   89   94 5877 5879   34   45]