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():

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]’:
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]’
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