Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-14 15:31:42

on Sun Dec 14 2008, "Tim Keitt" <tkeitt+list-AT-gmail.com> wrote:

> I've run into some problems with the Graph library as there is a lot
> of code that splits iterator ranges. An example of this is:
>
> (from depth_first_search.hpp)
>
>   template <class VertexListGraph, class DFSVisitor, class ColorMap>
>   void
>   depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color)
>   {
>     //
>     // should the below not be:
>     // graph_traits<VertexListGraph>::iterator vi, vend;
>     // tie(vi, vend) = vertices(g);
>     // if ( vi == vend ) ...  ???
>     // or perhaps to be more terse
>     // if ( empty_range(vertices(g)) )
>     // where empty_range(g) compares first and second
>     //
>     if (vertices(g).first == vertices(g).second)
>       return;
>
>     depth_first_search(g, vis, color, *vertices(g).first);
>   }
>
> This is causing problems in my code where I have defined custom graph
> classes. In my case
>
>   out_edges(g) != out_edges(g)
>
> because memory is allocated within the out_edges call and successive
> calls will return different ranges (vertex ranges are not a problem in
> my case as I use a simple counting iterator). Must out_edges(g) ==
> out_edges(g) for a graph class to meet the Graph library requirements?

Hmm. Well, it doesn't look like that's a documented requirement, but
maybe it should be (actually, out_edges(u,g) == out_edges(u,g)).  After
all, writing algorithms without making that assumption could be very
difficult.  I can even imagine that one might need to store these
iterators (in a heap or something) and come back to them compare them
with the end iterator later, which would be awkward at best and
impossible at worst unless one could make that assumption.

> If not, then a good bit of the code needs to be altered and possibly
> some of the iterator macros deprecated.
>
> Below I've located every instance where the first or second member of
> an iterator pair is thrown away. These cases are only problematic if
> the retained iterator is later compared to an iterator from another
> range.
>
> The fix is simple. One only needs to retain both members of the
> iterator pair. I am willing to provide a patch if it is agreed that
> the current code is wrong.

I'm not entirely against it, but I guess I'd need to be convinced that
it was really a worthwhile generalization.  

Since your out_edges() calls are already heavyweight, why don't you do
something to make iterators from consecutive calls compare equal? For
example, you could store the source vertex descriptor and offset in
them.  If that's at all practical, I would consider it a fairly good
argument for tightening the IncidenceGraph requirements a little bit so
the assumption was valid.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com