How do I use an explicit weight map? I thought specializing property_map<> would be the preferred way to add edge weights to a graph that doesn't already contain them. BTW, here is the entire spew up to the first error message: g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>

, Iterator = boost::counting_iterator<size_t, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’: /opt/local/include/boost/graph/astar_search.hpp:285: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor, PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap, CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, AStarVisitor = boost::astar_goal_visitor, PredecessorMap = boost::dummy_property_map, CostMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::edge_weight_map, VertexIndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, CompareFunction = std::less<float>, CombineFunction = boost::closed_plus<float>, CostInf = float, CostZero = float]’ /opt/local/include/boost/graph/astar_search.hpp:318: instantiated from ‘void boost::detail::astar_dispatch2(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::edge_weight_map, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ /opt/local/include/boost/graph/astar_search.hpp:350: instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = boost::detail::error_property_not_found, WeightMap = boost::edge_weight_map, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ /opt/local/include/boost/graph/astar_search.hpp:372: instantiated from ‘void

On Wed, Jun 30, 2010 at 4:09 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Wed, 30 Jun 2010, W.P. McNeill wrote:

I am trying to write a simple example of an a-star search over a

...

2-dimensional grid using the Boost Graph Library. The source is hosted here: http://github.com/wpm/Boost-Searchable-Grid-Example. My intent is for this to be a resource for other people writing a-star searches. I am seeing an error about a missing weight map when I try to compile the call to astar_search(). As far as I can tell, everything is in order. I hoping someone has insight into what I'm missing.

My graph class is a rank-2 grid graph called weighted_grid defined like so:

typedef grid_graph<2> weighted_grid;

I have a simple map that returns a weight of zero for every edge.

struct edge_weight_map { typedef float value_type; typedef float reference; typedef edge_descriptor key_type; typedef readable_property_map_tag category;

reference operator[](key_type e) const { // All edges have a weight of zero. return 0; } };

I associate this map with the weighted_grid class by specializing property_map.

template<> struct property_map<weighted_grid, edge_weight_t> { typedef edge_weight_map type; typedef edge_weight_map const_type; };

Since you didn't write the grid_graph class, this is not the correct way to add property maps. You will need to use an external property map (such as iterator_property_map) as your weight map, and then pass it in explicitly to the astar_search() function.

I've defined valid expression functions for this property map along with a

...

Euclidean distance heuristic and a visitor that throws an exception when a goal vertex is reached. The complete source is viewable at the URL given above.

With these definitions I can do concept checks on the ReadablePropertyMap, ReadablePropertyGraph, VertexListGraph, and AStarHeuristic concepts. I can instantiate a weighted_grid. I can get the edge weight map using get(edge_weight, g) and the vertex index map using get(vertex_index, g). I think I have written everything I need to do a-star search.

However, the following call does not build:

vertex_descriptor source = vertex(0, g), goal = vertex(3, g); astar_search(g, source, euclidean_heuristic(goal), visitor(astar_goal_visitor(goal)) );

I get a long error spew. The first relevant problem appears to be here:

The error here doesn't have enough of the instantiation stack to be useful. Just use an explicit weight map, though, and that is more likely to work.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

, Iterator = boost::counting_iterator<size_t, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’:

Digging through the error stack it looked like the problem may have been with a vertex_iterator declaration at the top of astar_search() function (astar_search.hpp line 285), so I tried to compile the following trivial program with grid_graph: #include <boost/graph/grid_graph.hpp> int main(int argc, char* argv[]) { using namespace boost; graph_traits< grid_graph<2> >::vertex_iterator vi; return 0; } Note that it is just vanilla grid_graph, with no edge weights or other code defined by me. I get the following compilation error: g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> main.cpp:7: instantiated from here /opt/local/include/boost/iterator/transform_iterator.hpp:100: error: no matching function for call to ‘boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>

::grid_graph_vertex_at()’ /opt/local/include/boost/graph/grid_graph.hpp:104: note: candidates are: boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const Graph*) [with Graph = boost::grid_graph<2ul, size_t, size_t>] /opt/local/include/boost/graph/grid_graph.hpp:100: note: boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> ::grid_graph_vertex_at(const boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> &) make: *** [main.o] Error 1

This looks wrong to me. I thought the fact that grid_graph models the VertexList concept would ensure that I could declare a default vertex_iterator. On Wed, Jun 30, 2010 at 4:50 PM, W.P. McNeill <billmcn@gmail.com> wrote:

I also tried passing an edge_weight_map structure as a named parameter to astar_search.

vertex_descriptor source = vertex(0, g), goal = vertex(3, g); edge_weight_map mymap = edge_weight_map(); astar_search(g, source, euclidean_heuristic(goal), weight_map(mymap). visitor(astar_goal_visitor(goal)) );

I get the same compilation error.

On Wed, Jun 30, 2010 at 4:25 PM, W.P. McNeill <billmcn@gmail.com> wrote:

...

How do I use an explicit weight map? I thought specializing property_map<> would be the preferred way to add edge weights to a graph that doesn't already contain them.

BTW, here is the entire spew up to the first error message:

g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>

...

, Iterator = boost::counting_iterator<size_t, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’: /opt/local/include/boost/graph/astar_search.hpp:285: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor, PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap, CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, AStarVisitor = boost::astar_goal_visitor, PredecessorMap = boost::dummy_property_map, CostMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::edge_weight_map, VertexIndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, CompareFunction = std::less<float>, CombineFunction = boost::closed_plus<float>, CostInf = float, CostZero = float]’ /opt/local/include/boost/graph/astar_search.hpp:318: instantiated from ‘void boost::detail::astar_dispatch2(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<float, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::edge_weight_map, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ /opt/local/include/boost/graph/astar_search.hpp:350: instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = boost::detail::error_property_not_found, WeightMap = boost::edge_weight_map, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ /opt/local/include/boost/graph/astar_search.hpp:372: instantiated from ‘void

On Wed, Jun 30, 2010 at 4:09 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

...

On Wed, 30 Jun 2010, W.P. McNeill wrote:

I am trying to write a simple example of an a-star search over a

...

2-dimensional grid using the Boost Graph Library. The source is hosted here: http://github.com/wpm/Boost-Searchable-Grid-Example. My intent is for this to be a resource for other people writing a-star searches. I am seeing an error about a missing weight map when I try to compile the call to astar_search(). As far as I can tell, everything is in order. I hoping someone has insight into what I'm missing.

My graph class is a rank-2 grid graph called weighted_grid defined like so:

typedef grid_graph<2> weighted_grid;

I have a simple map that returns a weight of zero for every edge.

struct edge_weight_map { typedef float value_type; typedef float reference; typedef edge_descriptor key_type; typedef readable_property_map_tag category;

reference operator[](key_type e) const { // All edges have a weight of zero. return 0; } };

I associate this map with the weighted_grid class by specializing property_map.

template<> struct property_map<weighted_grid, edge_weight_t> { typedef edge_weight_map type; typedef edge_weight_map const_type; };

Since you didn't write the grid_graph class, this is not the correct way to add property maps. You will need to use an external property map (such as iterator_property_map) as your weight map, and then pass it in explicitly to the astar_search() function.

I've defined valid expression functions for this property map along with

...

a Euclidean distance heuristic and a visitor that throws an exception when a goal vertex is reached. The complete source is viewable at the URL given above.

With these definitions I can do concept checks on the ReadablePropertyMap, ReadablePropertyGraph, VertexListGraph, and AStarHeuristic concepts. I can instantiate a weighted_grid. I can get the edge weight map using get(edge_weight, g) and the vertex index map using get(vertex_index, g). I think I have written everything I need to do a-star search.

However, the following call does not build:

vertex_descriptor source = vertex(0, g), goal = vertex(3, g); astar_search(g, source, euclidean_heuristic(goal), visitor(astar_goal_visitor(goal)) );

I get a long error spew. The first relevant problem appears to be here:

The error here doesn't have enough of the instantiation stack to be useful. Just use an explicit weight map, though, and that is more likely to work.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

The new grid_graph.hpp header gets me a little farther. The trivial program complies when I use the grid_graph.hpp (r63333) version you pointed me too. I still can't compile my weighted_grid graph program with the new grid_graph header, but I do think I'm getting further along. After making various minor changes (documented on github), I am trying to compile dimension_array dimensions = { {3, 4} }; weighted_grid g(dimensions); vertex_descriptor source = vertex(0, g), goal = vertex(3, g); astar_search(g, source, euclidean_heuristic(goal), visitor(astar_goal_visitor(goal)) ); The top of the error spew looks like this g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/graph/named_function_params.hpp: In static member function ‘static typename boost::detail::choose_default_param::bind_<P, Graph, Tag>::const_result_type boost::detail::choose_default_param::const_apply(const P&, const Graph&, Tag) [with P = boost::detail::error_property_not_found, Graph = boost::weighted_grid, Tag = boost::vertex_index_t]’: /opt/local/include/boost/graph/named_function_params.hpp:304: instantiated from ‘typename boost::detail::choose_pmap_helper<Param, Graph, Tag>::const_result_type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag) [with Param = boost::detail::error_property_not_found, Graph = boost::weighted_grid, PropertyTag = boost::vertex_index_t]’ /opt/local/include/boost/graph/astar_search.hpp:372: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’ main.cpp:23: instantiated from here */opt/local/include/boost/graph/named_function_params.hpp:253: error: conversion from ‘boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested* The named_function_params.hpp is calling get(), I think to acquire a vertex_index_map. The default vertex_index_map is being created incorrectly, but I can't figure out how. Note that I can acquire and use the vertex index. For example, the following call in main() function get(vertex_index, g)[source] returns (size_t) 0 as it should. I'm stuck again, though I am getting better at reading the big template compiler error spew. On Wed, Jun 30, 2010 at 9:59 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Wed, 30 Jun 2010, W.P. McNeill wrote:

Digging through the error stack it looked like the problem may have been

...

with a vertex_iterator declaration at the top of astar_search() function (astar_search.hpp line 285), so I tried to compile the following trivial program with grid_graph: #include <boost/graph/grid_graph.hpp>

int main(int argc, char* argv[]) { using namespace boost; graph_traits< grid_graph<2> >::vertex_iterator vi; return 0; }

Note that it is just vanilla grid_graph, with no edge weights or other code defined by me.

I get the following compilation error:

...

, Iterator = boost::counting_iterator<size_t, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’:

g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> main.cpp:7: instantiated from here /opt/local/include/boost/iterator/transform_iterator.hpp:100: error: no matching function for call to ‘boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> >::grid_graph_vertex_at()’ /opt/local/include/boost/graph/grid_graph.hpp:104: note: candidates are: boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const Graph*) [with Graph = boost::grid_graph<2ul, size_t, size_t>] /opt/local/include/boost/graph/grid_graph.hpp:100: note: boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> >::grid_graph_vertex_at(const boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t>

...

&) make: *** [main.o] Error 1

This looks wrong to me. I thought the fact that grid_graph models the VertexList concept would ensure that I could declare a default vertex_iterator.

This is a bug; it's been fixed in the trunk for a few days. Could you please see if that version ( https://svn.boost.org/svn/boost/trunk/boost/graph/grid_graph.hpp) works?

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

, WeightMap = boost::edge_weight_map, VertexIndexMap = boost::typed_identity_property_map<size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::typed_identity_property_map<size_t> >, CompareFunction = std::less<float>, CombineFunction = boost::closed_plus<float>, CostInf = float, CostZero = float]’ astar_search.hpp:319: instantiated from ‘void boost::detail::astar_dispatch2(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::vector_property_map<float, boost::typed_identity_property_map<size_t> >, DistanceMap = boost::vector_property_map<float, boost::typed_identity_property_map<size_t> , WeightMap = boost::edge_weight_map, IndexMap = boost::typed_identity_property_map<size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::typed_identity_property_map<size_t> >, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ astar_search.hpp:348: instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = boost::detail::error_property_not_found, WeightMap = boost::edge_weight_map, IndexMap = boost::typed_identity_property_map<size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<boost::astar_goal_visitor, boost::graph_visitor_t, boost::no_property>]’ astar_search.hpp:370: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’

Compiling with https://svn.boost.org/svn/boost/trunk/boost/graph/astar_search.hpp (r63472). Looks like the same error. I included a little more of the error spew in case it helps. One thing I'm confused about: what should weighted_grid::vertex_property_type be? I didn't see anything in the a-star documentation about this type, but I had to add it in order to get things to compile this far. Right now I've got it set to vertex_descriptor, though I get the same error if it's vertices_size_type. g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/graph/named_function_params.hpp: In static member function ‘static typename boost::detail::choose_default_param::bind_<P, Graph, Tag>::const_result_type boost::detail::choose_default_param::const_apply(const P&, const Graph&, Tag) [with P = boost::detail::error_property_not_found, Graph = boost::weighted_grid, Tag = boost::vertex_index_t]’: /opt/local/include/boost/graph/named_function_params.hpp:304: instantiated from ‘typename boost::detail::choose_pmap_helper<Param, Graph, Tag>::const_result_type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag) [with Param = boost::detail::error_property_not_found, Graph = boost::weighted_grid, PropertyTag = boost::vertex_index_t]’ astar_search.hpp:370: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’ main.cpp:23: instantiated from here /opt/local/include/boost/graph/named_function_params.hpp:253: error: conversion from ‘boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested /opt/local/include/boost/property_map/property_map.hpp: In function ‘void boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&) [with PropertyMap = boost::vector_property_map<boost::default_color_type, boost::typed_identity_property_map<size_t> >, Reference = boost::default_color_type&, K = boost::array<size_t, 2ul>, V = boost::default_color_type]’: astar_search.hpp:288: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor, PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap, CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, AStarVisitor = boost::astar_goal_visitor, PredecessorMap = boost::dummy_property_map, CostMap = boost::vector_property_map<float, boost::typed_identity_property_map<size_t> >, DistanceMap = boost::vector_property_map<float, boost::typed_identity_property_map<size_t> main.cpp:23: instantiated from here /opt/local/include/boost/property_map/property_map.hpp:325: error: no match for ‘operator[]’ in ‘(const boost::vector_property_map<boost::default_color_type, boost::typed_identity_property_map<size_t> >&)((const boost::vector_property_map<boost::default_color_type, boost::typed_identity_property_map<size_t> >*)(& pa))[k]’ On Thu, Jul 1, 2010 at 7:04 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 1 Jul 2010, W.P. McNeill wrote:

The new grid_graph.hpp header gets me a little farther.

...

The trivial program complies when I use the grid_graph.hpp (r63333) version you pointed me too. I still can't compile my weighted_grid graph program with the new grid_graph header, but I do think I'm getting further along. After making various minor changes (documented on github), I am trying to compile

dimension_array dimensions = { {3, 4} }; weighted_grid g(dimensions); vertex_descriptor source = vertex(0, g), goal = vertex(3, g); astar_search(g, source, euclidean_heuristic(goal), visitor(astar_goal_visitor(goal)) );

The top of the error spew looks like this

g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/graph/named_function_params.hpp: In static member function ‘static typename boost::detail::choose_default_param::bind_<P, Graph, Tag>::const_result_type boost::detail::choose_default_param::const_apply(const P&, const Graph&, Tag) [with P = boost::detail::error_property_not_found, Graph = boost::weighted_grid, Tag = boost::vertex_index_t]’: /opt/local/include/boost/graph/named_function_params.hpp:304: instantiated from ‘typename boost::detail::choose_pmap_helper<Param, Graph, Tag>::const_result_type boost::choose_const_pmap(const Param&, const Graph&, PropertyTag) [with Param = boost::detail::error_property_not_found, Graph = boost::weighted_grid, PropertyTag = boost::vertex_index_t]’ /opt/local/include/boost/graph/astar_search.hpp:372: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = boost::weighted_grid, AStarHeuristic = boost::euclidean_heuristic, P = boost::astar_goal_visitor, T = boost::graph_visitor_t, R = boost::no_property]’ main.cpp:23: instantiated from here /opt/local/include/boost/graph/named_function_params.hpp:253: error: conversion from ‘boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>’ to non-scalar type ‘boost::typed_identity_property_map<size_t>’ requested

