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: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-07-14 17:38:15

I used boost::unordered_map for the A* output property maps.

Since I'm also keeping track of a set of vertices to remove from the
filtered graph, I tried implementing this with boost::unordered_set instead
of std::set.  This doesn't build.  The error message is:

maze.cpp:243:   instantiated from here
/src/boost-trunk/boost/graph/filtered_graph.hpp:60: error: no matching
function for call to ‘set_contains(const
boost::unordered_set<vertex_descriptor, vertex_hash,
std::equal_to<vertex_descriptor>, std::allocator<vertex_descriptor> >&,
const boost::array<size_t, 2ul>&)’

What's going on is the vertex_subset_complement_filter calls
is_not_in_subset, which calls set_contains in set_adaptor.hpp, which takes
a std::set as its first argument.  Maybe you'd want to template this set
type too.

I'll keep std::set here, but that might be a good new feature.

On Wed, Jul 14, 2010 at 2:04 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

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