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.<div>
<br></div><div><div>main.cpp:38: instantiated from here</div><div>/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()’</div>
<div>/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>]</div>
<div>/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> >&)</div>
<div>make: *** [main.o] Error 1</div><div><br></div><div>Presumably the same issue.</div><br><div class="gmail_quote">On Mon, Jul 5, 2010 at 9:50 PM, W.P. McNeill <span dir="ltr"><<a href="mailto:billmcn@gmail.com">billmcn@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">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.<div>
<br></div><div>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:</div><div><br></div><div><br></div><div><br></div><div><div>#include <boost/graph/astar_search.hpp></div>
<div class="im">
<div>#include <boost/graph/grid_graph.hpp></div></div><div>#include <iostream></div><div><br></div><div>using namespace boost;</div><div><br></div><div>typedef grid_graph<2> grid;</div><div>typedef graph_traits<grid> traits;</div>
<div>typedef traits::vertex_descriptor vertex_descriptor;</div><div>typedef traits::edge_descriptor edge_descriptor;</div><div><br></div><div>typedef double edge_weight_type;</div><div><br></div><div>struct zero_heuristic:public</div>
<div> boost::astar_heuristic<grid, edge_weight_type> {</div><div><br></div><div> edge_weight_type operator()(vertex_descriptor v) {</div><div> return 0;</div><div> }</div><div>};</div><div><br></div><div>int main (int argc, char const *argv[]) {</div>
<div> array<size_t, 2> sizes = {{ 3, 2 }};</div><div> grid g(sizes);</div><div> shared_array_property_map<edge_weight_type,</div><div> property_map<grid, edge_index_t>::const_type></div>
<div> weight(num_edges(g), get(edge_index, g));</div><div><br></div><div> vertex_descriptor start = vertex(0, g);</div><div><br></div><div> astar_search(g,</div><div> start,</div>
<div> zero_heuristic(),</div><div> weight_map(weight) );</div><div><br></div><div> return 0;</div><div>}</div><div><br></div><div><br></div><div>It fails to compile with an error about missing a function for boost::detail::grid_graph_vertex_at():</div>
<div><br></div><div><div class="im"><div>g++ -g -I/opt/local/include -c -o main.o main.cpp</div></div><div>/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]’:</div>
<div>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]’</div>
<div>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>]’</div>
<div>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>]’</div>
<div>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]’</div>
<div>main.cpp:38: instantiated from here</div><div>/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()’</div>
<div>/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>]</div>
<div>/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> >&)</div>
</div><div><br></div>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 <span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">3917.</span></div>
<div><br></div><div><br><div class="gmail_quote"><div><div></div><div class="h5">On Mon, Jul 5, 2010 at 2:06 PM, Jeremiah Willcock <span dir="ltr"><<a href="mailto:jewillco@osl.iu.edu" target="_blank">jewillco@osl.iu.edu</a>></span> wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div class="h5"><div>On Mon, 5 Jul 2010, W.P. McNeill wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I'm using my own graph class because I need an implicit graph for the task I'm trying to do.<br>
<br>
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.)<br>
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<br>
empty cell is 1, and the cost of entering a blocked cell is infinity.<br>
(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<br>
will be reusable. Plus, I think an a-star maze search example would be useful for others to see.)<br>
<br>
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<br>
and vertex properties to Boost's grid_graph class, but I ran into compile errors, some of which are documented earlier in this thread.<br>
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<br>
grid_graph, so it would be easier to implement my own grid.<br>
<br>
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<br>
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<br>
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<br>
property.<br>
</blockquote>
<br></div>
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.<br>
<font color="#888888">
<br>
-- Jeremiah Willcock</font><br></div></div><div class="im">_______________________________________________<br>
Boost-users mailing list<br>
<a href="mailto:Boost-users@lists.boost.org" target="_blank">Boost-users@lists.boost.org</a><br>
<a href="http://lists.boost.org/mailman/listinfo.cgi/boost-users" target="_blank">http://lists.boost.org/mailman/listinfo.cgi/boost-users</a><br></div></blockquote></div><br></div>
</blockquote></div><br></div>