The named_function_params.hpp is calling get(), I think to acquire a vertex_index_map. The default vertex_index_map is being created incorrectly, but I can't figure out how.

Note that I can acquire and use the vertex index. For example, the following call in main() function

get(vertex_index, g)[source]

returns (size_t) 0 as it should.

Could you please try with the trunk version of astar_search.hpp? That will allow me to line up your line numbers with my copy.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I was trying to avoid inheriting from boost::grid_graph. The only reason I did it here was because astar_search requires its graph to define vertex_property_type and vertex_index, and the only way I could see to do that was with a subclass. I'll look at defining my own graph class that has a boost::grid_graph as a member. I'm still going to have to define vertex_property_type for the class I write though, right? What should it be: vertex_descriptor? On Thu, Jul 1, 2010 at 11:01 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 1 Jul 2010, W.P. McNeill wrote:

Compiling with

...

https://svn.boost.org/svn/boost/trunk/boost/graph/astar_search.hpp(r63472). Looks like the same error. I included a little more of the error spew in case it helps.

One thing I'm confused about: what should weighted_grid::vertex_property_type be? I didn't see anything in the a-star documentation about this type, but I had to add it in order to get things to compile this far. Right now I've got it set to vertex_descriptor, though I get the same error if it's vertices_size_type.

