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 00:50:10

Let me start over with code based on random_spanning_tree_test.cpp.
 Ultimately I'm going to want my edge weights to be calculated on the fly
instead of read from a pre-populated array, but getting this to work would
be a good starting point.

I've defined a trivial astar search over a grid_graph with weights stored in
a shared_array_property_map.  The program looks like this:

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

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

  vertex_descriptor start = vertex(0, g);

  astar_search(g,
               start,
               zero_heuristic(),
               weight_map(weight) );

  return 0;
}

It fails to compile with an error about missing a function
for boost::detail::grid_graph_vertex_at():

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]’:
astar_search.hpp:286:   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 = zero_heuristic,
AStarVisitor = boost::astar_visitor<boost::null_visitor>, PredecessorMap =
boost::dummy_property_map, 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 =
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> >, 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]’
astar_search.hpp:319:   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 =
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 =
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> >, 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<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>]’
astar_search.hpp:348:   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 =
zero_heuristic, CostMap = boost::detail::error_property_not_found,
DistanceMap = boost::detail::error_property_not_found, 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<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>]’
astar_search.hpp:370:   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 = grid,
AStarHeuristic = zero_heuristic, P =
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> >,
T = boost::edge_weight_t, R = boost::no_property]’
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_vertex_at<boost::grid_graph<2ul, size_t, size_t>
>::grid_graph_vertex_at()’
/opt/local/include/boost/graph/grid_graph.hpp:104: note: candidates are:
boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const
Graph*) [with Graph = boost::grid_graph<2ul, size_t, size_t>]
/opt/local/include/boost/graph/grid_graph.hpp:100: note:
boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>
>::grid_graph_vertex_at(const
boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>
>&)

This happens both with version 1.42 of astar_search.hpp and with the version
I pulled from the SVN tree that has the fix for bug 3917.

On Mon, Jul 5, 2010 at 2:06 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Mon, 5 Jul 2010, W.P. McNeill wrote:
>
>  I'm using my own graph class because I need an implicit graph for the task
>> I'm trying to do.
>>
>> Here's the full background: I'm writing a program that solves a maze using
>> a-star search.  (It's on github as Searchable Graph Example.)
>>  The maze is a grid of cells in which you can move up, down, right and
>> left.  Cells are either empty or blocked.  The cost of entering an
>> empty cell is 1, and the cost of entering a blocked cell is infinity.
>> (This is actually a warm-up for a more sophisticated graph search program,
>> but that one also operates on a grid, so a lot of this code
>> will be reusable.  Plus, I think an a-star maze search example would be
>> useful for others to see.)
>>
>> Because the graph topology is a grid, it seemed like the best way to
>> implement this is with an implicit graph.  I first tried adding edge
>> and vertex properties to Boost's grid_graph class, but I ran into compile
>> errors, some of which are documented earlier in this thread.
>>  Even after I worked around those errors I hit others, and it seemed like
>> I was writing an awful lot of boilerplate code to use
>> grid_graph, so it would be easier to implement my own grid.
>>
>> Now I'm writing my own grid class (called maze_search::maze in the code on
>> github).  It will have an out edge iterator that determines
>> the the grid structure, a read/write boolean vertex property for whether
>> or not a cell is blocked, and a read-only edge weight property
>> that returns the cost of entering a cell.  I've finished the iterator and
>> the edge weight property, and am starting to look at the vertex
>> property.
>>
>
> Why not just have a class that contains a grid_graph and property maps for
> the vertices and edges?  You can use grid_graph's vertex_index and
> edge_index maps to provide indices for iterator_property_maps for those
> properties.  You can also use external properties that you keep as separate
> data structures and pass into algorithms explicitly; that I think would be
> much easier than what you're doing.  The Knight's Tour example uses
> something similar, but its property map implementation is custom and
> overcomplicated because the graph there doesn't have vertex_index and
> edge_index properties.  If you look in
> libs/graph/test/random_spanning_tree_test.cpp (in the trunk and 1.44), there
> is an example of using external properties with a grid_graph.  It just seems
> to me that what you're doing should not require a new graph type and should
> actually be fairly simple, even if it doesn't seem that way from the
> documentation.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>