Boost logo

Boost Users :

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 =
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]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at