I think that you shouldn't try to inherit from BGL graph types. There are several traits classes that are used to look things up, and those do not respect inheritance (i.e., graph_traits<derived> has no relationship to graph_traits<base>). You should use a separate external property for your weights or define a separate graph type (that may contain a grid_graph, but has its own members/specializations for all of the traits).

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I'm not sure. I know I got a "property missing" compile error and got around it by defining vertex_property_type in the class. On Thu, Jul 1, 2010 at 11:35 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 1 Jul 2010, W.P. McNeill wrote:

I was trying to avoid inheriting from boost::grid_graph. The only reason

...

I did it here was because astar_search requires its graph to define vertex_property_type and vertex_index, and the only way I could see to do that was with a subclass. I'll look at defining my own graph class that has a boost::grid_graph as a member.

I'm still going to have to define vertex_property_type for the class I write though, right? What should it be: vertex_descriptor?

Does astar_search use vertex_property_type, or does it just use the property_map<> traits class? If the latter, just specialize that for your graph type.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Sun, 4 Jul 2010, W.P. McNeill wrote:

The property type problem was because I didn't have property_traits<> correctly defined. I rewrote this from scratch and defined my own grid object instead of using Boost's grid_graph.  Now I can get a-star to run, but only if I use the latest version of astar_search.hpp.  If I use the Boost 1.42 version installed on my machine by Macports, it fails to compile because of bug 3917.

Is 3917 fixed in version 1.43?  (I'm guessing that's what the struckthrough "Boost 1.43.0" in the Milestone field of the bug report means.)

I'm pretty sure the fix made it into 1.43. The milestone fields are not really up to date, though. Are you now using your own graph class just in order to add an internal property map? -- Jeremiah Willcock

On Mon, 5 Jul 2010, W.P. McNeill wrote:

I'm using my own graph class because I need an implicit graph for the task I'm trying to do.

Here's the full background: I'm writing a program that solves a maze using a-star search.  (It's on github as Searchable Graph Example.)  The maze is a grid of cells in which you can move up, down, right and left.  Cells are either empty or blocked.  The cost of entering an empty cell is 1, and the cost of entering a blocked cell is infinity. (This is actually a warm-up for a more sophisticated graph search program, but that one also operates on a grid, so a lot of this code will be reusable.  Plus, I think an a-star maze search example would be useful for others to see.)

Because the graph topology is a grid, it seemed like the best way to implement this is with an implicit graph.  I first tried adding edge and vertex properties to Boost's grid_graph class, but I ran into compile errors, some of which are documented earlier in this thread.  Even after I worked around those errors I hit others, and it seemed like I was writing an awful lot of boilerplate code to use grid_graph, so it would be easier to implement my own grid.

Now I'm writing my own grid class (called maze_search::maze in the code on github).  It will have an out edge iterator that determines the the grid structure, a read/write boolean vertex property for whether or not a cell is blocked, and a read-only edge weight property that returns the cost of entering a cell.  I've finished the iterator and the edge weight property, and am starting to look at the vertex property.

Why not just have a class that contains a grid_graph and property maps for the vertices and edges? You can use grid_graph's vertex_index and edge_index maps to provide indices for iterator_property_maps for those properties. You can also use external properties that you keep as separate data structures and pass into algorithms explicitly; that I think would be much easier than what you're doing. The Knight's Tour example uses something similar, but its property map implementation is custom and overcomplicated because the graph there doesn't have vertex_index and edge_index properties. If you look in libs/graph/test/random_spanning_tree_test.cpp (in the trunk and 1.44), there is an example of using external properties with a grid_graph. It just seems to me that what you're doing should not require a new graph type and should actually be fairly simple, even if it doesn't seem that way from the documentation. -- Jeremiah Willcock

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. On Mon, Jul 5, 2010 at 9:50 PM, W.P. McNeill <billmcn@gmail.com> wrote:

Let me start over with code based on random_spanning_tree_test.cpp. Ultimately I'm going to want my edge weights to be calculated on the fly instead of read from a pre-populated array, but getting this to work would be a good starting point.

I've defined a trivial astar search over a grid_graph with weights stored in a shared_array_property_map. The program looks like this:

#include <boost/graph/astar_search.hpp> #include <boost/graph/grid_graph.hpp> #include <iostream>

using namespace boost;

typedef grid_graph<2> grid; typedef graph_traits<grid> traits; typedef traits::vertex_descriptor vertex_descriptor; typedef traits::edge_descriptor edge_descriptor;

typedef double edge_weight_type;

struct zero_heuristic:public boost::astar_heuristic<grid, edge_weight_type> {

edge_weight_type operator()(vertex_descriptor v) { return 0; } };

int main (int argc, char const *argv[]) { array<size_t, 2> sizes = {{ 3, 2 }}; grid g(sizes); shared_array_property_map<edge_weight_type, property_map<grid, edge_index_t>::const_type> weight(num_edges(g), get(edge_index, g));

vertex_descriptor start = vertex(0, g);

astar_search(g, start, zero_heuristic(), weight_map(weight) );

return 0; }

It fails to compile with an error about missing a function for boost::detail::grid_graph_vertex_at():

...

, Iterator = boost::counting_iterator<size_t, boost::use_default, boost::use_default>, Reference = boost::use_default, Value = boost::use_default]’: astar_search.hpp:286: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor, PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap, CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, AStarVisitor = boost::astar_visitor<boost::null_visitor>, PredecessorMap = boost::dummy_property_map, CostMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, VertexIndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, CompareFunction = std::less<edge_weight_type>, CombineFunction = boost::closed_plus<edge_weight_type>, CostInf = double, CostZero = double]’ astar_search.hpp:319: instantiated from ‘void boost::detail::astar_dispatch2(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, CostMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, Params = boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, boost::edge_weight_t, boost::no_property>]’ astar_search.hpp:348: instantiated from ‘void boost::detail::astar_dispatch1(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = boost::detail::error_property_not_found, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, boost::edge_weight_t, boost::no_property>]’ astar_search.hpp:370: instantiated from ‘void boost::astar_search(VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = grid, AStarHeuristic = zero_heuristic, P = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, T = boost::edge_weight_t, R = boost::no_property]’

