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 13:14:12

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.

On Mon, Jul 5, 2010 at 9:50 PM, W.P. McNeill <billmcn_at_[hidden]> wrote:

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