New subject: [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph

19 Mar 2012

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

[Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph

Luke Meyers

Cedric Laczny

Luke Meyers

Jeremiah Willcock

Luke Meyers

tags

participants (2)