[boost] Re: graph structure interface compomise?

From: Bill Wade (bill.wade_at_[hidden])
Date: 1999-12-08 14:13:55

> Excellent: Looks like we get agreement on the graph interface
> relatively fast, too! Now that is is basically nailed down, we should
> invite other parties, eg. those from GTL and LEDA, to participate
> in the discussion :-)

I missed any discussion of performance requirements.  In STL almost all
iterators support advance() but relatively few (the fast ones) support
integer addition.  That interface makes it easy for me to write code that
assumes random access, without writing any explicit compile time assertions.

Writing graph algorithms I might want to make similar distinctions between
graphs that provide fast (O(1) or O(ln N)) adjacency operations and those
that don't.  In a similar vein, only fast decorators should use [] notation.