g++ -g -I/opt/local/include -c -o main.o main.cpp /opt/local/include/boost/iterator/transform_iterator.hpp: In constructor ‘boost::transform_iterator<UnaryFunction, Iterator, Reference, Value>::transform_iterator() [with UnaryFunc = boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> 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_vertex_at<boost::grid_graph<2ul, size_t, size_t>

...

::grid_graph_vertex_at()’ /opt/local/include/boost/graph/grid_graph.hpp:104: note: candidates are: boost::detail::grid_graph_vertex_at<Graph>::grid_graph_vertex_at(const Graph*) [with Graph = boost::grid_graph<2ul, size_t, size_t>] /opt/local/include/boost/graph/grid_graph.hpp:100: note: boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> ::grid_graph_vertex_at(const boost::detail::grid_graph_vertex_at<boost::grid_graph<2ul, size_t, size_t> &)

This happens both with version 1.42 of astar_search.hpp and with the version I pulled from the SVN tree that has the fix for bug 3917.

On Mon, Jul 5, 2010 at 2:06 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

...

On Mon, 5 Jul 2010, W.P. McNeill wrote:

I'm using my own graph class because I need an implicit graph for the

...

task I'm trying to do.

Here's the full background: I'm writing a program that solves a maze using a-star search. (It's on github as Searchable Graph Example.) The maze is a grid of cells in which you can move up, down, right and left. Cells are either empty or blocked. The cost of entering an empty cell is 1, and the cost of entering a blocked cell is infinity. (This is actually a warm-up for a more sophisticated graph search program, but that one also operates on a grid, so a lot of this code will be reusable. Plus, I think an a-star maze search example would be useful for others to see.)

Because the graph topology is a grid, it seemed like the best way to implement this is with an implicit graph. I first tried adding edge and vertex properties to Boost's grid_graph class, but I ran into compile errors, some of which are documented earlier in this thread. Even after I worked around those errors I hit others, and it seemed like I was writing an awful lot of boilerplate code to use grid_graph, so it would be easier to implement my own grid.

Now I'm writing my own grid class (called maze_search::maze in the code on github). It will have an out edge iterator that determines the the grid structure, a read/write boolean vertex property for whether or not a cell is blocked, and a read-only edge weight property that returns the cost of entering a cell. I've finished the iterator and the edge weight property, and am starting to look at the vertex property.

Why not just have a class that contains a grid_graph and property maps for the vertices and edges? You can use grid_graph's vertex_index and edge_index maps to provide indices for iterator_property_maps for those properties. You can also use external properties that you keep as separate data structures and pass into algorithms explicitly; that I think would be much easier than what you're doing. The Knight's Tour example uses something similar, but its property map implementation is custom and overcomplicated because the graph there doesn't have vertex_index and edge_index properties. If you look in libs/graph/test/random_spanning_tree_test.cpp (in the trunk and 1.44), there is an example of using external properties with a grid_graph. It just seems to me that what you're doing should not require a new graph type and should actually be fairly simple, even if it doesn't seem that way from the documentation.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I checked out the Boost trunk from http://svn.boost.org/svn/boost/trunk and rebuilt the program below using those headers. It builds and runs. From now on unless I say otherwise, everything I do uses this version of Boost. Next I tried to add distance and predecessor maps for the output. Following the astar-cities.cpp example, I implemented these as vectors. The program now looks like this: #include <boost/graph/astar_search.hpp> #include <boost/graph/grid_graph.hpp> #include <iostream> #include <vector> using namespace boost; typedef grid_graph<2> grid; typedef graph_traits<grid> traits; typedef traits::vertex_descriptor vertex_descriptor; typedef traits::edge_descriptor edge_descriptor; typedef double edge_weight_type; struct zero_heuristic:public boost::astar_heuristic<grid, edge_weight_type> { edge_weight_type operator()(vertex_descriptor v) { return 0; } }; int main (int argc, char const *argv[]) { array<size_t, 2> sizes = {{ 3, 2 }}; grid g(sizes); shared_array_property_map<edge_weight_type, property_map<grid, edge_index_t>::const_type> weight(num_edges(g), get(edge_index, g)); std::vector<vertex_descriptor> p(num_vertices(g)); std::vector<edge_weight_type> d(num_vertices(g)); vertex_descriptor start = vertex(0, g); astar_search(g, start, zero_heuristic(), weight_map(weight). predecessor_map(&p[0]).distance_map(&d[0]) ); return 0; } It now fails to compile because of what looks like a missing put() functions for the distance and predecessor maps. The top of the error spew looks contains a distance map error that looks like this: g++ -g -I/src/boost-trunk -c -o main.o main.cpp /src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, AStarVisitor, PredecessorMap, CostMap, DistanceMap, WeightMap, VertexIndexMap, ColorMap, CompareFunction, CombineFunction, CostInf, CostZero) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, AStarVisitor = boost::astar_visitor<boost::null_visitor>, PredecessorMap = vertex_descriptor*, CostMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = edge_weight_type*, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, VertexIndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, CompareFunction = std::less<edge_weight_type>, CombineFunction = boost::closed_plus<edge_weight_type>, CostInf = double, CostZero = double]’: /src/boost-trunk/boost/graph/astar_search.hpp:319: instantiated from ‘void boost::detail::astar_dispatch2(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, CostMap = boost::vector_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, DistanceMap = edge_weight_type*, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::vector_property_map<boost::default_color_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t> >, Params = boost::bgl_named_params<edge_weight_type*, boost::vertex_distance_t, boost::bgl_named_params<vertex_descriptor*, boost::vertex_predecessor_t, boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, boost::edge_weight_t, boost::no_property> > >]’ /src/boost-trunk/boost/graph/astar_search.hpp:348: instantiated from ‘void boost::detail::astar_dispatch1(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, CostMap, DistanceMap, WeightMap, IndexMap, ColorMap, const Params&) [with VertexListGraph = boost::grid_graph<2ul, size_t, size_t>, AStarHeuristic = zero_heuristic, CostMap = boost::detail::error_property_not_found, DistanceMap = edge_weight_type*, WeightMap = boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, IndexMap = boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, boost::array<size_t, 2ul>, size_t>, ColorMap = boost::detail::error_property_not_found, Params = boost::bgl_named_params<edge_weight_type*, boost::vertex_distance_t, boost::bgl_named_params<vertex_descriptor*, boost::vertex_predecessor_t, boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, boost::edge_weight_t, boost::no_property> > >]’ /src/boost-trunk/boost/graph/astar_search.hpp:370: instantiated from ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = grid, AStarHeuristic = zero_heuristic, P = edge_weight_type*, T = boost::vertex_distance_t, R = boost::bgl_named_params<vertex_descriptor*, boost::vertex_predecessor_t, boost::bgl_named_params<boost::shared_array_property_map<edge_weight_type, boost::grid_graph_index_map<boost::grid_graph<2ul, size_t, size_t>, std::pair<boost::array<size_t, 2ul>, boost::array<size_t, 2ul> >, size_t> >, boost::edge_weight_t, boost::no_property> >]’ main.cpp:41: instantiated from here /src/boost-trunk/boost/graph/astar_search.hpp:289: error: no matching function for call to ‘put(edge_weight_type*&, boost::array<size_t, 2ul>, double&)’ ... Further down there's another missing put function for the predecessor map. ... /src/boost-trunk/boost/graph/astar_search.hpp:291: error: no matching function for call to ‘put(vertex_descriptor*&, boost::array<size_t, 2ul>, boost::array<size_t, 2ul>)’ /src/boost-trunk/boost/graph/astar_search.hpp:319: instantiated from ‘void ... I thought I didn't have to write my own put() functions if I was passing in distance and predecessor map objects external to the graph. Plus, if I did try to write my own put functions, they'd have to be able to look up vertex indexes from vertex descriptors, which means they need access to the graph object in order to call vertex(...), which means I can't use a simple vector. On Tue, Jul 6, 2010 at 10:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu>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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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. On Tue, Jul 6, 2010 at 10:41 AM, Jeremiah Willcock <jewillco@osl.iu.edu>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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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@osl.iu.edu>

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@osl.iu.edu> 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I would put a warning about not subclassing BGL components on the Boost Graph Concepts page<http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html> since this is a point in the documentation that gives an overview of the way all the graph concepts are implemented. It is also a page that I personally kept referring back to. I guess the warning should mention that this prohibition is an STL thing, and not specific to BGL. I'll take a look at Boost.Program_options, Boost.Lexical_cast, and Boost.Random. Putting filtered_graph over a grid_graph does seem like the right way to go. However, I'm having problems doing this. I can create a filtered version of a grid graph, however I get build errors when I try to call graph concept functions on it. Here's a simple example: #include <iostream> #include <boost/graph/grid_graph.hpp> #include <boost/graph/filtered_graph.hpp> #include <set> using namespace boost; #define RANK 2 typedef grid_graph<RANK> Graph; typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef graph_traits<Graph>::edge_descriptor edge_descriptor; typedef graph_traits<Graph>::out_edge_iterator out_edge_iterator; // Print vertices as (x, y). std::ostream& operator<<(std::ostream& output, const vertex_descriptor& u) { return output << "(" << u[0] << ", " << u[1] << ")"; } // Print edges as (x1, y1) -> (x2, y2). std::ostream& operator<<(std::ostream& output, const edge_descriptor& e) { return output << e.first << "->" << e.second; } typedef std::set<vertex_descriptor> VertexSet; typedef vertex_subset_compliment_filter<Graph, VertexSet>::type VertexFilteredGraph; int main(int argc, char* argv[]) { array<std::size_t, RANK> lengths = { {3, 3} }; Graph g(lengths); VertexSet omit; omit.insert(vertex(1, g)); // Filter vertex (1, 0) out of the graph. VertexFilteredGraph fg = make_vertex_subset_compliment_filter(g, omit); // Print the out edges coming from (0, 0) in the unfiltered and filtered // graphs. vertex_descriptor u = vertex(0, g); std::cout << "Unfiltered out edges from " << u << std::endl; out_edge_iterator oi, oi_end; for (tie(oi, oi_end) = out_edges(u, g); oi != oi_end; oi++) std::cout << *oi << std::endl; std::cout << "Filtered out edges from " << u << std::endl; for (tie(oi, oi_end) = out_edges(u, fg); oi != oi_end; oi++) std::cout << *oi << std::endl; return 0; } When I try to build this I get the following error, which is triggered by the call to out_edges(u, fg): g++ -g -O3 -Wall -I/src/boost-trunk -c -o filter.o filter.cpp /src/boost-trunk/boost/tuple/detail/tuple_basic.hpp: In member function ‘boost::tuples::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>& boost::tuples::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>::operator=(const std::pair<_U1, _U2>&) [with U1 = boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> >, U2 = boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> >, T0 = out_edge_iterator&, T1 = out_edge_iterator&, T2 = boost::tuples::null_type, T3 = boost::tuples::null_type, T4 = boost::tuples::null_type, T5 = boost::tuples::null_type, T6 = boost::tuples::null_type, T7 = boost::tuples::null_type, T8 = boost::tuples::null_type, T9 = boost::tuples::null_type]’: filter.cpp:47: instantiated from here /src/boost-trunk/boost/tuple/detail/tuple_basic.hpp:583: error: no match for ‘operator=’ in ‘((boost::tuples::tuple<out_edge_iterator&, out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>*)this)->boost::tuples::tuple<out_edge_iterator&, out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>::<anonymous>.boost::tuples::cons<out_edge_iterator&, boost::tuples::cons<out_edge_iterator&, boost::tuples::null_type> >::head = k->std::pair<boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> >, boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> > >::first’ /src/boost-trunk/boost/iterator/transform_iterator.hpp:78: note: candidates are: boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>& boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>::operator=(const boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>&) /src/boost-trunk/boost/tuple/detail/tuple_basic.hpp:584: error: no match for ‘operator=’ in ‘((boost::tuples::tuple<out_edge_iterator&, out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>*)this)->boost::tuples::tuple<out_edge_iterator&, out_edge_iterator&, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>::<anonymous>.boost::tuples::cons<out_edge_iterator&, boost::tuples::cons<out_edge_iterator&, boost::tuples::null_type>

::tail.boost::tuples::cons<out_edge_iterator&, boost::tuples::null_type>::head = k->std::pair<boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> >, boost::filter_iterator<boost::detail::out_edge_predicate<boost::keep_all, boost::is_not_in_subset<VertexSet>, boost::filtered_graph<Graph, boost::keep_all, boost::is_not_in_subset<VertexSet> > >, boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default> > >::second’ /src/boost-trunk/boost/iterator/transform_iterator.hpp:78: note: candidates are: boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>& boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>::operator=(const boost::transform_iterator<boost::detail::grid_graph_out_edge_at<boost::grid_graph<2ul, size_t, size_t> >, boost::counting_iterator<size_t, boost::use_default, boost::use_default>, boost::use_default, boost::use_default>&) make: *** [filter.o] Error 1

It looks like missing assignment operators for some tuple structure, but offhand I'm not sure what. On Mon, Jul 12, 2010 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Mon, 12 Jul 2010, W.P. McNeill wrote:

I've got a working A-star maze solver. The code is checked into the

...

github Astar-Maze-Solver project. 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.

One more that has hit other people is named parameters (especially the thing about using "." between arguments rather than ",").

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

...

Yes, and thank you for doing the example.

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

OK. I don't think anyone had tried astar_search with an implicit graph before the earliest bug report on the issue (the first one, though, was about implicit graphs that don't have num_vertices() and astar_search's failure on those).

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

The subclassing thing is based on STL; you are not supposed to subclass STL containers either. If you want to selectively remove edges, look at boost::graph::filtered_graph ( http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/filtered_graph.html). You should be able to wrap that on top of the existing grid_graph.

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.

Where do you think that should go?

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.

One minor thing: maze_traversal_catetory should be maze_traversal_category. I think using filtered_graph might replace all of that code, however. You might also want to use iterator_property_map or shared_array_property_map instead of associative_property_map for performance. If you want to really make the code Boost-like (and I'm not suggesting or requiring that you do this), you can also use Boost.Program_options, Boost.Lexical_cast and Boost.Random to replace the corresponding C functions that you are using now. You are also free to use "using namespace std;" and/or "using namespace boost;" in examples; you can put those in if you think it will make the code more readable.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Different out edge iterators was the problem for my filtered graph example. It's spelled "compliment" in filtered_graph.hpp lines 507-516. I guess that's a bug. Here's a working subset_compliment_filter example. I did my own graph printing rather than using print_graph(...) in graph_utility.hpp because it seemed easier than defining an vertex property for an implicit graph. // Copyright W.P. McNeill 2010. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #include <iostream> #include <boost/graph/grid_graph.hpp> #include <boost/graph/filtered_graph.hpp> #include <set> using namespace boost; #define RANK 2 typedef grid_graph<RANK> Grid; typedef graph_traits<Grid>::vertices_size_type vertices_size_type; typedef graph_traits<Grid>::vertex_descriptor vertex_descriptor; typedef graph_traits<Grid>::edge_descriptor edge_descriptor; typedef std::set<vertex_descriptor> VertexSet; typedef vertex_subset_compliment_filter<Grid, VertexSet>::type VertexFilteredGrid; // Print vertices as (x, y). std::ostream& operator<<(std::ostream& output, const vertex_descriptor& u) { return output << "(" << u[0] << ", " << u[1] << ")"; } // Print edges as (x1, y1) -> (x2, y2). std::ostream& operator<<(std::ostream& output, const edge_descriptor& e) { return output << e.first << "->" << e.second; } // Print all the graph vertices along with their out edges. template<typename Graph, typename VertexIter, typename EdgeIter> void print_graph(const Graph &g) { VertexIter vi, vi_end; for (tie(vi, vi_end) = vertices(g); vi != vi_end; vi++) { vertex_descriptor u = *vi; std::cout << u << std::endl; EdgeIter ei, ei_end; for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++) std::cout << "\t" << *ei << std::endl; } } int main(int argc, char* argv[]) { array<std::size_t, RANK> lengths = { {2, 2} }; Grid g(lengths); std::cout << "Original:" << std::endl; print_graph<Grid, graph_traits<Grid>::vertex_iterator, graph_traits<Grid>::out_edge_iterator>(g); // Filter the lower right-hand vertex out of the graph. vertex_descriptor u = vertex(num_vertices(g)-1, g); VertexSet omit; omit.insert(u); VertexFilteredGrid fg = make_vertex_subset_compliment_filter(g, omit); std::cout << std::endl << "With vertex " << u << " removed:" << std::endl; print_graph<VertexFilteredGrid, graph_traits<VertexFilteredGrid>::vertex_iterator, graph_traits<VertexFilteredGrid>::out_edge_iterator>(fg); return 0; } On Tue, Jul 13, 2010 at 8:55 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Mon, 12 Jul 2010, W.P. McNeill wrote:

I would put a warning about not subclassing BGL components on the Boost

...

Graph Concepts page since this is a point in the documentation that gives an overview of the way all the graph concepts are implemented. It is also a page that I personally kept referring back to. I guess the warning should mention that this prohibition is an STL thing, and not specific to BGL.

OK.

I'll take a look at Boost.Program_options, Boost.Lexical_cast,

...

and Boost.Random.

That's up to you -- I don't mind if you use the C functions for those things.

Putting filtered_graph over a grid_graph does seem like the right way to

...

go. However, I'm having problems doing this. I can create a filtered version of a grid graph, however I get build errors when I try to call graph concept functions on it. Here's a simple example:

#include <iostream> #include <boost/graph/grid_graph.hpp> #include <boost/graph/filtered_graph.hpp> #include <set>

using namespace boost;

#define RANK 2 typedef grid_graph<RANK> Graph; typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor; typedef graph_traits<Graph>::edge_descriptor edge_descriptor; typedef graph_traits<Graph>::out_edge_iterator out_edge_iterator;

// Print vertices as (x, y). std::ostream& operator<<(std::ostream& output, const vertex_descriptor& u) { return output << "(" << u[0] << ", " << u[1] << ")"; }

// Print edges as (x1, y1) -> (x2, y2). std::ostream& operator<<(std::ostream& output, const edge_descriptor& e) { return output << e.first << "->" << e.second; }

typedef std::set<vertex_descriptor> VertexSet; typedef vertex_subset_compliment_filter<Graph, VertexSet>::type VertexFilteredGraph;

int main(int argc, char* argv[]) { array<std::size_t, RANK> lengths = { {3, 3} }; Graph g(lengths);

VertexSet omit; omit.insert(vertex(1, g)); // Filter vertex (1, 0) out of the graph. VertexFilteredGraph fg = make_vertex_subset_compliment_filter(g, omit);

"complement"?

...

// Print the out edges coming from (0, 0) in the unfiltered and filtered // graphs. vertex_descriptor u = vertex(0, g);

std::cout << "Unfiltered out edges from " << u << std::endl; out_edge_iterator oi, oi_end; for (tie(oi, oi_end) = out_edges(u, g); oi != oi_end; oi++) std::cout << *oi << std::endl;

std::cout << "Filtered out edges from " << u << std::endl; for (tie(oi, oi_end) = out_edges(u, fg); oi != oi_end; oi++) std::cout << *oi << std::endl;

fg will have a different out_edge_iterator type than g does, since fg's iterator will need to do the filtering. I think that is the cause of the errors you are getting.

...

return 0; }

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

A-Star-Maze solver <http://github.com/wpm/Astar-Maze-Solver> is pretty much done. The filtered_graph does make the code a lot simpler. I used lexical_cast and Boost's random number facilities, but decided the Boost command line processing code was overkill for this example. The warnings you added about not subclassing BGL types look good. Two things that look like documentation errors: 1. On the A* search<http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/astar_search.html>page, the examine_vertex prototype for the visitor is listed as vis.examine_vertex(u, g), but you actually need it to be vis.examine_vertex(u, const g) in order for the code the build. (This may be true for the other visitor functions as well.) This tripped me up when I first wrote my visitor class. I'm not sure if you want to specify the constants here, or let them be assumed. 2. The grid graph indexing documentation<http://www.boost.org/doc/libs/1_41_0/libs/graph/doc/grid_graph.html#indexing> incorrectly states that you get a vertex index with get(boost::vertex_index, vertex_descriptor, const Graph&). The order of the last two parameters is switched. The header actually specifies get(boost::vertex_index, const Graph&, vertex_descriptor). This appears to be the case in the documentation for a number of the get(...) functions. On Wed, Jul 14, 2010 at 11:59 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Tue, 13 Jul 2010, W.P. McNeill wrote:

Different out edge iterators was the problem for my filtered graph

...

example. It's spelled "compliment" in filtered_graph.hpp lines 507-516. I guess that's a bug.

I fixed that now in the trunk (r64016); the old version is still around for compatibility reasons. Please use the new name.

Here's a working subset_compliment_filter example. I did my own graph

...

printing rather than using print_graph(...) in graph_utility.hpp because it seemed easier than defining an vertex property for an implicit graph.

You can also use write_graphviz_dp() to do your printing; that will allow you to just fill in a dynamic_properties() object with whatever external property maps you want. There is also a function_property_map that's not in BGL but you can find by searching the Boost mailing lists; you can use that to create your vertex names, or you can just create a shared_array_property_map that you fill in manually with the names.

I also added warnings in graph_concepts.html and graph_traits.html about subclassing BGL graphs. Please see if you like the wording or if you think there are any other places those warnings need to be.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I verified the documentation changes for grid graph indexing calls and A* visitors. Looks good. Now doing edge weights with a static_property_map<>. 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: g++ -g -I/src/boost-trunk -Wall -Werror -O3 -c -o maze.o maze.cpp /src/boost-trunk/boost/graph/graph_traits.hpp: In instantiation of ‘boost::vertex_property_type<grid>’: /src/boost-trunk/boost/graph/filtered_graph.hpp:226: instantiated from ‘boost::vertex_property_type<boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> > >’ /src/boost-trunk/boost/graph/properties.hpp:202: instantiated from ‘boost::detail::vertex_property_map<boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/properties.hpp:251: instantiated from ‘boost::property_map<boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/named_function_params.hpp:243: instantiated from ‘boost::detail::choose_default_param::bind_<boost::detail::error_property_not_found, boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/named_function_params.hpp:276: instantiated from ‘boost::detail::choose_pmap_helper<boost::detail::error_property_not_found, boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> >, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/astar_search.hpp:370: instantiated from ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid, AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>, boost::vertex_predecessor_t, boost::bgl_named_params<maze::solve()::edge_weight_pmap, boost::edge_weight_t, boost::no_property> > >]’ maze.cpp:229: instantiated from here /src/boost-trunk/boost/graph/graph_traits.hpp:226: error: no type named ‘vertex_property_type’ in ‘class grid’ /src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid, AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>, boost::vertex_predecessor_t, boost::bgl_named_params<maze::solve()::edge_weight_pmap, boost::edge_weight_t, boost::no_property> > >]’: maze.cpp:229: instantiated from here /src/boost-trunk/boost/graph/astar_search.hpp:370: error: no matching function for call to ‘choose_const_pmap(boost::detail::error_property_not_found, const boost::filtered_graph<grid, boost::keep_all, boost::is_not_in_subset<vertex_set> >&, boost::vertex_index_t)’ make: *** [maze.o] Error 1 I was surprised by this because I expected the filtered graph to inherit the grid graph's vertex index map like you describe. On Wed, Jul 14, 2010 at 1:43 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

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

A-Star-Maze solver is pretty much done. The filtered_graph does make the

...

code a lot simpler. I used lexical_cast and Boost's random number facilities, but decided the Boost command line processing code was overkill for this example. The warnings you added about not subclassing BGL types look good.

OK.

Two things that look like documentation errors:

...

1. On the A* search page, the examine_vertex prototype for the visitor is listed as vis.examine_vertex(u, g), but you actually need it to

be vis.examine_vertex(u, const g) in order for the code the build. (This may be true for the other visitor functions as well.) This tripped me up when I first wrote my visitor class. I'm not sure if you want to specify the constants here, or let them be assumed. 2. The grid graph indexing documentation incorrectly states that you get a vertex index with get(boost::vertex_index, vertex_descriptor, const Graph&).

The order of the last two parameters is switched. The header actually specifies get(boost::vertex_index, const Graph&, vertex_descriptor). This appears to be the case in the documentation for a number of the get(...) functions.

I believe I fixed both of these now. Please check.

BTW, you don't need to create your own weight map if the weights are all the same; just use something like static_property_map<double>(1.) as the weight map. Also, why do you need your own vertex index map? It appears to just forward to the grid graph's version; why not just use that one directly? It appears that filtered_graph forwards property map requests to the underlying graph by default anyway, so you might just be able to remove that argument from your call to astar_search. You also don't need to call num_vertices() on the underlying graph; calling it on the filtered_graph does the same thing. Does your random_int() function re-seed the RNG to get a different answer each time?

I think overall that your code is nearly ready to put in. What did you want me to do with the README.md file? Put that in the documentation somewhere, or is most of the content in there about building it outside Boost (where it will build with the rest of the BGL examples using Boost.Build)?

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Wed, Jul 14, 2010 at 3:16 PM, Jeremiah Willcock <jewillco@osl.iu.edu>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().

Change r64024 looks like it introduced a regression. I now get the following build error in astar-maze that wasn't there before:

g++ -g -I/src/boost-trunk -Wall -Werror -O3 -c -o astar_maze.o astar_maze.cpp /src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid, AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>, boost::vertex_predecessor_t, boost::bgl_named_params<vertex_index_pmap, boost::vertex_index_t, boost::bgl_named_params<maze::solve()::edge_weight_pmap, boost::edge_weight_t, boost::no_property> > > >]’: astar_maze.cpp:242: instantiated from here /src/boost-trunk/boost/graph/astar_search.hpp:329: error: ‘override_const_property’ was not declared in this scope make: *** [astar_maze.o] Error 1 As a wild guess I tried building with detail::override_const_property but got the same error.

