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-12 15:45:36

I've got a working A-star maze solver.  The code is checked into the
github Astar-Maze-Solver
project <http://github.com/wpm/Astar-Maze-Solver>.  I've tried to put it
into a format in which it can be added to the Boost examples directory.

A little post-mortem.  A certain amount of difficultly for a newcomer to use
the BGL is the price you pay for getting such a powerful and flexible
toolkit.  However, I can identify three specific things that contributed to
the challenge of writing this sample:

   1. A lack of examples of running A-star search on implicit graphs.
   2. A-star search bugs in Boost 1.43 that are fixed in the latest source.
   3. My confusion about whether or not to subclass Boost Graph Library
   structures.

(1) I hope this code can help other people with.

(2) hit me because I'm developing on OS X and getting my Boost from
MacPorts, which currently only has released version 1.42.  It won't be an
issue for people building against the latest version.

(3) caused me to go down a few blind alleys.  I by trying to subclass
grid_graph, and when that didn't work made grid_graph a member of my own
maze class.  Later still, I found that what I really needed was a grid graph
from which I could selectively remove edges.  I would have liked to have
used grid_graph and just subclassed its out edge iterator, but since
subclassing BGL components is a bad idea I ended up writing my own grid
implementation.

I've seen it mentioned elsewhere on this board, but I'll also suggest that a
warning about subclassing BGL components should be prominent in the
documentation.

Thanks for your help getting this and the implicit graph example into shape.
 If there are more tweaks that would make them more suitable for the Boost
examples directory, let me know.

2010/7/10 Jeremiah Willcock <jewillco_at_[hidden]>

> On Fri, 9 Jul 2010, W.P. McNeill wrote:
>
>  Is there a separate ticket number for this?  I'd like to put these in the
>> README. BTW This is starting to come together now.  I should have a working
>> maze search example soon.
>>
>
> I don't see a ticket for the bug -- I think you reported it through an
> email to the Boost list and not a formal ticket.  The trunk fix is in r63333
> and the release branch fix is in r63554.  The fix should be in 1.44 (I'm
> pretty sure, but you might want to check to be really safe).  You can just
> grab grid_graph.hpp from the release branch (
> https://svn.boost.org/svn/boost/branches/release/boost/graph/grid_graph.hpp)
> if you want to try it yourself.
>
> -- Jeremiah Willcock
>
>
>
>> On Tue, Jul 6, 2010 at 10:41 AM, Jeremiah Willcock <jewillco_at_[hidden]>
>> wrote:
>>      On Tue, 6 Jul 2010, W.P. McNeill wrote:
>>
>>            Looking through the error spew again, there are actually two
>> errors.  The first is the one I already showed you.  Then beneath that
>>            there's another big error
>>            stack that winds through various astar_dispatch functions and
>> ends with no matching function call to
>>            boost::detail::grid_graph_out_edge_at.
>>            main.cpp:38:   instantiated from here
>>            /opt/local/include/boost/iterator/transform_iterator.hpp:100:
>> error: no matching function for call to
>>            ‘boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
>> size_t, size_t> >::grid_graph_out_edge_at()’
>>            /opt/local/include/boost/graph/grid_graph.hpp:128: note:
>> candidates are:
>>
>>  boost::detail::grid_graph_out_edge_at<Graph>::grid_graph_out_edge_at(typename
>>            boost::graph_traits<G>::vertex_descriptor, const Graph*) [with
>> Graph = boost::grid_graph<2ul, size_t, size_t>]
>>            /opt/local/include/boost/graph/grid_graph.hpp:119: note:
>>           boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul,
>>            size_t, size_t>
>>            >::grid_graph_out_edge_at(const
>> boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t>
>> >&)
>>            make: *** [main.o] Error 1
>>
>>            Presumably the same issue.
>>
>>
>> Yes.  This has been fixed in Boost trunk, though, so please try the copy
>> of grid_graph.hpp from there.
>>
>> -- Jeremiah Willcock
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>>
>>
>>
>>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>