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: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-07-13 13:56:03

Different out edge iterators was the problem for my filtered graph example.

It's spelled "compliment" in filtered_graph.hpp lines 507-516.  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 right-hand 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>