Boost Users :
Subject: Re: [Boost-users] [BGL] A* queue size not mutable
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-12-22 12:07:49
On Tue, 22 Dec 2009, Arnaud Masserann wrote:
> 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<NodeID,boost::default_color_type > (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
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net