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

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.

So implicit graphs have been implemented since boost 1.39 ... Are you aware of any implementation notes, documentation, reference ? I'll give it a try tonight.

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.

That was not exactly my question. The thing is, I discovered the type "boost::default_color_type" while watching internal boost headers I'm not really supposed to look at as an end-user. I feel like I should have used something like boost::color_map::type or whatever. This would be exactly the same from the compiler's point of view, but the code would be better. More importantly, what are the logical steps I should have done to figure it out ?