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: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-06-30 19:50:43

I also tried passing an edge_weight_map structure as a named parameter to
astar_search.

  vertex_descriptor source = vertex(0, g), goal = vertex(3, g);
  edge_weight_map mymap = edge_weight_map();
  astar_search(g,
               source,
               euclidean_heuristic(goal),
               weight_map(mymap).
               visitor(astar_goal_visitor(goal)) );

I get the same compilation error.

On Wed, Jun 30, 2010 at 4:25 PM, W.P. McNeill <billmcn_at_[hidden]> wrote:

> How do I use an explicit weight map?  I thought specializing property_map<>
> would be the preferred way to add edge weights to a graph that doesn't
> already contain them.
>
> BTW, here is the entire spew up to the first error message:
>
> g++ -g -I/opt/local/include   -c -o main.o main.cpp
> /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor
> ‘boost::transform_iterator<UnaryFunction, Iterator, Reference,
> Value>::transform_iterator() [with UnaryFunc =
> boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>
> >, Iterator = boost::counting_iterator<size_t, boost::use_default,
> boost::use_default>, Reference = boost::use_default, Value =
> boost::use_default]’:
> /opt/local/include/boost/graph/astar_search.hpp:285:   instantiated from
> ‘void boost::astar_search(VertexListGraph&, typename
> boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor,
> PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap,
> CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph =
> boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic =
> boost::euclidean_heuristic, AStarVisitor = boost::astar_goal_visitor,
> PredecessorMap = boost::dummy_property_map, CostMap =
> boost::vector_property_map<float,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, DistanceMap =
> boost::vector_property_map<float,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::edge_weight_map,
> VertexIndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t,
> size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap =
> boost::vector_property_map<boost::default_color_type,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, CompareFunction = std::less<float>,
> CombineFunction = boost::closed_plus<float>, CostInf = float, CostZero =
> float]’
> /opt/local/include/boost/graph/astar_search.hpp:318:   instantiated from
> ‘void boost::detail::astar_dispatch2(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::vector_property_map<float,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, DistanceMap =
> boost::vector_property_map<float,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, 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::vector_property_map<boost::default_color_type,
> boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
> boost::array<size_t, 2ul>, size_t> >, Params =
> boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t,
> boost::no_property>]’
> /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
>
> On Wed, Jun 30, 2010 at 4:09 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:
>
>> 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
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
>
>