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

From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2006-10-11 16:11:14

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_at_[hidden]
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users