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 16:26:58

A-Star-Maze solver <http://github.com/wpm/Astar-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.

Two things that look like documentation errors:

   1. On the A*
search<http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/astar_search.html>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<http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/grid_graph.html#indexing>
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.

On Wed, Jul 14, 2010 at 11:59 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Tue, 13 Jul 2010, W.P. McNeill wrote:
>
>  Different out edge iterators was the problem for my filtered graph
>> example.
>> It's spelled "compliment" in filtered_graph.hpp lines 507-516.  I guess
>> that's a bug.
>>
>
> I fixed that now in the trunk (r64016); the old version is still around for
> compatibility reasons.  Please use the new name.
>
>
>  Here's a working subset_compliment_filter example.  I did my own graph
>> printing rather than using print_graph(...) in graph_utility.hpp because it
>> seemed easier than defining an vertex property for an implicit graph.
>>
>
> You can also use write_graphviz_dp() to do your printing; that will allow
> you to just fill in a dynamic_properties() object with whatever external
> property maps you want.  There is also a function_property_map that's not in
> BGL but you can find by searching the Boost mailing lists; you can use that
> to create your vertex names, or you can just create a
> shared_array_property_map that you fill in manually with the names.
>
> I also added warnings in graph_concepts.html and graph_traits.html about
> subclassing BGL graphs.  Please see if you like the wording or if you think
> there are any other places those warnings need to be.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>