[boost] [graph] VertexListGraph and InputIterator, and LEDA graph

Subject: [boost] [graph] VertexListGraph and InputIterator, and LEDA graph
From: Jens Müller (blog_at_[hidden])
Date: 2012-01-01 16:12:16

Hi all,

I'm currently fixing up leda_graph.hpp so it passes the tests, or 
indeed, fixing the tests ...

A leda::GRAPH<int,int> (=Graph) has to fulfill VertexListGraphConcept. 
This means that boost::graph_traits<G>::vertex_iterator has to be a 
MultiPassInputIterator, i.e., also a InputIterator.

I cannot read from http://www.sgi.com/tech/stl/InputIterator.html that 
it must be possible that you can compute the difference between two 
iterators.

But apparently the concept check (which fails) requires a difference 
type, which must be a signed integer. Is this a bug in the concept check?

The vertex_iterator type is defined in leda_graph.hpp using iterator_facade:

     class vertex_iterator
       : public iterator_facade<vertex_iterator,
                                leda::node,
                                bidirectional_traversal_tag,
                                const leda::node&,
                                const leda::node*>
     {
     public:
       vertex_iterator(leda::node node = 0,
                       const leda::GRAPH<vtype, etype>* g = 0)
         : base(node), g(g) {}

     private:
       const leda::node& dereference() const { return base; }

       bool equal(const vertex_iterator& other) const
       { return base == other.base; }

       void increment() { base = g->succ_node(base); }
       void decrement() { base = g->pred_node(base); }

       leda::node base;
       const leda::GRAPH<vtype, etype>* g;

       friend class iterator_core_access;
     };

Is maybe iterator_facade insufficient? For me, 
bidirectional_traversal_tag does not indicate that random access is 
possible ...

-- Jens