Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-14 17:04:25

On Wed, 14 Jul 2010, W.P. McNeill wrote:

> I intentionally used associative_property_map<> structures for the 
> predecessor and distance maps for space efficiency.  Since I know not 
> every vertex in the grid will be visited, it made sense to have a map 
> keyed on vertices rather than a vector with elements for all the 
> vertices.  Am I right in thinking that iterator_property_map won't work 
> for this implementation?  (Since std::map does not model a Random Access 
> Iterator.) Of course for time efficiency it may still be better to 
> create vectors for the entire grid rather than maps, particularly for 
> small mazes.  But I want to use maps to illustrate the principle.  Also, 
> a hash map would be better than std::map, but there's no standard hash 
> map implementation so I stay away from it.  (I'm waiting for a Boost 
> hash_map :-)

OK, although here it might be worth wasting the space.  I don't think an 
iterator_property_map will work on an std::map.  There is a Boost hash_map 
-- it's named boost::unordered_map.

> Using map structures brings up another question: am I correct in 
> thinking that astar_search_no_init(...) does not permit named parameters 
> so that I have to create all the various maps myself?  (That is what I 
> have gleaned from looking at the source and experimenting, but I've been 
> wrong before.)  I ask because the real project I'm using this maze 
> search as a warmup for is aimed at a class of problems where most of the 
> grid is not visited, so I want to  avoid the O(V) initialization by 
> calling astar_search_no_init(...) with maps that have the correct 
> default values.

It appears that it doesn't allow named parameters, so right now you need 
to fill all of the parameters manually.  That could be added later if it 
was important.

-- Jeremiah Willcock