# astar_iterator#

graph_tool.search.astar_iterator(g, source, weight, heuristic=<function <lambda>>, dist_map=None, combine=None, compare=None, zero=0, infinity=inf, array=False)[source]#

Return an iterator of the edges corresponding to an $$A^*$$ traversal of the graph.

Parameters:
gGraph

Graph to be used.

sourceVertex

Source vertex.

weightEdgePropertyMap

Edge property map with weight values.

heuristicunary function (optional, default: lambda v: 1)

The heuristic function that guides the search. It should take a single argument which is a Vertex, and output an estimated distance from the supplied vertex to the target vertex.

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:
astar_iteratorIterator or numpy.ndarray

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

bfs_iterator

dfs_iterator

Depth-first search

dijkstra_iterator

Dijkstra search algorithm

Notes

See astar_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

[astar]

Hart, P. E.; Nilsson, N. J.; Raphael, B. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100-107, 1968. DOI: 10.1109/TSSC.1968.300136 [sci-hub, @tor]

Examples