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

Subject: Re: [Boost-users] Boost Graph Lib > A*
From: Damien Maupu (damien.maupu_at_[hidden])
Date: 2010-01-11 10:07:34

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?

Thank you

Damien