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

Subject: Re: [Boost-users] Boost Graph Lib > A*
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-01-23 20:42:51

On Mon, 11 Jan 2010, Damien Maupu wrote:

> Jeremiah Willcock a écrit :
>> 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
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>> 
>
> Hi,
>
> My graph is growing as the search progress so it is an implicit graph and I 
> understand I have to use the _no_init version (because the doc say so). Why 
> can I just the version with the init? Because if I use the no_init version I 
> need to init the properties map somehow.
>
> I guess the moment the make the graph grows is while visitor does 
> examine_vertex.
> I understand how I can add vertex to the graph, but how should I proceed for 
> the properties map?
> Should I destroy and recreate new one (with the correct size) each time?
>
> Anybody have a working example of the a* working on a implicit graph?

I do not have an example of implicit A*.  What property do you need other 
than the color?  If you only need the color map and are able to accept 
visiting the same vertex multiple times, just use a fake property map that 
always returns "white" no matter what vertex is given.  There is a 
constant_property_map for that.

-- Jeremiah Willcock