[BGL] Why does astar_search require VertexList?
I am in need of a path-finding function, and decided to give astar_search from BGL a try. However, I have found to my surprise that astar_search requires a VertexList graph. Looking at the source code, I see that it does indeed try to iterate over all vertices. I find this unreasonable. My graph is not infinite, but it is large, and iterating over several hundred million vertices would completely kill performance for me. (I intend to perform several of these searches per millisecond.) I know for a fact that it is possible to implement A* without iterating over all vertices. What is the rationale behind the current astar_search implementation? -- Rainer Deyke - rainerd@eldwood.com
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. 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. -Nick Edmonds On Oct 10, 2006, at 1:29 AM, Rainer Deyke wrote:
Nick Edmonds wrote:
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.
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
2006/10/13, Rainer Deyke
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? [snip]
Filtered_graph can remove vertices from a graph. It's the same as with edges. see http://tinyurl.com/y9jbea The thing with corrected num_vertices (num_edges) is explained here: http://tinyurl.com/ycq3sq But I think the argument with "keep the index" doesn't really count for you. As you don't have your entire graph in memory you don't have an index, do you? May I ask what graph representation you are using?
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? Cheers, Stephan
Stephan Diederich wrote:
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 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
participants (3)
-
Nick Edmonds -
Rainer Deyke -
Stephan Diederich