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

Subject: Re: [Boost-users] [BGL] A* queue size not mutable
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-12-26 15:34:25

On Tue, 22 Dec 2009, Arnaud Masserann wrote:

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

I don't think there is separate documentation; allowing implicit graphs 
was a fix for a bug that was in Trac.

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

You could define your own color type if you want as well.  It would 
probably be difficult to figure out, though.  It might be better to have a 
tree search version of A* that automatically does _no_init and a fake 
color map.  Could you please submit a feature request on svn.boost.org for 
this functionality?  Thank you.

-- Jeremiah Willcock