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

Subject: Re: [Boost-users] Boost Graph Lib > A*
From: Damien Maupu (damien.maupu_at_[hidden])
Date: 2010-02-09 10:27:24

Hi Jeremiah,

Thank for your help.
I succeed in doing what I wanted.
My implicit graph's vertex have as internal properties all features 
needed by Astar instead of using external property map.
I know it make sense but it wasn't for me at the beginning.
I am using bundle properties and calling them with the proper mechanism 
while loading property map.

Thank

Damien

Jeremiah Willcock a écrit :
> 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