Hi there -- long-time reader, first-time poster!<br><br>I&#39;ve been trying to use astar_search from the graph library for a little problem I&#39;m working on. Specifically, I wanted to use it to perform a search on an implicit graph (more specifically, an implicit tree), as touched on briefly in the docs for astar_search. In this case, I&#39;m using boost 1.33.1<br>
<br>Unfortunately, this doesn&#39;t appear to be well supported &quot;out of the box&quot;. Google didn&#39;t turn up much on the subject, except for a paper done by Kris Beevers and Jufeng Peng (<span class="a"><a href="http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf">www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf</a>) which mentions the need for a non-const version of the breadth-first search code in BGL, and a message to the list from Ian Downes, Feb 28th, asking about doing an implicit search as well (couldn&#39;t find any followups).<br>
<br>Using Beevers paper as a template, I started bumping into some serious memory corruptions problems with my test-cases. Finally today I ran the tests under valgrind and managed to track it down to mutable_queue (boost/pending/mutable_queue.hpp), which is used by the astar_search code to manage the set of partial solutions.<br>
<br>mutable_queue is constructed with a vector of integers, index_array, sized to the initial size of the implicit graph (1 vertex in my case). Unfortunately, this vector is never resized, so calls to mutable_queue::push wind up walking off the end of the index_array vector </span><span class="a">as the graph gets expanded (by my astar_visitor::examine_vertex callback)</span><span class="a">, with various undefined (but generally bad) side-effects.<br>
<br>So, after some mucking around, I&#39;ve wound up with a solution to this where I specialize mutable_queue for my graph&#39;s vertex type, leaving astar_search and the standard mutable_queue definitions alone. The specialization is basically a copy of mutable_queue.hpp, with a change to the push method to ensure that index_array is sized correctly before indexing into it. Problem solved, everything working like a charm.<br>
<br>Now, is this a bug in mutable_queue? Reading the two-paragraph description in mutable_queue.hpp, I&#39;d guess this is how it is supposed to act. This would mean that implicit search with astar_search (and presumably any other search) isn&#39;t supported, because the queue that it uses for partial results can&#39;t get bigger as the graph itself grows. The documentation probably shouldn&#39;t mention implicit search if this is the case, or maybe there is need for a non-const version of astar_search that can use a more appropriate queue type... My solution, though it seems to work fine, is a bit of a bodge...<br>
<br>As a side-note, I initially thought that the memory corruption that I was seeing was a result of vertex iterators becoming invalidated as the graph was expanded. I attempted a switch over to using listS for the VertexList parameter of the adjacency_list template (from vecS), but this causes all sorts of compiler errors under gcc <a href="http://4.1.2.">4.1.2.</a> I tried making a similar change to the astar_search example program (astar-cities.cpp) and this too fails to compile (with 1.33.1 and 1.34.1). Shouldn&#39;t listS and vecS for the VertexList parameter be interchangeable?<br>
<br><br>Cheers,<br>Oliver<br></span>