dijkstra_iterator

dijkstra_iterator#

graph_tool.search.dijkstra_iterator(g, weight, source=None, dist_map=None, combine=None, compare=None, zero=0, infinity=inf, array=False)[source]#

Return an iterator of the edges corresponding to a Dijkstra traversal of the graph.

Parameters:
gGraph

Graph to be used.

weightEdgePropertyMap

Edge property map with weight values.

sourceVertex (optional, default: None)

Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.

dist_mapVertexPropertyMap (optional, default: None)

A vertex property map where the distances from the source will be stored.

combinebinary function (optional, default: lambda a, b: a + b)

This function is used to combine distances to compute the distance of a path.

comparebinary function (optional, default: lambda a, b: a < b)

This function is use to compare distances to determine which vertex is closer to the source vertex.

zeroint or float (optional, default: 0)

Value assumed to correspond to a distance of zero by the combine and compare functions.

infinityint or float (optional, default: numpy.inf)

Value assumed to correspond to a distance of infinity by the combine and compare functions.

arraybool (optional, default: False)

If True, a numpy.ndarray with the edge endpoints be returned instead.

Returns:
dfs_iteratorIterator or numpy.ndarray

An iterator over the edges in Dijkstra order. If array == True, this will be a numpy.ndarray instead, of shape (E,2), containing the edge endpoints.

See also

bfs_iterator

Breadth-first search

dfs_iterator

Depth-first search

astar_iterator

\(A^*\) heuristic search algorithm

Notes

See dijkstra_search() for an explanation of the algorithm.

The time complexity is \(O(1)\) to create the generator and \(O(E + V\log V)\) to traverse it completely.

References

[dijkstra]

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

Examples

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> for e in gt.dijkstra_iterator(g, weight, g.vertex(0)):
...    print(name[e.source()], "->", name[e.target()])
Bob -> Eve
Bob -> Chuck
Bob -> Carlos
Bob -> Isaac
Eve -> Imothep
Eve -> Carol
Carlos -> Alice
Alice -> Oscar
Alice -> Dave