Re: [Boost-users] Boost Graph Lib > A*

Subject: Re: [Boost-users] Boost Graph Lib > A*
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-12-11 20:09:15

On Fri, 11 Dec 2009, Damien Maupu wrote:

> Dear all,
>
> First Hello.
> Then does anybody knows how the a star search works for implicit graph?
> There is little information on the Internet.
>
> I found a pdf:
> A* Graph Search Within the BGL Framework
> http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
>
> But I wasn't able to run the implicit graph example because I am missing:
> #include <nonconst_bfs.hpp>
> and
> #include "test-astar-visitors.hpp"
> #include "test-astar-accept.hpp"
>
> In the online doc:
> http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
> It is said to use astar_search_no_init but I don't know how.
>
> Any clues?

There is an example of A* search at 
<URL:http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp> 
but it uses the version with initialization.  Does your graph have an 
infinite or unknown number of vertices?  If so, use the _no_init version 
by swapping the color and index_map arguments and providing your own color 
map.  You can use 
boost::make_constant_property<vertex_t>(boost::white_color) (where 
vertex_t is your graph's vertex type, with includes of 
<boost/graph/property_maps/constant_property_map.hpp> and 
<boost/graph/properties.hpp>) as the property map if you don't mind having 
the same vertex visited multiple times (for example, for a tree-like 
graph).  If you are having performance problems with multiple visits of 
the same vertices, you will need to use a boost::associative_property_map 
(from <boost/property_map/property_map.hpp>) with a less-then-comparable 
vertex type instead.

-- Jeremiah Willcock