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