[boost] Re: data accessor/decorator

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-12-08 10:37:50

Hi,
At 08:47 AM 12/8/99 -0500, Dave Abrahams wrote:
>Dietmar wrote:
>> I haven't seen any comment on the 'operator[]()' issue. Thus, I will
>> assume that there is no objection to the use of the 'get()' and 'set()'
>> in algorithms to access the properties.
>
>I missed the op[]() issue. What was that?

Jeremy's interface for property accessors uses only 'operator[]()'. Mine
uses two functions, depending on whether the data is read or written,
ie 'get()' and 'set()' respectively. I made a point why this separation is
important: basically, whenever a property is not directly stored but is
both read and written it is useful to separate the functions. This can be
done with a proxy object using a user defined conversion and special
assignment operator but I strongly prefer the use of two functions.

>> In the context of graph algorithms, it is desirable that a property
>> accessor can be "indexed" using different kinds of identifiers for
>> the objects whose properties are to be accessed. For example, the
>> accessor for a node property should both be indexable using either
>> a node iterator or a node descriptor.
>
>As far as I understand the term, a node descriptor is just what you get from
>dereferencing a node iterator. If you can get to the property from the
>descriptor, you can of course get there from the iterator.

... because you can dereference the iterator? Or because the property
accessors handles both iterators and descriptors? There is a subtle
difference between these two: The former assumes that there is indeed
a dereference operator ('operator*()') while the latter does not.

I'm still not convinced that a dereference operator for the iterators is
really the right thing: Currently I'm using an int eg. for node iterator
in my grid graph. This works just fine...

>But I don't see the use of the node descriptor to the graph algorithm. I
>thought you had the same position. Has that changed?

Yes, this has changed in some way: I was aware of the use of node and
edge descriptors as an optimization technique (descriptors at least
sometimes contain less data than iterators) but in a recent project it was
necessary to introduce this concept to cope with certain temporary
structures (the graph's structure was modified in the nodes on the fly
in certain situations but this was just a temporary view). Descriptors
are useful in several context. For example, in priority queues it is often
sufficient to store a descriptor. ... or the reference to the  parent node in
a spanning tree doesn't have to be an iterator, the edges along a path,
etc. However, this discussion is actually independent from the property
accessors...

>I think I've seen some posts suggesting that you should always be able
>to get at the source node for an edge as well as the destination node.

No, this should definitely not be a general requirement! Many algorithms
never ever access the source of an edge but only the destination.
However, incidence iterators probably should provide access to the
source node and there is normally no problem with the graph data
structure because the source node can be remembered when the iterator
is constructed. Potentially this can be factored into a separate category
it is indeed useful to have incidence iterators without access to the
source node.

>I hate the names "head" and "tail" for edge start and end points. They have
>the opposite meaning for the arrows that we usually use to draw edges with
>(the head is the pointy end of the arrow).

I'm using them because they are short. Source and destination are fine
with me and I don't really care much about these names.

>Do a best-first search over a graph labeling each node with its minimum cost
>from a start node, while AT THE SAME TIME copying the graph into a new
>structure. Here's some simple pseudo-code for the search (almost Python!):
>
>bfs(first, visit, cost)

"bfs" is a bad name for a best first search: Normally BFS refers to
breadth first search ie. uses a FIFO, not a priority queue.

>    q.push(0, first)
>    while (!q.empty()):
>        c, n = q.pop()
>        if not visited(n):
>            mark(n)
>            if (visit(n)) return
>            for e in n.outgoing():
>                q.push(c+cost(e), e.destination)

This does not copy the graph, does it?

>There are a number of problems here. To begin with, you want to label nodes
>with costs, so the visit function needs to get the cost somehow.

'visit' is a "callback". I woudn't do it this way... I would rather use an
algorithm iterator.

> Also, the
>obvious place to copy the graph would be the "visit" function, but you don't
>get an edge there so you'd have to distort the algorithm so it visits edges.

Yes, searches normally should put edges into the queue, stack,
whatever: Just getting the next node is normally quite useless. You
can provide some label to the nodes but this is about it. You can't
even create a path this way because you can't tell from which node
the current node was reached, not to mention that there are normally
multiple edges between nodes (at least between some of the nodes in
a graph).

>OK, no problem... except that you don't visit nodes which have already been
>visited so you would only ever get a single incoming edge in the graph's
>"copy" (it would be a tree). Dietmar's "algorithm iterator" might begin to
>address the issue, but I wonder about its applicability in algorithms that
>don't have a single, obvious "main loop" with an obvious point at which to
>return.

It is indeed not at all easy to determine the right points where an
algorithms should stop and there are often multiple points. The
approach I'm taking in these cases is Duff's Device in the advance
function (eg. operator++()): A template argument is used to select
the break points using a bitmask. Each break point corresponds
to a state in an underlying state machine defined by the algorithm
(the state machines are there but normally not explicitly mentioned
in the description of the algorithms). If the algorithm breaks in a
certain state, this state is remembered and later used as an entry
point into the algorithm. In this context, it is convenient to use
Duff's Device to resume processing at the right point.

Since this thread is about the interface for property accessors, I'm
not giving an example here. I can give examples in a thread discussing
details of algorithm implementations...

>I suggest we look at the above case carefully before pinning down too much.
>It seems a tough nut to crack.

It is a thought worth considering but I think it does not influence
the interface for property accessors... Actually, I think it only has
to be considered when actually implementing the algorithm and is
also independent from the interface used by the algorithms.

Regards,
  dk