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:
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
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk