astar_search

graph_tool.search.astar_search(g, source, weight, visitor=<graph_tool.search.AStarVisitor object>, heuristic=<function <lambda>>, dist_map=None, pred_map=None, cost_map=None, combine=<function <lambda>>, compare=<function <lambda>>, zero=0, infinity=inf, implicit=False)

Heuristic \(A^*\) search on a weighted, directed or undirected graph for the case where all edge weights are non-negative.

Parameters:

gGraph

Graph to be used.

sourceVertex

Source vertex.

weightEdgePropertyMap

Edge property map with weight values.

visitorAStarVisitor (optional, default: AStarVisitor())

A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of AStarVisitor.

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.

pred_mapVertexPropertyMap (optional, default: None)

A vertex property map where the predecessor map will be stored (must have value type “int64_t”).

cost_mapVertexPropertyMap (optional, default: None)

A vertex property map where the vertex costs will be stored. It must have the same value type as dist_map. This parameter is only used if implicit is True.

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.

implicitbool (optional, default: False)

If true, the underlying graph will be assumed to be implicit (i.e. constructed during the search).

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: float('inf'))

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

Returns:

dist_mapVertexPropertyMap

A vertex property map with the computed distances from the source.

pred_mapVertexPropertyMap

A vertex property map with the predecessor tree.

See also

bfs_search

Breadth-first search

dfs_search

Depth-first search

dijkstra_search

Dijkstra’s search algorithm

Notes

The \(A^*\) algorithm is a heuristic graph search algorithm: an \(A^*\) search is “guided” by a heuristic function. A heuristic function \(h(v)\) is one which estimates the cost from a non-goal state (v) in the graph to some goal state, t. Intuitively, \(A^*\) follows paths (through the graph) to the goal that are estimated by the heuristic function to be the best paths. Unlike best-first search, \(A^*\) takes into account the known cost from the start of the search to v; the paths \(A^*\) takes are guided by a function \(f(v) = g(v) + h(v)\), where \(h(v)\) is the heuristic function, and \(g(v)\) (sometimes denoted \(c(s, v)\)) is the known cost from the start to v. Clearly, the efficiency of \(A^*\) is highly dependent on the heuristic function with which it is used.

The time complexity is \(O((E + V)\log V)\).

The pseudo-code for the \(A^*\) algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

A*(G, source, h)
  for each vertex u in V                 initialize vertex u
    d[u] := f[u] := infinity
    color[u] := WHITE
  end for
  color[s] := GRAY
  d[s] := 0
  f[s] := h(source)
  INSERT(Q, source)                      discover vertex source
  while (Q != Ø)
    u := EXTRACT-MIN(Q)                  examine vertex u
    for each vertex v in Adj[u]          examine edge (u,v)
      if (w(u,v) + d[u] < d[v])
        d[v] := w(u,v) + d[u]            edge (u,v) relaxed
        f[v] := d[v] + h(v)
        if (color[v] = WHITE)
          color[v] := GRAY
          INSERT(Q, v)                   discover vertex v
        else if (color[v] = BLACK)
          color[v] := GRAY
          INSERT(Q, v)                   reopen vertex v
        end if
      else
        ...                              edge (u,v) not relaxed
    end for
    color[u] := BLACK                    finish vertex u
  end while

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]

[astar-bgl]

http://www.boost.org/doc/libs/release/libs/graph/doc/astar_search.html

[astar-wikipedia]

http://en.wikipedia.org/wiki/A*_search_algorithm

Examples

We will use an irregular two-dimensional lattice as an example, where the heuristic function will be based on the euclidean distance to the target.

The heuristic function will be defined as:

def h(v, target, pos):
    return sqrt(sum((pos[v].a - pos[target].a) ** 2))

where pos is the vertex position in the plane.

We must define what should be done during the search by subclassing AStarVisitor, and specializing the appropriate methods. In the following we will keep track of the discovered vertices, and which edges were examined, as well as the predecessor tree. We will also abort the search when a given target vertex is found, by raising the StopSearch exception.

class VisitorExample(gt.AStarVisitor):

    def __init__(self, touched_v, touched_e, target):
        self.touched_v = touched_v
        self.touched_e = touched_e
        self.target = target

    def discover_vertex(self, u):
        self.touched_v[u] = True

    def examine_edge(self, e):
        self.touched_e[e] = True

    def edge_relaxed(self, e):
        if e.target() == self.target:
            raise gt.StopSearch()

With the above class defined, we can perform the \(A^*\) search as follows.

