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:
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
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users