
Boost Users : 
Subject: [Boostusers] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph
From: Luke Meyers (n.luke.meyers_at_[hidden])
Date: 20120319 01:23:40
Hello, list. First time poster, sometime reader. Today I finally achieved
a milestone I've been working towards in my BGLoriented 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 righthand 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 prelink). 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;
}
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net