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@osl.iu.edu> 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