Re: [Boost-users] [BGL] A* queue size not mutable

On Tue, 22 Dec 2009, Arnaud Masserann wrote:

Hi,

I'm using the BGL to explore an implicit graph. At the beginning, I only have one node, and no arc. And I instanciate new nodes and their corresponding arc on-the-fly in the A* visitor ( in examine_vertex ).

However, the A* algorithm internally uses this queue :     MutableQueue Q(num_vertices(g), icmp, index_map); which means that I'm supposed to :  - know how many vertices I'm gonna need during the search, which I don't  - Instanciate them all...

Where are you looking? The line I see (in astar_search_no_init) is: MutableQueue Q(cost, index_in_heap, compare); which doesn't require the number of vertices in advance.

Notes : I use astar_search_no_init, and property maps based on std::map so that put() can index it in a not-known-yet location. Btw, my color map type is std::map (plus the wrapper around it). I feel that using "boost::default_color_type" is kind of a hack. Is it ?

The reason is that the normal Boost A* search avoids processing the same vertex twice by using a color map. If you want the implicit graph version that appears in most textbooks, you need a dummy color map that claims that all vertices are unvisited. So it is somewhat a workaround to allow the same algorithm to work for both cases. -- Jeremiah Willcock