I was surprised by this because I expected the filtered graph to inherit

...

the grid graph's vertex index map like you describe.

That is what it should do.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Wed, Jul 14, 2010 at 3:46 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

Change r64024 looks like it introduced a regression. I now get the

...

following build error in astar-maze that wasn't there before:

g++ -g -I/src/boost-trunk -Wall -Werror -O3 -c -o astar_maze.o astar_maze.cpp /src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid, AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T = boost::graph_visitor_t, R = boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>, boost::vertex_distance_t, boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>, boost::vertex_predecessor_t, boost::bgl_named_params<vertex_index_pmap, boost::vertex_index_t, boost::bgl_named_params<maze::solve()::edge_weight_pmap, boost::edge_weight_t, boost::no_property> > > >]’: astar_maze.cpp:242: instantiated from here /src/boost-trunk/boost/graph/astar_search.hpp:329: error: ‘override_const_property’ was not declared in this scope make: *** [astar_maze.o] Error 1

As a wild guess I tried building with detail::override_const_property but got the same error.

That's odd. It is in detail::; r64025 should have the fix for that. Do you at least get a clearer error message with detail:: qualifying the call to override_const_property()?

Version >= 64025 still does not build for me. It appears that you overlooked calls to override_const_property on lines 335 and 336 of astar_search.hpp. If I insert detail:: namespace qualifiers on these two calls, my program builds and runs correctly.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Wed, Jul 14, 2010 at 4:57 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

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

