[Boost-users] [BGL] implicit astar_search weirdness, bug in mutable_queue?

From: Oliver Seiler (oseiler_at_[hidden])
Date: 2008-04-21 16:54:45

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