Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search

On Wed, Jul 14, 2010 at 5:04 PM, Jeremiah Willcock wrote:

On Wed, 14 Jul 2010, W.P. McNeill wrote:

...

On Wed, Jul 14, 2010 at 3:16 PM, Jeremiah Willcock 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::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 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::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::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’ 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::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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users