Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-16 14:06:38

on Tue Dec 16 2008, "Andrew Sutton" <andrew.n.sutton-AT-gmail.com> wrote:

>>
>> > Thinking about this more, it seems that if you are going to return
>> > iterator pairs, then it makes sense to assume they are unique per call
>> > and you should not compare iterators from different ranges (ie
>> > subsequent calls). Otherwise, I would suggest that calls like
>> > out_edges be split into out_edges_begin and out_edges_end because you
>> > may want very different things to happen when retrieving the beginning
>> > of a range and the end of a range.
>>
>> You're making a good point.
>
>
> I don't know that I agree with this - or perhaps I conditionally agree,
> depending on the concepts modeled by the custom graph - who knows.
>
> The IncidenceGraph, which defines the out_edges requirement is intended to
> abstract a view over a container. 

Iterators are intended to be an abstraction of pointers, and yet not all
categories carry the same requirements as pointers, and we're even going
to drop the *p => T& requirement for random access iterators in C++0x.

> For adjacency lists, this is a transform
> iterator over a container's range. 

Yes, but a transform is not necessarily a projection.

> For an incidence list or adjaceny matrix, it's probably
> filter+transform iterator over the list of edges or row/column of a
> vertex. If you assume this property holds:
>
> make_pair(C.begin(), c.end()) == make_pair(C.begin(), C.end())
>
> then it *should* follow that the ranges of adapted iterators also exhibit
> the same property. This is probably expressable as some kind of congruence
> relation. Something like:
>
> typedef adapted_iterator<C::iterator> iterator;
> make_pair(iterator(C.begin()), iterator(C.end())) ==
> make_pair(iterator(C.begin()), iterator(C.end()))
>
> Obviously, allocating the range from an SQL query is substantially different
> than pulling iterators from an in-memory container, but I think I would
> argue that this property should be preserved. 

That was my initial instinct, too.  but Tim is pointing out that the
algorithms can all be raised to a higher level of generality without
loss of efficiency, and I am now inclined to agree that there's no
reason they need to reply on this property.

> If you can make your out_edge_iterators model this behavior, then your
> graph should be interoperable.
>
> Of course, this is all conjeture, undocumented and up for discussion.
>
>> I'm guessing that if you submit a patch for the library that updates the
>> code and docs,  and passes the library's test suite (you should test
>> that yourself), it would probably be accepted.
>
> I'm not against adding *begin and *end variants for the iterator ranges, but
> I'm not sure how much it actually gives you - except avoiding this notation:
> *vertices(g).first.

That's not the patch I (or Tim, I think) had in mind.  I'm talking
about changing the algorithms so they no longer rely on 
out_edges(u,g) == out_edges(u,g) and updating the documentation to make
it completely clear that the property just stated is not part of the
concept requirements.

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