[boost] Re: data accessor/decorator

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-12-08 08:47:39

Dietmar wrote:
> Hi,
> At 02:40 PM 12/7/99 -0500, jsiek_at_[hidden] wrote:
>>How about "property accessor" as a compromise on the
>>name for data accessors/decorators?
>
> That's an excellent compromise: I even like it better than data
> accessor :-) It is more to the point and "property" does have
> both a singular and plural. "Data" only has one of them and I can't
> always remember which...

Actually, there's datum (singular) and data (plural). Usage of "datum" has
mostly fallen by the wayside.

> The interface for property accessors is still somewhat open and
> actually a little hard to define with respect to one of the arguments,
> namely the object used to identify the object whose properties are
> to be accessed: This can be very general ranging from a variaty of
> iterators to simple integers.
>
> 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?

> 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.

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?

A few other random thoughts:

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. I have
some graphs in which that is difficult and some algorithms for which it is
unneeded.

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 wanted to solve this problem the other day:
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)
    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)

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. 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.
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.

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

-Dave