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