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

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 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(boost::white_color) (where vertex_t is your graph's vertex type, with includes of and ) 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 ) with a less-then-comparable vertex type instead. -- Jeremiah Willcock