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-14 17:09:45

I verified the documentation changes for grid graph indexing calls and A*
visitors.  Looks good.

Now doing edge weights with a static_property_map<>.

I've duplicated relevant information from the README at the top of maze.cpp,
so README doesn't need to be included in the Boost examples.

I found that I have to implement my own vertex index map, though I'm not
sure exactly why.  If I remove all my vertex index map code and call A* with
the default map like so:

    astar_search(m_barrier_grid,
                 source(),
                 heuristic,
                 boost::weight_map(weight).
                 predecessor_map(pred_pmap).
                 distance_map(dist_pmap).
                 visitor(visitor) );

I get the following error:

g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o maze.o maze.cpp
/src/boost-trunk/boost/graph/graph_traits.hpp: In instantiation of
‘boost::vertex_property_type<grid>’:
/src/boost-trunk/boost/graph/filtered_graph.hpp:226:   instantiated from
‘boost::vertex_property_type<boost::filtered_graph<grid, boost::keep_all,
boost::is_not_in_subset<vertex_set> > >’
/src/boost-trunk/boost/graph/properties.hpp:202:   instantiated from
‘boost::detail::vertex_property_map<boost::filtered_graph<grid,
boost::keep_all, boost::is_not_in_subset<vertex_set> >,
boost::vertex_index_t>’
/src/boost-trunk/boost/graph/properties.hpp:251:   instantiated from
‘boost::property_map<boost::filtered_graph<grid, boost::keep_all,
boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’
/src/boost-trunk/boost/graph/named_function_params.hpp:243:   instantiated
from
‘boost::detail::choose_default_param::bind_<boost::detail::error_property_not_found,
boost::filtered_graph<grid, boost::keep_all,
boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’
/src/boost-trunk/boost/graph/named_function_params.hpp:276:   instantiated
from
‘boost::detail::choose_pmap_helper<boost::detail::error_property_not_found,
boost::filtered_graph<grid, boost::keep_all,
boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’
/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 = filtered_grid,
AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T =
boost::graph_visitor_t, R =
boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>,
boost::vertex_distance_t,
boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>,
boost::vertex_predecessor_t,
boost::bgl_named_params<maze::solve()::edge_weight_pmap,
boost::edge_weight_t, boost::no_property> > >]’
maze.cpp:229:   instantiated from here
/src/boost-trunk/boost/graph/graph_traits.hpp:226: error: no type named
‘vertex_property_type’ in ‘class grid’
/src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void
boost::astar_search(const VertexListGraph&, typename
boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const
boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid,
AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T =
boost::graph_visitor_t, R =
boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>,
boost::vertex_distance_t,
boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>,
boost::vertex_predecessor_t,
boost::bgl_named_params<maze::solve()::edge_weight_pmap,
boost::edge_weight_t, boost::no_property> > >]’:
maze.cpp:229:   instantiated from here
/src/boost-trunk/boost/graph/astar_search.hpp:370: error: no matching
function for call to
‘choose_const_pmap(boost::detail::error_property_not_found, const
boost::filtered_graph<grid, boost::keep_all,
boost::is_not_in_subset<vertex_set> >&, boost::vertex_index_t)’
make: *** [maze.o] Error 1

I was surprised by this because I expected the filtered graph to inherit the
grid graph's vertex index map like you describe.

On Wed, Jul 14, 2010 at 1:43 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Wed, 14 Jul 2010, W.P. McNeill wrote:
>
>  A-Star-Maze solver is pretty much done.  The filtered_graph does make the
>> code a lot simpler.  I used lexical_cast and Boost's random number
>> facilities, but decided the Boost command line processing code was overkill
>> for this example. The warnings you added about not subclassing BGL types
>> look good.
>>
>
> OK.
>
>  Two things that look like documentation errors:
>>  1. On the A* search page, the examine_vertex prototype for the visitor is
>> listed as vis.examine_vertex(u, g), but you actually need it to
>>
>>    be vis.examine_vertex(u, const g) in order for the code the build.
>>  (This may be true for the other visitor functions as well.)  This tripped
>> me up when
>>    I first wrote my visitor class.  I'm not sure if you want to specify
>> the constants here, or let them be assumed.
>>  2. The grid graph indexing documentation incorrectly states that you get
>> a vertex index with get(boost::vertex_index, vertex_descriptor, const
>> Graph&).
>>
>>     The order of the last two parameters is switched.  The header actually
>> specifies get(boost::vertex_index, const Graph&, vertex_descriptor).  This
>>    appears to be the case in the documentation for a number of the
>> get(...) functions.
>>
>
> I believe I fixed both of these now.  Please check.
>
> BTW, you don't need to create your own weight map if the weights are all
> the same; just use something like static_property_map<double>(1.) as the
> weight map.  Also, why do you need your own vertex index map?  It appears to
> just forward to the grid graph's version; why not just use that one
> directly?  It appears that filtered_graph forwards property map requests to
> the underlying graph by default anyway, so you might just be able to remove
> that argument from your call to astar_search.  You also don't need to call
> num_vertices() on the underlying graph; calling it on the filtered_graph
> does the same thing.  Does your random_int() function re-seed the RNG to get
> a different answer each time?
>
> I think overall that your code is nearly ready to put in.  What did you
> want me to do with the README.md file?  Put that in the documentation
> somewhere, or is most of the content in there about building it outside
> Boost (where it will build with the rest of the BGL examples using
> Boost.Build)?
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>