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

Subject: Re: [Boost-users] [BGL] A* queue size not mutable
From: Arnaud Masserann (arnaud1602_at_[hidden])
Date: 2009-12-22 13:00:14

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<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.
>

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 ?