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

Subject: Re: [Boost-users] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2012-03-19 01:53:12

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<XY,XY>,
> 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 <boost/graph/filtered_graph.hpp>
> #include <boost/graph/graph_concepts.hpp>
> #include <boost/graph/graph_traits.hpp>
> #include <boost/operators.hpp>
> 
> 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<XY,
>     boost::totally_ordered<XY,
>     boost::equivalent<XY>
>     > >
> {
>     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<XY, XY>          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<XYGraph::out_edge_iterator,
> XYGraph::out_edge_iterator> 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<neighbor_iterator, XY,
> std::ptrdiff_t, XY *, XY>
> {
> public:
>     neighbor_iterator();
>     neighbor_iterator(XY xy, Direction::id direction);
>     neighbor_iterator & operator=(neighbor_iterator const& that);
>     std::pair<XY,XY> 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<XY,XY> 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<XYGraph,
> orthogonal_only> >));
> 
>     return 0;
> }