...

On Wed, Jul 14, 2010 at 3:46 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: Change r64024 looks like it introduced a regression. I now get the following build error in astar-maze that wasn't there before:

g++ -g -I/src/boost-trunk -Wall -Werror -O3 -c -o astar_maze.o astar_maze.cpp /src/boost-trunk/boost/graph/astar_search.hpp: In function ‘void boost::astar_search(const VertexListGraph&, typename boost::graph_traits<G>::vertex_descriptor, AStarHeuristic, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = filtered_grid, AStarHeuristic = euclidean_heuristic, P = astar_goal_visitor, T = boost::graph_visitor_t, R =

boost::bgl_named_params<boost::associative_property_map<maze::solve()::dist_map>, boost::vertex_distance_t,

boost::bgl_named_params<boost::associative_property_map<maze::solve()::pred_map>, boost::vertex_predecessor_t, boost::bgl_named_params<vertex_index_pmap, boost::vertex_index_t, boost::bgl_named_params<maze::solve()::edge_weight_pmap, boost::edge_weight_t, boost::no_property> > > >]’: astar_maze.cpp:242: instantiated from here /src/boost-trunk/boost/graph/astar_search.hpp:329: error: ‘override_const_property’ was not declared in this scope make: *** [astar_maze.o] Error 1

