count_shortest_paths

count_shortest_paths#

graph_tool.topology.count_shortest_paths(g, source, target, dist_map=None, pred_map=None, all_preds_map=None, epsilon=1e-08, **kwargs)[source]#

Return the number of 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.

**kwargsKeyword parameter list

The remaining parameters will be passed to shortest_path().

Returns:
n_pathsint

Number of shortest paths from source to target.

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"]
>>> n_paths = gt.count_shortest_paths(g, 92, 45)
>>> print(n_paths)
4