Re: [Boost-users] [BGL] Why does astar_search require VertexList?

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2006-10-13 07:29:21

2006/10/13, Rainer Deyke <rainerd_at_[hidden]>:
> Nick Edmonds wrote:
> > astar_search is implemented using breadth_first_visit which does not
> > iterate over all vertices.  The only vertex iteration I can find in
> > astar_search is intialization code to initialize the color, distance,
> > cost, and predecessor property maps.  A version of astar_search,
> > astar_search_no_init is provided which skips this initialization, if
> > you can handle the initialization of these property maps yourself
> > then you should be able to use astar_search_no_init() and eliminate
> > the need to iterate over all vertices.
>
> Looking at the source, it appears that astar_search_no_init indeed
> doesn't iterate over all vertices.  However, it does construct a
> mutable_queue of size num_vertices(), which in my case would allocate no
> less than a gigabyte of memory.

One possibility would be to change asta_seach_no_init so you could
specify your own  MutableQueue (Just move the MutableQueue-typedef to
the template params of astar_seach_no_init). With that, you could
implement your own Queue without creating that fat index_vector. Would
that work?

[snip]
> I was planning on using the visitor to terminate the search (by throwing
> an exception) after finding the destination or when the path becomes too
> long.  I assume at least the former, if not the latter, is supported by BGL.
>
> filtered_graph can remove edges from a graph, but it cannot remove
> vertices (and it does not even affect the number returned by num_edges).
>   As such, it can constrain the range of the path, and indirectly the
> length of the path, but it does not prevent either the iteration over
> the vertices or the allocation of the huge mutable_queue.

Filtered_graph can remove vertices from a graph. It's the same as with edges.
see http://tinyurl.com/y9jbea

The thing with corrected num_vertices (num_edges) is explained here:
http://tinyurl.com/ycq3sq

But I think the argument with "keep the index" doesn't really count
for you. As you don't have your entire graph in memory you don't have
an index, do you?

May I ask what graph representation you are using?

> I could write my own graph adaptor which reduces the full graph to a
> much smaller subgraph, including reducing the vertices reached through
> iteration and the number returned by num_vertices.  It's not an ideal
> solution, but it should prevent at least some of the needless
> initialization and memory allocation.

Yeah, sort of filtered_graph, where especially those things are
considered (updating num_vertices, num_edges, and provide an extra
layer of indirection where old indices are mapped to new ones).
The out-of-memory-graph idea was an SoC project, but it didn't make it
(http://tinyurl.com/ydl8to).
Maybe a filtered-graph with those features is a first attempt for this?

Cheers,
Stephan