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

From: Rainer Deyke (rainerd_at_[hidden])
Date: 2006-10-14 15:09:52

Stephan Diederich wrote:
> 2006/10/13, Rainer Deyke <rainerd_at_[hidden]>:
>>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?

It would work, but I'm not too keen not the idea of having to implement 
my own MutableQueue to get what I believe should be the default behavior.

The documentation mentions that A* could be used for "implicit" graphs 
where the neighbors of a vertex are generated when that vertex is first 
visited.  The size of such implicit graphs may not be known ahead of 
time, and may very well be infinite.  I agree that the A* algorithm 
would be useful for searching such graphs.  However, this can only 
happen if the algorithm if the implementation does no require the graph 
to be a VertexList.

> May I ask what graph representation you are using?

My graph is essentially a 2D grid.  Each cell of the grid is a vertex in 
the graph, and is potentially connected to its four neighbors.  The main 
optimization is that the grid is divided into blocks of 16x16 cells, 
where each block can be reused several times across the entire grid. 
The blocks are loaded from disk on demand.  My vertex_descriptor is a 
pair of integers, indicating the row and column on the grid.  My 
edge_descriptor is just a pair of vertex_descriptors.

>>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?

I was actually thinking of just limiting the row and column of my grid 
cells to a specific range in the adaptor class that I need in order to 
use the BGL with my graph.  A generalized enhanced filterd_graph would 
of course also work.

-- 
Rainer Deyke - rainerd_at_[hidden]