Where are you looking?  The line I see (in astar_search_no_init) is:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<br>
    MutableQueue Q(cost, index_in_heap, compare);<br>
<br>
which doesn&#39;t require the number of vertices in advance.</blockquote><div><br>So implicit graphs have been implemented since boost 1.39 ... Are you aware of any implementation notes, documentation, reference ? I&#39;ll give it a try tonight.<br>
 </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im"><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Notes :<br>
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.<br>
Btw, my color map type is std::map&lt;NodeID,boost::default_color_type &gt; (plus the wrapper around it). I feel that using<br>
&quot;boost::default_color_type&quot; is kind of a hack. Is it ?<br>
</blockquote>
<br></div>
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.<br>
</blockquote><div><br>That was not exactly my question. The thing is, I discovered the type &quot;boost::default_color_type&quot; while watching internal boost headers I&#39;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&#39;s point of view, but the code would be better.<br>
More importantly, what are the logical steps I should have done to figure it out ?<br></div></div>