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

Subject: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-06-30 17:24:56

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;
  };

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:

...
/opt/local/include/boost/graph/astar_search.hpp:350:   instantiated from
‘void boost::detail::astar_dispatch1(VertexListGraph&, typename
boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap,
DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with
VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic =
boost::euclidean_heuristic, CostMap =
boost::detail::error_property_not_found, DistanceMap =
boost::detail::error_property_not_found, WeightMap = boost::edge_weight_map,
IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t,
size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap =
boost::detail::error_property_not_found, Params =
boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t,
boost::no_property>]’
/opt/local/include/boost/graph/astar_search.hpp:372:   instantiated from
‘void boost::astar_search(VertexListGraph&, typename
boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const
boost::bgl_named_params<P, T, R>&) [with VertexListGraph =
boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P =
boost::astar_goal_visitor, T = boost::graph_visitor_t, R =
boost::no_property]’
main.cpp:36:   instantiated from here
...

(Line 36 main.cpp is the last line of the astar_search call.)

This error message seems to be telling me that the weight map property for
edges is missing, but I think I have properly implemented
the get(edge_weight, g) function the documentation says is used to create
the default weight map.

Any idea what I'm doing wrong?  Thanks.