
Boost Users : 
Subject: Re: [Boostusers] Default weight map doesn't work for weighted grid graph in Astar search
From: W.P. McNeill (billmcn_at_[hidden])
Date: 20100713 13:56:03
Different out edge iterators was the problem for my filtered graph example.
It's spelled "compliment" in filtered_graph.hpp lines 507516. 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 righthand 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_at_[hidden]>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
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net