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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-14 20:04:13

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.

> 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.

-- Jeremiah Willcock