[boost] Re: graph interface/implementation

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 1999-12-10 13:51:32

Hi,

> >>Hashing?
> >
> > Unless the answer to 'op<()' already answered this question, this
> > question is a little bit too brief to me to understand it...
> 
> Here I'm aiming at the fact that many algorithms need to look up
nodes or
> edges in short order (e.g. in a hash table). A simple example is
marking
> nodes as visited in a search.

Ah, yes. This is what property accessors are for: The node descriptor
gives eg. the index used to look things up in the hash which is
accessible
from the property accessor. The node descriptor might also provide an
integer used as an index into an array or just a pointer which can be
dereferenced. Note, that one property accessor might internally use
another one, eg. to get an index extracted from a node record to which
the descriptor points. The only tricky part is the complexity: I'm
normally assuming that access to properties have constant complexity,
at least amortized.

If the complexity rules are not obeyed the performance of the
algorithms
might go somewhat astray. On the other hand these algorithms are
sufficently complex and have enough variability without taking care of
different complexity traits of the property accesses. In general there
should be no real problem: Just multiply the nominal complexity of the
algorithm with the complexity of the property access to get a new worst
case estimate. On average, the real performance should be better
though...

> > On the other hand, using this approach makes it viable to reuse
> > algorithms in the first place rather than implementing them from
> > scratch over and over again. The callback interface is not
necessarily
> > better because it gives less control over the algorithm.
> 
> If you have enough callbacks, you can surely do all the same things.
I'm not
> sure what loss of control you fear, but from an efficiency
point-of-view it
> might make sense to exit the algorithm by throwing an exception (no,
I'm
> really NOT kidding).

Argh: Unexpected attack from behind! :-)

> > What should
> > be used and what is more effective should definitely be measured.
> > Having a stable interface for the graph structure should give the
> > opportunity to do so!
> 
> Agreed!

Maybe I can manage to get a complete walk-through for simple algorithms
starting with a textbook version and moving it towards a very general
one done over the weekend.

Regards,
  dk

__________________________________________________
Do You Yahoo!?
Thousands of Stores.  Millions of Products.  All in one place.
Yahoo! Shopping: http://shopping.yahoo.com