shortest_distance

shortest_distance#

graph_tool.topology.shortest_distance(g, source=None, target=None, weights=None, negative_weights=False, max_dist=None, directed=None, dense=False, dist_map=None, pred_map=False, return_reached=False, dag=False)[source]#

Calculate the distance from a source to a target vertex, or to of all vertices from a given source, or the all pairs shortest paths, if the source is not specified.

Parameters:
gGraph

Graph to be used.

sourceVertex (optional, default: None)

Source vertex of the search. If unspecified, the all pairs shortest distances are computed.

targetVertex or iterable of such objects (optional, default: None)

Target vertex (or vertices) of the search. If unspecified, the distance to all vertices from the source will be computed.

weightsEdgePropertyMap (optional, default: None)

The edge weights. If provided, the shortest path will correspond to the minimal sum of weights.

negative_weightsbool (optional, default: False)

If True, this will trigger the use of the Bellman-Ford algorithm. Ignored if source is None.

max_distscalar value (optional, default: None)

If specified, this limits the maximum distance of the vertices searched. This parameter has no effect if source is None, or if negative_weights=True.

directedbool (optional, default:None)

Treat graph as directed or not, independently of its actual directionality.

densebool (optional, default: False)

If True, and source is None, the Floyd-Warshall algorithm is used, otherwise the Johnson algorithm is used. If source is not None, this option has no effect.

dist_mapVertexPropertyMap (optional, default: None)

Vertex property to store the distances. If none is supplied, one is created.

Warning

If this parameter is supplied, the user is responsible for initializing it to infinity. This can be done as:

>>> dist_map = g.new_vp("double", numpy.inf)

or

>>> dist_map = g.new_vp("int32_t", numpy.iinfo(numpy.int32).max)

depending on the distance type.

pred_mapbool or VertexPropertyMap (optional, default: False)

If True, a vertex property map with the predecessors is returned. If a VertexPropertyMap is passed, it must be of value int64_t and it will be used to store the predecessors. Ignored if source is None.

Warning

If a property map is supplied, the user is responsible for initializing to the identity map. This can be done as:

>>> pred_map = g.vertex_index.copy()
return_reachedbool (optional, default: False)

If True, return an array of visited vertices.

dagbool (optional, default:False)

If True, assume that the graph is a Directed Acyclic Graph (DAG), which will be faster if weights are given, in which case they are also allowed to contain negative values (irrespective of the parameter negative_weights). Ignored if source is None.

Returns:
dist_mapVertexPropertyMap or numpy.ndarray or scalar

Vertex property map with the distances from source. If source is None, it will have a vector value type, with the distances to every vertex. If target is an iterable, instead of VertexPropertyMap, this will be of type numpy.ndarray, and contain only the distances to those specific targets. If a single source and a single target are specified, a single scalar will be returned.

pred_mapVertexPropertyMap (optional, if pred_map == True)

Vertex property map with the predecessors in the search tree.

visitednumpy.ndarray (optional, if return_reached == True)

Array containing vertices visited during the search.

Notes

If a source is given, the distances are calculated with a breadth-first search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If negative_weights == True, the Bellman-Ford algorithm is used [bellman-ford], which accepts negative weights, as long as there are no negative loops. If source is not given, the distances are calculated with Johnson’s algorithm [johnson-apsp]. If dense=True, the Floyd-Warshall algorithm [floyd-warshall-apsp] is used instead.

If there is no path between two vertices, the computed distance will correspond to the maximum value allowed by the value type of dist_map, or inf in case of floating point types.

If source is specified, the algorithm runs in \(O(V + E)\) time, or \(O(V \log V)\) if weights are given (if dag == True this improves to \(O(V+E)\)). If negative_weights == True, the complexity is \(O(VE)\). If source is not specified, the algorithm runs in parallel with complexity \(O(V (V + E))\), if weights are given it runs in \(O(VE\log V)\) time, or \(O(V^3)\) if dense == True.

References

[bfs]

Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press.

[dijkstra]

E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269-271, 1959.

Examples

>>> from numpy.random import poisson
>>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
>>> dist = gt.shortest_distance(g, source=g.vertex(0))
>>> print(dist.a)
[         0          4          5          4          6          4
          5          5          2          3          4          4
          6          5          7          5 2147483647          4
 2147483647          3          3          4          3          2
          4          5          5          4          4          4
          4          6          3          4          3          5
          1          5          4          3          4          3
          6 2147483647          4          5          3          5
          6          4          5          4          4          3
          3          4          6          4          2          3
          4          5          4          5          4          2
          5          5          3          3 2147483647          4
 2147483647          7          6          3          4          4
          5          4          1 2147483647          3          2
          4          4          5          3          4          5
          5          5          5          5          5          5
          4          3          2          3]
>>>
>>> dist = gt.shortest_distance(g)
>>> print(dist[g.vertex(0)].a)
[         0          4          5          4          6          4
          5          5          2          3          4          4
          6          5          7          5 2147483647          4
 2147483647          3          3          4          3          2
          4          5          5          4          4          4
          4          6          3          4          3          5
          1          5          4          3          4          3
          6 2147483647          4          5          3          5
          6          4          5          4          4          3
          3          4          6          4          2          3
          4          5          4          5          4          2
          5          5          3          3 2147483647          4
 2147483647          7          6          3          4          4
          5          4          1 2147483647          3          2
          4          4          5          3          4          5
          5          5          5          5          5          5
          4          3          2          3]
>>> dist = gt.shortest_distance(g, source=g.vertex(0), target=g.vertex(2))
>>> print(dist)
5
>>> dist = gt.shortest_distance(g, source=g.vertex(0), target=[g.vertex(2), g.vertex(6)])
>>> print(dist)
[5 5]