As a wild guess I tried building with detail::override_const_property but got the same error.

That's odd. It is in detail::; r64025 should have the fix for that. Do you at least get a clearer error message with detail:: qualifying the call to override_const_property()?

Version >= 64025 still does not build for me. It appears that you overlooked calls to override_const_property on lines 335 and 336 of astar_search.hpp. If I insert detail:: namespace qualifiers on these two calls, my program builds and runs correctly.

Thanks for catching that -- look at r64030 now and see if it's fixed.

I verified that it's fixed in r64030.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

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

On Wed, Jul 14, 2010 at 3:16 PM, Jeremiah Willcock <jewillco@osl.iu.edu> 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

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.

OK -- I was just saying to try that with some object of type "grid", however you can construct one.

#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();

That declares a function, though, not a real graph.

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?

I think so. Does a line like that work with the filtered_graph too? -- Jeremiah Willcock

It doesn't work with a filtered_graph.  Adding the following line:

boost::property_map<filtered_grid, boost::vertex_index_t>::const_type fpm = get(boost::vertex_index, m_barrier_grid);

produces this error:

g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o astar_maze.o astar_maze.cpp /src/boost-trunk/boost/graph/graph_traits.hpp: In instantiation of ‘boost::vertex_property_type<grid>’: /src/boost-trunk/boost/graph/filtered_graph.hpp:226:   instantiated from ‘boost::vertex_property_type<filtered_grid>’ /src/boost-trunk/boost/graph/properties.hpp:202:   instantiated from ‘boost::detail::vertex_property_map<filtered_grid, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/properties.hpp:251:   instantiated from ‘boost::property_map<filtered_grid, boost::vertex_index_t>’ astar_maze.cpp:234:   instantiated from here /src/boost-trunk/boost/graph/graph_traits.hpp:226: error: no type named ‘vertex_property_type’ in ‘class grid’

Which is the same error I was seeing before inside the astar_search call. 

Could you please try this code and the astar_search call with r64035 from the trunk? -- Jeremiah Willcock

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

On Wed, Jul 14, 2010 at 7:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: It doesn't work with a filtered_graph.  Adding the following line:

boost::property_map<filtered_grid, boost::vertex_index_t>::const_type fpm = get(boost::vertex_index, m_barrier_grid);

produces this error:

g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o astar_maze.o astar_maze.cpp /src/boost-trunk/boost/graph/graph_traits.hpp: In instantiation of ‘boost::vertex_property_type<grid>’: /src/boost-trunk/boost/graph/filtered_graph.hpp:226:   instantiated from ‘boost::vertex_property_type<filtered_grid>’ /src/boost-trunk/boost/graph/properties.hpp:202:   instantiated from ‘boost::detail::vertex_property_map<filtered_grid, boost::vertex_index_t>’ /src/boost-trunk/boost/graph/properties.hpp:251:   instantiated from ‘boost::property_map<filtered_grid, boost::vertex_index_t>’ astar_maze.cpp:234:   instantiated from here /src/boost-trunk/boost/graph/graph_traits.hpp:226: error: no type named ‘vertex_property_type’ in ‘class grid’

Which is the same error I was seeing before inside the astar_search call. 

Could you please try this code and the astar_search call with r64035 from the trunk?

That fixed it.  With r64035 I am able to use the filtered grid's default vertex index map to do an A* search.

Do you know which release of Boost 64035 will be in?  I want to make note of this in the README.

Right now, 1.45, but since it's a bug fix I can push it into 1.44 if I have time. -- Jeremiah Willcock

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

On Wed, Jul 14, 2010 at 7:55 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: On Wed, 14 Jul 2010, W.P. McNeill wrote:

On Wed, Jul 14, 2010 at 7:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:            It doesn't work with a filtered_graph.  Adding the following line:

           boost::property_map<filtered_grid, boost::vertex_index_t>::const_type fpm = get(boost::vertex_index, m_barrier_grid);

           produces this error:

           g++ -g -I/src/boost-trunk -Wall -Werror -O3   -c -o astar_maze.o astar_maze.cpp            /src/boost-trunk/boost/graph/graph_traits.hpp: In instantiation of ‘boost::vertex_property_type<grid>’:            /src/boost-trunk/boost/graph/filtered_graph.hpp:226:   instantiated from ‘boost::vertex_property_type<filtered_grid>’            /src/boost-trunk/boost/graph/properties.hpp:202:   instantiated from ‘boost::detail::vertex_property_map<filtered_grid,            boost::vertex_index_t>’            /src/boost-trunk/boost/graph/properties.hpp:251:   instantiated from ‘boost::property_map<filtered_grid, boost::vertex_index_t>’            astar_maze.cpp:234:   instantiated from here            /src/boost-trunk/boost/graph/graph_traits.hpp:226: error: no type named ‘vertex_property_type’ in ‘class grid’

           Which is the same error I was seeing before inside the astar_search call. 

Could you please try this code and the astar_search call with r64035 from the trunk?

That fixed it.  With r64035 I am able to use the filtered grid's default vertex index map to do an A* search.

Do you know which release of Boost 64035 will be in?  I want to make note of this in the README.

Right now, 1.45, but since it's a bug fix I can push it into 1.44 if I have time.

If you do, let me know.  Otherwise I'll just bump the version in the README to 1.45 when I release this sometime next week.  Of course I doubt it'll matter that much, most people looking for example code are probably building against the trunk anyway. 

I think I've merged everything over; please check your example against the current (future 1.44) release branch. Please tell me if it fails, otherwise you can say that your example will work with 1.44. Your example itself won't be merged in until 1.45, though. -- Jeremiah Willcock

I just verified that everything builds and works with version 64058 on http://svn.boost.org/svn/boost/trunk.  Is that the 1.44 branch?

No -- that's the trunk, and some of those changes will not get in until 1.45 (but BGL should be the same). What you need to test against is https://svn.boost.org/svn/boost/branches/release.

I also put my implicit graph example into a single source to make it easier to include in the examples directory.  

Good. I'll check it over again and most likely put it in soon. -- Jeremiah Willcock

On Thu, 15 Jul 2010, W.P. McNeill wrote:

On Thu, Jul 15, 2010 at 5:45 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: I just verified that everything builds and works with version 64058 on http://svn.boost.org/svn/boost/trunk.  Is that the 1.44 branch?

No -- that's the trunk, and some of those changes will not get in until 1.45 (but BGL should be the same).  What you need to test against is https://svn.boost.org/svn/boost/branches/release.

I also put my implicit graph example into a single source to make it easier to include in the examples directory.  

Good.  I'll check it over again and most likely put it in soon.

