Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-30 19:09:08

On Wed, 30 Jun 2010, W.P. McNeill wrote:

> I am trying to write a simple example of an a-star search over a 2-dimensional grid using the Boost Graph Library. Â The source is hosted
> here:Â http://github.com/wpm/Boost-Searchable-Grid-Example. Â My intent is for this to be a resource for other people writing a-star searches.
> I am seeing an error about a missing weight map when I try to compile the call to astar_search().  As far as I can tell, everything is in order.  I hoping someone
> has insight into what I'm missing.
> 
> My graph class is a rank-2 grid graph called weighted_grid defined like so:
> 
> Â Â typedef grid_graph<2> weighted_grid;
> 
> I have a simple map that returns a weight of zero for every edge.
> 
> Â Â struct edge_weight_map {
> Â Â  Â typedef float value_type;
> Â Â  Â typedef float reference;
> Â Â  Â typedef edge_descriptor key_type;
> Â Â  Â typedef readable_property_map_tag category;
> 
> Â Â  Â reference operator[](key_type e) const {
> Â Â  Â  Â // All edges have a weight of zero.
> Â Â  Â  Â return 0;
> Â Â  Â }
> Â Â };
> 
> I associate this map with the weighted_grid class by specializing property_map.
> 
> Â Â template<>
> Â Â struct property_map<weighted_grid,
> Â Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â edge_weight_t> {
> Â Â  Â typedef edge_weight_map type;
> Â Â  Â typedef edge_weight_map const_type;
> Â Â };

Since you didn't write the grid_graph class, this is not the correct way 
to add property maps.  You will need to use an external property map (such 
as iterator_property_map) as your weight map, and then pass it in 
explicitly to the astar_search() function.

> I've defined valid expression functions for this property map along with 
> a Euclidean distance heuristic and a visitor that throws an exception 
> when a goal vertex is reached. Â The complete source is viewable at the 
> URL given above.
> 
> With these definitions I can do concept checks on the 
> ReadablePropertyMap, ReadablePropertyGraph, VertexListGraph, 
> and AStarHeuristic concepts.  I can instantiate a weighted_grid.  I can 
> get the edge weight map using get(edge_weight, g) and the vertex index 
> map using get(vertex_index, g).  I think I have written everything I 
> need to do a-star search.
> 
> However, the following call does not build:
> 
> Â Â vertex_descriptor source = vertex(0, g), goal = vertex(3, g);
> Â Â astar_search(g,
> Â Â  Â  Â  Â  Â  Â  Â  source,
> Â Â  Â  Â  Â  Â  Â  Â  euclidean_heuristic(goal),
> Â Â  Â  Â  Â  Â  Â  Â  visitor(astar_goal_visitor(goal)) );
> 
> I get a long error spew. Â The first relevant problem appears to be here:

The error here doesn't have enough of the instantiation stack to be 
useful.  Just use an explicit weight map, though, and that is more likely 
to work.

-- Jeremiah Willcock