Hi there -- long-time reader, first-time poster! I've been trying to use astar_search from the graph library for a little problem I'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'm using boost 1.33.1 Unfortunately, this doesn't appear to be well supported "out of the box". Google didn't turn up much on the subject, except for a paper done by Kris Beevers and Jufeng Peng (www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf) 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't find any followups). 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. 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 as the graph gets expanded (by my astar_visitor::examine_vertex callback), with various undefined (but generally bad) side-effects. So, after some mucking around, I've wound up with a solution to this where I specialize mutable_queue for my graph'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. Now, is this a bug in mutable_queue? Reading the two-paragraph description in mutable_queue.hpp, I'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't supported, because the queue that it uses for partial results can't get bigger as the graph itself grows. The documentation probably shouldn'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... 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 4.1.2. 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't listS and vecS for the VertexList parameter be interchangeable? Cheers, Oliver