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