The A* maze solver example and the implicit graph example both build and run correctly using the Boost release tree (https://svn.boost.org/svn/boost/branches/release) revision 64062.

Good -- you can safely say your code will work with 1.44 then. -- Jeremiah Willcock

On Thu, Jul 15, 2010 at 6:50 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Thu, 15 Jul 2010, W.P. McNeill wrote:

...

On Thu, Jul 15, 2010 at 5:45 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: I just verified that everything builds and works with version 64058 on http://svn.boost.org/svn/boost/trunk. Is that the 1.44 branch?

No -- that's the trunk, and some of those changes will not get in until 1.45 (but BGL should be the same). What you need to test against is https://svn.boost.org/svn/boost/branches/release.

I also put my implicit graph example into a single source to make it easier to include in the examples directory.

Good. I'll check it over again and most likely put it in soon.

The A* maze solver example and the implicit graph example both build and run correctly using the Boost release tree (https://svn.boost.org/svn/boost/branches/release) revision 64062.

I added both of your examples into the Boost trunk in r64063 (with a small change in r64064). Please check and see if you are fine with them. I put implicit_graph.cpp in as-is (except for changing a quote to a normal ASCII quote); I tweaked astar_maze.cpp a bit (changing the distance type to double and adding missing braces around an initializer) to fix compiler warnings. Thank you for your contributions to BGL.

I picked up all your changes. I'm surprised that astar_maze.cpp has warnings since I'm building it with -Wall -Werror g++ flags. The astar_maze.cpp in revision 64064 looks good. Can you pick up the latest implicit_graph.cpp on github (commit 916fe4e05c0b75dfd48d). This fixes the non-ASCII quote, changes stringification for edges and (most importantly) removes a comment from the code which is incorrect and might be misleading to people using it as an example. After this change I'm going to declare this example complete. Thanks again for all your help.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I seed the random number generator once at the top of main(). This is sufficient to generate a different random maze every time the program is run or if multiple random mazes were to be created in the same run. On Wed, Jul 14, 2010 at 1:43 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

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

A-Star-Maze solver is pretty much done. The filtered_graph does make the

...

code a lot simpler. I used lexical_cast and Boost's random number facilities, but decided the Boost command line processing code was overkill for this example. The warnings you added about not subclassing BGL types look good.

OK.

Two things that look like documentation errors:

...

1. On the A* search page, the examine_vertex prototype for the visitor is listed as vis.examine_vertex(u, g), but you actually need it to

be vis.examine_vertex(u, const g) in order for the code the build. (This may be true for the other visitor functions as well.) This tripped me up when I first wrote my visitor class. I'm not sure if you want to specify the constants here, or let them be assumed. 2. The grid graph indexing documentation incorrectly states that you get a vertex index with get(boost::vertex_index, vertex_descriptor, const Graph&).

The order of the last two parameters is switched. The header actually specifies get(boost::vertex_index, const Graph&, vertex_descriptor). This appears to be the case in the documentation for a number of the get(...) functions.

I believe I fixed both of these now. Please check.

BTW, you don't need to create your own weight map if the weights are all the same; just use something like static_property_map<double>(1.) as the weight map. Also, why do you need your own vertex index map? It appears to just forward to the grid graph's version; why not just use that one directly? It appears that filtered_graph forwards property map requests to the underlying graph by default anyway, so you might just be able to remove that argument from your call to astar_search. You also don't need to call num_vertices() on the underlying graph; calling it on the filtered_graph does the same thing. Does your random_int() function re-seed the RNG to get a different answer each time?

I think overall that your code is nearly ready to put in. What did you want me to do with the README.md file? Put that in the documentation somewhere, or is most of the content in there about building it outside Boost (where it will build with the rest of the BGL examples using Boost.Build)?

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I intentionally used associative_property_map<> structures for the predecessor and distance maps for space efficiency. Since I know not every vertex in the grid will be visited, it made sense to have a map keyed on vertices rather than a vector with elements for all the vertices. Am I right in thinking that iterator_property_map won't work for this implementation? (Since std::map does not model a Random Access Iterator.) Of course for time efficiency it may still be better to create vectors for the entire grid rather than maps, particularly for small mazes. But I want to use maps to illustrate the principle. Also, a hash map would be better than std::map, but there's no standard hash map implementation so I stay away from it. (I'm waiting for a Boost hash_map :-) Using map structures brings up another question: am I correct in thinking that astar_search_no_init(...) does not permit named parameters so that I have to create all the various maps myself? (That is what I have gleaned from looking at the source and experimenting, but I've been wrong before.) I ask because the real project I'm using this maze search as a warmup for is aimed at a class of problems where most of the grid is not visited, so I want to avoid the O(V) initialization by calling astar_search_no_init(...) with maps that have the correct default values. On Mon, Jul 12, 2010 at 1:12 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

On Mon, 12 Jul 2010, W.P. McNeill wrote:

I've got a working A-star maze solver. The code is checked into the

...

github Astar-Maze-Solver project. 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.

One more that has hit other people is named parameters (especially the thing about using "." between arguments rather than ",").

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

...

Yes, and thank you for doing the example.

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

OK. I don't think anyone had tried astar_search with an implicit graph before the earliest bug report on the issue (the first one, though, was about implicit graphs that don't have num_vertices() and astar_search's failure on those).

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

The subclassing thing is based on STL; you are not supposed to subclass STL containers either. If you want to selectively remove edges, look at boost::graph::filtered_graph ( http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/filtered_graph.html). You should be able to wrap that on top of the existing grid_graph.

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.

Where do you think that should go?

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.

One minor thing: maze_traversal_catetory should be maze_traversal_category. I think using filtered_graph might replace all of that code, however. You might also want to use iterator_property_map or shared_array_property_map instead of associative_property_map for performance. If you want to really make the code Boost-like (and I'm not suggesting or requiring that you do this), you can also use Boost.Program_options, Boost.Lexical_cast and Boost.Random to replace the corresponding C functions that you are using now. You are also free to use "using namespace std;" and/or "using namespace boost;" in examples; you can put those in if you think it will make the code more readable.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

I used boost::unordered_map for the A* output property maps. Since I'm also keeping track of a set of vertices to remove from the filtered graph, I tried implementing this with boost::unordered_set instead of std::set. This doesn't build. The error message is: maze.cpp:243: instantiated from here /src/boost-trunk/boost/graph/filtered_graph.hpp:60: error: no matching function for call to ‘set_contains(const boost::unordered_set<vertex_descriptor, vertex_hash, std::equal_to<vertex_descriptor>, std::allocator<vertex_descriptor> >&, const boost::array<size_t, 2ul>&)’ What's going on is the vertex_subset_complement_filter calls is_not_in_subset, which calls set_contains in set_adaptor.hpp, which takes a std::set as its first argument. Maybe you'd want to template this set type too. I'll keep std::set here, but that might be a good new feature. On Wed, Jul 14, 2010 at 2:04 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

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

I intentionally used associative_property_map<> structures for the

...

predecessor and distance maps for space efficiency. Since I know not every vertex in the grid will be visited, it made sense to have a map keyed on vertices rather than a vector with elements for all the vertices. Am I right in thinking that iterator_property_map won't work for this implementation? (Since std::map does not model a Random Access Iterator.) Of course for time efficiency it may still be better to create vectors for the entire grid rather than maps, particularly for small mazes. But I want to use maps to illustrate the principle. Also, a hash map would be better than std::map, but there's no standard hash map implementation so I stay away from it. (I'm waiting for a Boost hash_map :-)

OK, although here it might be worth wasting the space. I don't think an iterator_property_map will work on an std::map. There is a Boost hash_map -- it's named boost::unordered_map.

Using map structures brings up another question: am I correct in thinking

...

that astar_search_no_init(...) does not permit named parameters so that I have to create all the various maps myself? (That is what I have gleaned from looking at the source and experimenting, but I've been wrong before.) I ask because the real project I'm using this maze search as a warmup for is aimed at a class of problems where most of the grid is not visited, so I want to avoid the O(V) initialization by calling astar_search_no_init(...) with maps that have the correct default values.

It appears that it doesn't allow named parameters, so right now you need to fill all of the parameters manually. That could be added later if it was important.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Wed, Jul 14, 2010 at 3:59 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:

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

I used boost::unordered_map for the A* output property maps.

...

Since I'm also keeping track of a set of vertices to remove from the filtered graph, I tried implementing this with boost::unordered_set instead of std::set. This doesn't build. The error message is:

maze.cpp:243: instantiated from here /src/boost-trunk/boost/graph/filtered_graph.hpp:60: error: no matching function for call to ‘set_contains(const boost::unordered_set<vertex_descriptor, vertex_hash, std::equal_to<vertex_descriptor>, std::allocator<vertex_descriptor> >&, const boost::array<size_t, 2ul>&)’

What's going on is the vertex_subset_complement_filter calls is_not_in_subset, which calls set_contains in set_adaptor.hpp, which takes a std::set as its first argument. Maybe you'd want to template this set type too.

Try r64026 -- unordered_set should work in that version.

That worked. I am able to use boost::unordered_set for my vertex sets after r64026.

-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users