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

From: Rainer Deyke (rainerd_at_[hidden])
Date: 2006-10-12 18:25:14

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_at_[hidden]