>>> points = random((500, 2)) * 4
>>> points[0] = [-0.01, 0.01]
>>> points[1] = [4.01, 4.01]
>>> g, pos = gt.triangulation(points, type="delaunay")
>>> weight = g.new_edge_property("double") # Edge weights corresponding to
...                                        # Euclidean distances
>>> for e in g.edges():
...    weight[e] = sqrt(sum((pos[e.source()].a -
...                          pos[e.target()].a) ** 2))
>>> touch_v = g.new_vertex_property("bool")
>>> touch_e = g.new_edge_property("bool")
>>> target = g.vertex(1)
>>> dist, pred = gt.astar_search(g, g.vertex(0), weight,
...                              VisitorExample(touch_v, touch_e, target),
...                              heuristic=lambda v: h(v, target, pos))

We can now observe the best path found, and how many vertices and edges were visited in the process.

>>> ecolor = g.new_edge_property("string")
>>> ewidth = g.new_edge_property("double")
>>> ewidth.a = 1
>>> for e in g.edges():
...    ecolor[e] = "#3465a4" if touch_e[e] else "#d3d7cf"
>>> v = target
>>> while v != g.vertex(0):
...     p = g.vertex(pred[v])
...     for e in v.out_edges():
...         if e.target() == p:
...             ecolor[e] = "#a40000"
...             ewidth[e] = 3
...     v = p
>>> gt.graph_draw(g, pos=pos, output_size=(300, 300), vertex_fill_color=touch_v,
...               vcmap=matplotlib.cm.binary, edge_color=ecolor,
...               edge_pen_width=ewidth, output="astar-delaunay.svg")
<...>

The shortest path is shown in red. The visited edges are shown in blue, and the visited vertices in black.

The \(A^*\) algorithm is very useful for searching implicit graphs, i.e. graphs which are not entirely stored in memory and are generated “on-the-fly” during the search. In the following example we will carry out a search in a hamming hypercube of 10 bits witch has random weights on its edges in the range \([0,1]\). The vertices of the hypercube will be created during the search.

The heuristic function will use the Hamming distance between vertices:

def h(v, target, state):
    return sum(abs(state[v].a - target)) / 2

In the following visitor we will keep growing the graph on-the-fly, and abort the search when a given target vertex is found, by raising the StopSearch exception.

from numpy.random import random

class HammingVisitor(gt.AStarVisitor):

    def __init__(self, g, target, state, weight, dist, cost):
        self.g = g
        self.state = state
        self.target = target
        self.weight = weight
        self.dist = dist
        self.cost = cost
        self.visited = {}

    def examine_vertex(self, u):
        for i in range(len(self.state[u])):
            nstate = list(self.state[u])
            nstate[i] ^= 1
            if tuple(nstate) in self.visited:
                v = self.visited[tuple(nstate)]
            else:
                v = self.g.add_vertex()
                self.visited[tuple(nstate)] = v
                self.state[v] = nstate
                self.dist[v] = self.cost[v] = float('inf')
            for e in u.out_edges():
                if e.target() == v:
                    break
            else:
                e = self.g.add_edge(u, v)
                self.weight[e] = random()
        self.visited[tuple(self.state[u])] = u

    def edge_relaxed(self, e):
        if self.state[e.target()] == self.target:
            self.visited[tuple(self.target)] = e.target()
            raise gt.StopSearch()

With the above class defined, we can perform the \(A^*\) search as follows.

>>> g = gt.Graph(directed=False)
>>> state = g.new_vertex_property("vector<bool>")
>>> v = g.add_vertex()
>>> state[v] = [0] * 10
>>> target = [1] * 10
>>> weight = g.new_edge_property("double")
>>> dist = g.new_vertex_property("double")
>>> cost = g.new_vertex_property("double")
>>> visitor = HammingVisitor(g, target, state, weight, dist, cost)
>>> dist, pred = gt.astar_search(g, g.vertex(0), weight, visitor, dist_map=dist,
...                              cost_map=cost, heuristic=lambda v: h(v, array(target), state),
...                              implicit=True)

We can now observe the best path found, and how many vertices and edges were visited in the process.

>>> ecolor = g.new_edge_property("string")
>>> vcolor = g.new_vertex_property("string")
>>> ewidth = g.new_edge_property("double")
>>> ewidth.a = 1
>>> for e in g.edges():
...    ecolor[e] = "black"
>>> for v in g.vertices():
...    vcolor[v] = "white"
>>> v = visitor.visited[tuple(target)]
>>> while v != g.vertex(0):
...     vcolor[v] = "black"
...     p = g.vertex(pred[v])
...     for e in v.out_edges():
...         if e.target() == p:
...             ecolor[e] = "#a40000"
...             ewidth[e] = 3
...     v = p
>>> vcolor[v] = "black"
>>> pos = gt.graph_draw(g, output_size=(300, 300), vertex_fill_color=vcolor, edge_color=ecolor,
...                     edge_pen_width=ewidth, output="astar-implicit.svg")

The shortest path is shown in red, and the vertices which belong to it are in black. Note that the number of vertices visited is much smaller than the total number \(2^{10} = 1024\).