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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-12 16:12:04

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