Boost logo

Boost Users :

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-14 16:43:17

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.


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

-- Jeremiah Willcock

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