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:44:09

I intentionally used associative_property_map<> structures for the
predecessor and distance maps for space efficiency.  Since I know not every
vertex in the grid will be visited, it made sense to have a map keyed on
vertices rather than a vector with elements for all the vertices.  Am I
right in thinking that iterator_property_map won't work for this
implementation?  (Since std::map does not model a Random Access Iterator.)

Of course for time efficiency it may still be better to create vectors for
the entire grid rather than maps, particularly for small mazes.  But I want
to use maps to illustrate the principle.  Also, a hash map would be better
than std::map, but there's no standard hash map implementation so I stay
away from it.  (I'm waiting for a Boost hash_map :-)

Using map structures brings up another question: am I correct in thinking
that astar_search_no_init(...) does not permit named parameters so that I
have to create all the various maps myself?  (That is what I have gleaned
from looking at the source and experimenting, but I've been wrong before.)
 I ask because the real project I'm using this maze search as a warmup for
is aimed at a class of problems where most of the grid is not visited, so I
want to  avoid the O(V) initialization by
calling astar_search_no_init(...) with maps that have the correct default
values.

On Mon, Jul 12, 2010 at 1:12 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Mon, 12 Jul 2010, W.P. McNeill wrote:
>
>  I've got a working A-star maze solver.  The code is checked into the
>> github Astar-Maze-Solver project.  I've tried to put it into a format in
>> which it can be
>> added to the Boost examples directory.
>> A little post-mortem.  A certain amount of difficultly for a newcomer to
>> use the BGL is the price you pay for getting such a powerful and flexible
>> toolkit.
>>  However, I can identify three specific things that contributed to the
>> challenge of writing this sample:
>>  1. A lack of examples of running A-star search on implicit graphs.
>>  2. A-star search bugs in Boost 1.43 that are fixed in the latest source.
>>  3. My confusion about whether or not to subclass Boost Graph Library
>> structures.
>>
>
> One more that has hit other people is named parameters (especially the
> thing about using "." between arguments rather than ",").
>
>
>  (1) I hope this code can help other people with.
>>
>
> Yes, and thank you for doing the example.
>
>
>  (2) hit me because I'm developing on OS X and getting my Boost from
>> MacPorts, which currently only has released version 1.42.  It won't be an
>> issue for people building against the latest version.
>>
>
> OK.  I don't think anyone had tried astar_search with an implicit graph
> before the earliest bug report on the issue (the first one, though, was
> about implicit graphs that don't have num_vertices() and astar_search's
> failure on those).
>
>
>  (3) caused me to go down a few blind alleys.  I by trying to subclass
>> grid_graph, and when that didn't work made grid_graph a member of my own
>> maze class.  Later still, I found that what I really needed was a grid graph
>> from which I could selectively remove edges.  I would have liked to have
>> used grid_graph and just subclassed its out edge iterator, but since
>> subclassing BGL components is a bad idea I ended up writing my own grid
>> implementation.
>>
>
> The subclassing thing is based on STL; you are not supposed to subclass STL
> containers either.  If you want to selectively remove edges, look at
> boost::graph::filtered_graph (
> http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/filtered_graph.html).
> You should be able to wrap that on top of the existing grid_graph.
>
>
>  I've seen it mentioned elsewhere on this board, but I'll also suggest that
>> a warning about subclassing BGL components should be prominent in the
>> documentation.
>>
>
> Where do you think that should go?
>
>
>  Thanks for your help getting this and the implicit graph example into
>> shape.  If there are more tweaks that would make them more suitable for the
>> Boost examples directory, let me know.
>>
>
> One minor thing: maze_traversal_catetory should be maze_traversal_category.
>  I think using filtered_graph might replace all of that code, however.  You
> might also want to use iterator_property_map or shared_array_property_map
> instead of associative_property_map for performance.  If you want to really
> make the code Boost-like (and I'm not suggesting or requiring that you do
> this), you can also use Boost.Program_options, Boost.Lexical_cast and
> Boost.Random to replace the corresponding C functions that you are using
> now.  You are also free to use "using namespace std;" and/or "using
> namespace boost;" in examples; you can put those in if you think it will
> make the code more readable.
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>