Re: [Boost-users] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph

Hi, as far as I understood the filtered_graph concept, I see it as some sort of wrapper/adaptor. Actually, I think if you have a graph type G, using filtered_graph will give you a filtered_graph< G > type. In some cases, the resulting graph is accepted by BGL-algorithms, but I think to remember that there were also cases where I had to copy the filtered_graph into an instance of the original graph type (here G) again. Of course, this may introduce some overhead for the copying... Hope that helps. Best, Cedric On Sunday, March 18, 2012 10:23 PM, Luke Meyers wrote:

Hello, list. First time poster, sometime reader. Today I finally achieved a milestone I've been working towards in my BGL-oriented project: I got astar_search_no_init working on an implicit graph. Now I want to filter the input graph to restrict the search, and I'm running into trouble with filtered_graph. My implicit graph class is a model of IncidenceGraph, as required by astar_search_no_init, but when I apply filtered_graph to it I find that the result is no longer an IncidenceGraph (according to BOOST_CONCEPT_ASSERT).

The filtered_graph documentation saith:

If the underlying Graph type models VertexAndEdgeListGraph and

...

PropertyGraph then so does the filtered graph. If the underlying Graph type models fewer or smaller concepts than these, then so does the filtered graph.

...

From this, I would assume that if I run filtered_graph on an IncidenceGraph, the result will be a model of IncidenceGraph, not just of Graph. Also, if my input is an IncidenceGraph and not a VertexAndEdgeListGraph, I'd hope compilation would not fail if I don't have graph_traits defined for types required by VertexAndEdgeListGraph, but it does:

c:\src\boost_1_49_0\boost\graph\filtered_graph.hpp(181) : error C2039:

...

'in_edge_iterator' : is not a member of 'boost::graph_traits<XYGraph>'

When I provide a bunch of dummy typedefs to get around this error, I can get to the point of doing a BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<* FilteredGraphType*>)). This fails:

c:\src\boost_1_49_0\boost\graph\graph_concepts.hpp(94) : error C2679:

...

binary '=' : no operator found which takes a right-hand operand of type 'XY' (or there is no acceptable conversion)

XY here is my vertex descriptor type. The edge descriptor is a pair, but for some reason it's getting XY out of the graph_traits instead and failing in this strange way.

Am I missing something? Are my expectations incorrect? Is this actually a bug (or two)? At the bottom is a decently small example that fails for me (some function bodies excised for brevity -- my concerns are pre-link). Is there a way to work around this without making my graph into a model of VertexAndEdgeListGraph? Since my graph is infinite, this would hardly seem sensible.

Thanks in advance for any assistance. Incidentally, if anyone's interested to see a working example of astar_search_no_init over an implicit graph, I'd be happy to clean up the code a little and post it.

Luke

Project blog (SnargleQuest, a Roguelike game): http://snarglequest.blogspot.com/

// Code listing

#include <iostream> #include <list> #include <map> #include <set> #include <utility>

#include #include #include #include

using namespace boost; using namespace std;

namespace Direction { enum id { MIN = 0, N = MIN, S, E, W, NW, NE, SE, SW, NONE, NUM_DIRECTIONS }; }

struct XY : public boost::additive > { typedef int X; typedef int Y;

XY(X x = 0, Y y = 0);

XY & operator=(XY const& that); XY & operator+=(XY const& that);

bool operator<(XY const& that) const;

X x; Y y; };

std::ostream & operator<<(std::ostream & os, XY const& xy);

struct neighbor_iterator;

/* * Model of: * * Graph * * IncidenceGraph */ struct XYGraph { XYGraph();

// Graph concept requirements typedef XY vertex_descriptor; typedef std::pair edge_descriptor; typedef undirected_tag directed_category; typedef disallow_parallel_edge_tag edge_parallel_category; typedef incidence_graph_tag traversal_category;

// IncidenceGraph concept requirements typedef neighbor_iterator out_edge_iterator; typedef int degree_size_type; };

// IncidenceGraph concept requirements std::pair out_edges(XYGraph::vertex_descriptor v, XYGraph const& g); XYGraph::degree_size_type out_degree(XYGraph::vertex_descriptor v, XYGraph const& g); XYGraph::vertex_descriptor source(XYGraph::edge_descriptor e, XYGraph const& g); XYGraph::vertex_descriptor target(XYGraph::edge_descriptor e, XYGraph const& g);

// Iterator struct neighbor_iterator : public boost::forward_iterator_helper { public: neighbor_iterator(); neighbor_iterator(XY xy, Direction::id direction); neighbor_iterator & operator=(neighbor_iterator const& that); std::pair operator*() const; void operator++(); bool operator==(neighbor_iterator const& that) const; };

namespace boost { template <> struct graph_traits<XYGraph> { typedef XYGraph G;

typedef G::vertex_descriptor vertex_descriptor; typedef G::edge_descriptor edge_descriptor; typedef G::out_edge_iterator out_edge_iterator;

typedef G::directed_category directed_category; typedef G::edge_parallel_category edge_parallel_category; typedef G::traversal_category traversal_category;

typedef G::degree_size_type degree_size_type;

// Shouldn't have to do this! typedef void in_edge_iterator; typedef void vertex_iterator; typedef void vertices_size_type; typedef void edge_iterator; typedef void edges_size_type; }; }

struct orthogonal_only { typedef pair Edge; bool operator()(Edge const& edge) { return edge.first.x == edge.second.x || edge.first.y == edge.second.y; } };

int main(int argc, char **argv) { BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<XYGraph>));

// This fails BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< filtered_graph >));

return 0; }