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

Subject: [Boost-users] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph
From: Luke Meyers (n.luke.meyers_at_[hidden])
Date: 2012-03-19 01:23:40

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;
}