[boost] Re: property accessors

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

Hi,

> > I have just uploaded a first draft of the property accessor
description to
> > the Boost document vault at egroups:
> >
<http://www.egroups.com/docvault/boost/graphs/property_accessor.html>
> 
> I guess I'm still a bit confused. I thought property accessors were
an
> alternative to operator*() and that you had settled on operator*().
Once
> again, please explain to my feeble brain.

I settled that there is an 'operator*()' for the graph related
iterators
at all. However, with a very specific semantic which is a little
different from the normal STL semantic (but still reasonable in the STL
sense): The operator is supposed to return the respective descriptor,
ie.
for iterators on nodes the node descriptor and for iterators on edges
the
edge descriptor. This operators does not access data associated with
the
corresponding object which is kind of the normal STL assumption.

The problem with graph algorithms is that they need many different
properties of nodes and edges which is rather different from sequence
algorithms (STL == sequence template library :-) where there is
normally
just one property. Even worse, different graph algorithms give
different
names to the same thing such that it is not possible to use struct with
all properties accessed by 'operator*()'. ... and the property used by
one
algorithm is often slightly modified for another algorithm. For
example,
the free capacity in the augmenting path algorithm for the max flow
problem
can be used in a shortest path algorithm to find a path with big free
capacity: The length of the edges can be determined as 1/capacity (this
is just a heuristic improvement and does not give the path with highest
free capacity).

Property accessors are actually the important new abstraction for graph
algorithms!  The use of iterators for the graph structure is rather
obvious and not really new (eg. LEDA used something similar 10 years
ago). What is important is that you can parameterize the properties to
be accessed by the algorithm. Actually, with it's node and edge maps
LEDA
does something like this too for quite a while but there is essentially
no
way to play tricks with these maps: These are just external containers
indexed by nodes and edges. However, it is important to connect the
properties eg. by certain computations. Again an example from the max
flow algorithm: For the edge (i,j) the current flow, the free capacity,
and the upper bound are closely releated:

  free capacity = upper bound - current flow.

In addition, when looking at the edge from node j, it holds that

  free capacity = current flow

If you only have external maps you basically have to store the upper
bound and the current flow, always computing the free capacity *in the
algorithm* which requires a case distinction wherever you access the
free
capacity. Using a property accessor for the free capacity factors out
the
corresponding code into a property accessor. Since flow algorithms
often
just manipulate the free capacity, this is great help when implementing
algorithms and because the necessary property accessors need not be
provided by the user of the algorithm (by implementing corresponding
ones building on others) it is no problem to the user.

Anyway, the idea is basically this:
- operator*() on an iterator gives a descriptor for the underlying
object
- property accessors are used to, well, access properties of an object
  given a correspondng descriptor

Note that property accessors are not only useful in the context of
graphs. For example, if you take a step back you will see that the
I/O functions Jan Kristoffersen presented for embedded systems are
basically the same idea. This is of course no big surprise: Jan and
I worked out the basics at the Santa Cruz meeting... Again I noted as
similar effect as I described in one of the mails: Once Jan understood
the basic abstraction he wondered why he hadn't thought of it before!
It
is just plain obvious. There were still some technical details to solve
but the general way to go of this stuff was rather clear.

Regards,
  dk

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