Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2008-12-17 16:58:13

On Tue, Dec 16, 2008 at 1:06 PM, David Abrahams <dave_at_[hidden]> wrote:
>
> 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.

I've checked out http://svn.boost.org/svn/boost/trunk/boost/graph and
have converted almost all the cases where iterators are compared
across calls. A few questions:

1) does something like

template<class T>
inline bool
equal_pair(const std::pair<T, T>& p)
{
    return p.first == p.second;
}

exist somewhere in std or boost? If not would it be useful to add? It
would help with eg if ( equal_pair(vertices(g)) ) ...

2) what is the best way to test changes to the graph library?
3) I assume svn diff is sufficient. How do I submit the patch?

THK
>
> --
> Dave Abrahams
> BoostPro Computing
> http://www.boostpro.com
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Timothy H. Keitt
http://www.keittlab.org/