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. This is significantly more than I can afford. (If I loaded my entire graph into memory, which I currently don't, it would probably still be less than 10 megabytes in size due to the data structures I use.) If mutable_queue allocated memory as needed instead of allocating all of it up-front, there would not be a problem. In my case, a typical search does not need to examine more than 100 nodes.

Let me know if you have found another case (that I have overlooked) where astar_search explicitly iterates over all vertices. Also, BFS _will_ explore all vertices with paths to the source vertex so if you wish to constrain the 'depth' of the astar_search then you may want to use a filtered_graph or some other method (i.e. playing tricks with the color map) to limit the size/scope of the search.

If I wanted to find all paths from the source vertex, I would use the simpler Dijkstra's algorithm. The difference between Dijkstra's algorithm and A* is that the latter uses a heuristic function to quickly home in on the destination vertex, but that is only an advantage when the search is terminated after finding the destination. 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. 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. -- Rainer Deyke - rainerd@eldwood.com

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