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

Stephan Diederich wrote:

2006/10/13, Rainer Deyke :

...

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@eldwood.com