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

Subject: Re: [Boost-users] Default weight map doesn't work for weighted grid graph in A-star search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-13 11:55:29

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