2006/10/13, Rainer Deyke
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.
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]
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.
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?
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? Cheers, Stephan