Boost logo

Boost Users :

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

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.


Project blog (SnargleQuest, a Roguelike game):

// 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,

struct XY : public boost::additive<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

    // 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
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>
    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 ==

int main(int argc, char **argv)

    // This fails
    BOOST_CONCEPT_ASSERT((IncidenceGraphConcept< filtered_graph<XYGraph,
orthogonal_only> >));

    return 0;

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at