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

14 Jul 2010

      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, std::allocator >&,
const boost::array&)’

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