Boost logo

Boost :

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" <> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at