Boost logo

Boost Users :

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
>>> 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:
>>> 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:>
>> 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]
> 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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at