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 20:39:42

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

> On Wed, 14 Jul 2010, W.P. McNeill wrote:
>
>
>>
>> On Wed, Jul 14, 2010 at 3:16 PM, Jeremiah Willcock <jewillco_at_[hidden]>
>> wrote:
>>      On Wed, 14 Jul 2010, W.P. McNeill wrote:
>>
>>      I verified the documentation changes for grid graph indexing calls
>> and A* visitors.  Looks good. Now doing edge weights with
>>      a static_property_map<>.
>>
>>
>> OK.
>>
>>      I've duplicated relevant information from the README at the top of
>> maze.cpp, so README doesn't need to be included in the Boost examples.
>>
>>      I found that I have to implement my own vertex index map, though I'm
>> not sure exactly why.  If I remove all my vertex index map code and
>>      call A* with the
>>      default map like so:
>>
>>          astar_search(m_barrier_grid,
>>                       source(),
>>                       heuristic,
>>                       boost::weight_map(weight).
>>                       predecessor_map(pred_pmap).
>>                       distance_map(dist_pmap).
>>                       visitor(visitor) );
>>
>>      I get the following error:
>>
>> (snip)
>>
>>      That is a bug in astar_search().  Please try with the latest Boost
>> trunk and see if it works.  I also added named parameters to
>>      astar_search_no_init().
>>
>> I tried building with the default index map again against the Boost tree
>> at version 64026 and got the same error as before:
>>
>
> OK.  See if any of the later changes I did affect this too.
>
> All of this is true when building against revision 64030 of Boost.

>
>  graph_traits.hpp:226: error: no type named ‘vertex_property_type’ in
>> ‘class grid’   I noticed that the documentation for the the vertex_index_map
>> parameter says that the graph must have an internal vertex_index property.
>>  Could this be the problem?  If I try to add the following line to a working
>> build:
>>
>> typedef grid::vertex_index grid_vertex_index;
>>
>> I get this error:
>>
>> g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o astar_maze.o
>> astar_maze.cpp
>> astar_maze.cpp:62: error: ‘vertex_index’ in class ‘grid’ does not name a
>> type
>>
>
> What is supposed to work is:
>
> boost::property_map<grid, boost::vertex_index>::const_type pm
>   = get(boost::vertex_index, grid());
>
> If that succeeds, it's an algorithm bug most likely.
>

First, I can't get grid_graph's argumentless constructor to work.  The
following program does not build.

#include <boost/graph/grid_graph.hpp>

int main (int argc, char const *argv[]) {
  boost::grid_graph<2> g = boost::grid_graph<2>();
  return 0;
}

g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o grid.o grid.cpp
grid.cpp: In function ‘int main(int, const char**)’:
/src/boost-trunk/boost/graph/grid_graph.hpp:232: error:
‘boost::grid_graph<DimensionsT, VertexIndexT, EdgeIndexT>::grid_graph()
[with long unsigned int Dimensions = 2ul, VertexIndex = size_t, EdgeIndex =
size_t]’ is private
grid.cpp:4: error: within this context
/src/boost-trunk/boost/graph/grid_graph.hpp: In constructor
‘boost::grid_graph<DimensionsT, VertexIndexT, EdgeIndexT>::grid_graph()
[with long unsigned int Dimensions = 2ul, VertexIndex = size_t, EdgeIndex =
size_t]’:
grid.cpp:4:   instantiated from here
/src/boost-trunk/boost/graph/grid_graph.hpp:232: error: uninitialized member
‘boost::grid_graph<2ul, size_t, size_t>::m_dimension_lengths’ with ‘const’
type ‘const boost::array<size_t, 2ul>’

It looks like the grid_graph() constructor at line grid_graph.hpp 232 needs
to initialize m_dimension_lengths.  (Tricky because you need to use curly
braces and assignment.)

The program does build if you change the line to:

  boost::grid_graph<2> g();

But that's an aside.  In my code can use the m_grid grid graph, which has
already been created.  If I remove all the vertex index code and the call to
astar_search from my program, and add the following line to the
maze::solve() function:

boost::property_map<grid, boost::vertex_index_t>::const_type pm =
get(boost::vertex_index, m_grid);

The program builds.  Does that indicate that it's a problem with
astar_search then?

>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>