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://listarchives.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