Boost logo

Boost Users :

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

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at