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-07-06 17:38:21

I checked out the Boost trunk from http://svn.boost.org/svn/boost/trunk and
rebuilt the program below using those headers.  It builds and runs.  From
now on unless I say otherwise, everything I do uses this version of Boost.

Next I tried to add distance and predecessor maps for the output.  Following
the astar-cities.cpp example, I implemented these as vectors.  The program
now looks like this:

#include <boost/graph/astar_search.hpp>
#include <boost/graph/grid_graph.hpp>
#include <iostream>
#include <vector>

using namespace boost;

typedef grid_graph<2> grid;
typedef graph_traits<grid> traits;
typedef traits::vertex_descriptor vertex_descriptor;
typedef traits::edge_descriptor edge_descriptor;

typedef double edge_weight_type;

struct zero_heuristic:public
  boost::astar_heuristic<grid, edge_weight_type> {

  edge_weight_type operator()(vertex_descriptor v) {
    return 0;
  }
};

int main (int argc, char const *argv[]) {
  array<size_t, 2> sizes = {{ 3, 2 }};
  grid g(sizes);
  shared_array_property_map<edge_weight_type,
                            property_map<grid, edge_index_t>::const_type>
                            weight(num_edges(g), get(edge_index, g));
  std::vector<vertex_descriptor> p(num_vertices(g));
  std::vector<edge_weight_type> d(num_vertices(g));

  vertex_descriptor start = vertex(0, g);

  astar_search(g,
               start,
               zero_heuristic(),
               weight_map(weight).
               predecessor_map(&p[0]).distance_map(&d[0]) );

  return 0;
}

It now fails to compile because of what looks like a missing put() functions
for the distance and predecessor maps.  The top of the error spew looks
contains a distance map error that looks like this:

g++ -g -I/src/boost-trunk   -c -o main.o main.cpp
/src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void
boost::astar_search(const 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 = zero_heuristic,
AStarVisitor = boost::astar_visitor<boost::null_visitor>, PredecessorMap =
vertex_descriptor*, CostMap = boost::vector_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
boost::array<size_t, 2ul>, size_t> >, DistanceMap = edge_weight_type*,
WeightMap = boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
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<edge_weight_type>, CombineFunction =
boost::closed_plus<edge_weight_type>, CostInf = double, CostZero = double]’:
/src/boost-trunk/boost/graph/astar_search.hpp:319:   instantiated from ‘void
boost::detail::astar_dispatch2(const 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 =
zero_heuristic, CostMap = boost::vector_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
boost::array<size_t, 2ul>, size_t> >, DistanceMap = edge_weight_type*,
WeightMap = boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
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<edge_weight_type*, boost::vertex_distance_t,
boost::bgl_named_params<vertex_descriptor*, boost::vertex_predecessor_t,
boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
boost::edge_weight_t, boost::no_property> > >]’
/src/boost-trunk/boost/graph/astar_search.hpp:348:   instantiated from ‘void
boost::detail::astar_dispatch1(const 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 =
zero_heuristic, CostMap = boost::detail::error_property_not_found,
DistanceMap = edge_weight_type*, WeightMap =
boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
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<edge_weight_type*, boost::vertex_distance_t,
boost::bgl_named_params<vertex_descriptor*, boost::vertex_predecessor_t,
boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
boost::edge_weight_t, boost::no_property> > >]’
/src/boost-trunk/boost/graph/astar_search.hpp:370:   instantiated from ‘void
boost::astar_search(const VertexListGraph&, typename
boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const
boost::bgl_named_params<P, T, R>&) [with VertexListGraph = grid,
AStarHeuristic = zero_heuristic, P = edge_weight_type*, T =
boost::vertex_distance_t, R = boost::bgl_named_params<vertex_descriptor*,
boost::vertex_predecessor_t,
boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type,
boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>,
std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >,
boost::edge_weight_t, boost::no_property> >]’
main.cpp:41:   instantiated from here
/src/boost-trunk/boost/graph/astar_search.hpp:289: error: no matching
function for call to ‘put(edge_weight_type*&, boost::array<size_t, 2ul>,
double&)’
...

Further down there's another missing put function for the predecessor map.

...
/src/boost-trunk/boost/graph/astar_search.hpp:291: error: no matching
function for call to ‘put(vertex_descriptor*&, boost::array<size_t, 2ul>,
boost::array<size_t, 2ul>)’
/src/boost-trunk/boost/graph/astar_search.hpp:319:   instantiated from
‘void
...

I thought I didn't have to write my own put() functions if I was passing in
distance and predecessor map objects external to the graph.  Plus, if I did
try to write my own put functions, they'd have to be able to look up vertex
indexes from vertex descriptors, which means they need access to the graph
object in order to call vertex(...), which means I can't use a simple
vector.

On Tue, Jul 6, 2010 at 10:41 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Tue, 6 Jul 2010, W.P. McNeill wrote:
>
>  Looking through the error spew again, there are actually two errors.  The
>> first is the one I already showed you.  Then beneath that there's another
>> big error
>> stack that winds through various astar_dispatch functions and ends with no
>> matching function call to boost::detail::grid_graph_out_edge_at.
>> main.cpp:38:   instantiated from here
>> /opt/local/include/boost/iterator/transform_iterator.hpp:100: error: no
>> matching function for call to
>> ‘boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t,
>> size_t> >::grid_graph_out_edge_at()’
>> /opt/local/include/boost/graph/grid_graph.hpp:128: note: candidates are:
>> boost::detail::grid_graph_out_edge_at<Graph>::grid_graph_out_edge_at(typename
>> boost::graph_traits<G>::vertex_descriptor, const Graph*) [with Graph =
>> boost::grid_graph<2ul, size_t, size_t>]
>> /opt/local/include/boost/graph/grid_graph.hpp:119: note:
>> boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t>
>> >::grid_graph_out_edge_at(const
>> boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t>
>> >&)
>> make: *** [main.o] Error 1
>>
>> Presumably the same issue.
>>
>
> Yes.  This has been fixed in Boost trunk, though, so please try the copy of
> grid_graph.hpp from there.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>