astar_iterator

Contents

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.

See also

bfs_iterator

Breadth-first search

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

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> for e in gt.astar_iterator(g, g.vertex(0), weight):
...    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
Contents