[boost] Re: graph structure interface

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-12-08 11:21:14

Hi,
At 05:04 PM 12/7/99 -0500, jsiek_at_[hidden] wrote:
> > - iit = go.begin(np)  // begin iterator for "incidence list" of the node
> > - iit = go.end(np)     // past the end iterator for this list
>
>maps to adj(v).begin() and adj(v).end()

It is this simple operation which made me introduce the graph object!
Here is why: With your approach, you have to determine the incident
edges just given a descriptor. There are two options how to do this:
Either the descriptor stores the necessary data to determine the set
of incident edges or the descriptor has to point to an object which
can be used for this purpose. If you have an explicit representation of
nodes, the latter is the obvious approach to take. Otherwise you can
only take the former approach.

Now consider a grid graph. This graph data structure is clearly an
extreme case but one which is actually used, eg. in VLSI design. All
this graph needs for a representation is the height and the width.
Nodes are just numbered and n / width gives the y coordinate and
n % width the x coordinate of the node. A node descriptor can just
store the number to uniquely identifiy the node. However, to
determine the incident edges, it has to know both the width and the
height: The width to determine whether there are edges leading to the
left and the right from the node, the height to determine whether there
are edges leading upwards.Thus, a node descriptor is three times the
size it could be!

I have seen that you used a graph object in a later mail. This was
just to give the reason why I have introduced it. I hesitated long
before doing so because I don't really like it. However, it solves
problems. It is not just convenience!

> > - ep = go.to_edge_pointer(eit) // obtain an ede pointer from an iterator
> > - ep = go.to_edge_pointer(iit) // obtain an ede pointer from an iterator
> > - np = go.to_node_pointer(nit) // obtain a pnode ointer from an iterator
>
>maps to operator*() for the iterator of an edgelist_type and vertexlist_type
>of the Vertex concept.

OK, using 'operator*()' to get the node or edge descriptor looks
reasonable and actually might even solve the problem of having
different iterator types to be used as index with a property accessor:
Property accessors can be defined to just use the descriptor as index.

Somehow I assumed that 'operator*()' would access some property
of the underlying object. I think I can accept the use of this operator
to obtain the corresponding descriptor. I'm not entirely happy with
it because it rules out the use of integers as one of the iterators (this
would be possible without the 'operator*()') but it is acceptable.

>II. Implications
>----------------
>
>I'm going to argue that Dietmar's interface makes for easier
>implementation, while the GGCL interface is more flexible (more
>abstract) and has a "cleaner" look to it.

The GGCL has a cleaner look (for an appropriate definition of "clean")
but it is in no ways more flexible! I will argue below why it is not more
flexible. However, I'm not going to argue that it is less flexible because
I think the interface allow the same degree of flexibility!

>b) When a Graph Object Isn't Needed
>
>One problem I have with the graph object approach is that there are
>some kinds of graph representations for which there is no need for a
>graph object.

Indeed and this was the major reason why I didn't like the graph object
and didn't use it for a long time! However, I have made my peace with
this situation using the following simple argument: If you use a well
defined interface in your iterators, it is easy to create a template graph
object class which is just parameterized with the corresponding iterator
types. The operations in the graph object are then just forwarding
functions to the corresponding iterator operations. It takes a litle bit
of infrastructure but not a lot. The gain on the other hand is significant!

>This is true of the kind of graph structure that Alex
>Stepanov's connected components algorithm works on.  Here's a little
>example of setting up a graph structure, and then calling his
>algorithm:

Somewhere in my thesis I'm using a list of words as a graph: Between
two nodes, ie. words, there is an edge if they have a Hamming distance
of one. There is no graph object either but it is easy to create suitable
iterators. However, using these iterators it is also easy to instantiate
a corresponding template providing the necessary graph object.

>With Dietmar's interface, one would have to create a graph object
>class that basically doesn't do anything, and then pass it around in
>the algorithms.

Exactly. This is a fairly small price to pay in situations where you
don't need it. The pay-off in cases where you need the graph object
is huge.

>c) Prettiness and Encapsulation
>
>So far the main advantage of Dietmar's interface is that it makes the
>graph structure easier to implement in some situations.

This alone would not be an argument for me! Ease of implementation
(with respect to the algorithm) simply is no argument. Good
performance, even in border cases, is an argument. Spending three
words instead of one can really degrade performance...

>As Dietmar mentioned previously, the difficulty of implementation
>should be of a lessor concern than the other interfacing issues.

Apparently I didn't make the context of this statement clear: I accept
it if it is more difficult to implement the library, that it in this case the
graph algorithms! I'm trying to make the implementation using the
library, ie. the graph data structure in this case, as easy as possible.

>Therefore I would encourage the move to the slightly more abstract
>but less easy to implement interface of GGCL.

Since using forwarding functions in the graph object and having a
corresponding template basically does the same thing, I can't see
where the GGCL interface is more abstract. Which case is sacrificed
if the graph object is there?

>III. Miscellaneous Replies
>--------------------------
>
> > - Most interesting graph algorithms associate more than just one piece
> >   of data with an object like a node or an edge, eg. in flow algorithms
> >   there are upper and lower flow constraints as well as the current flow
> >   associated with each edge. Which of these shall 'operator*()' access?
> >   Basically, 'operator*()' addresses a similar problem that the
decorators/
> >   data accessors are intended to solve!
>
>In GGCL, the operator*() does not pick "just one peice of data" for the
>return value. Instead it returns a Vertex, which is something like the
>NodePointer of Dietmar's interface. The Vertex can then be used with a
>data accessors to get different peices of data.

This was a misunderstanding on my side! Using 'operator*()' to access
the corresponding descriptor would be acceptable although I don't
really like it... (see above).

>I suppose one could consider the typical Vertex of GGCL a proxy class,
>but I do not see the problem with that, nor how that violates STL
>requirements. In fact, most standard implementations of
>ostream_iterator use a proxy class (the SGI version uses the
>ostream_iterator itself as a proxy).

The iterators used by graph algorithms need to be at least forward
iterators: You need multiple passes in many cases. There is no
concept between forward iterators and input iterators in the current
STL definition. For forward iterators the requirements dictate that
you have to return a reference ('T&' or 'T const&') from 'operator*()'.
This requirement is used in algorithms (see the other mails in this
thread which address this issue).

However, again this confusion at least partially stems from a
misunderstanding on my side! Returning the descriptor from
'operator*()', even as a proxy, seems to be reasonable because
this object is immutable anyway! However, I don't think that the
STL requirements are a good argument in favor of this operation
because you simply can only use a few of them on iterator accessing
a graph's structure. The use in obtaining a descriptor from an iterator
is much more convincing (at least to me).

Regards,
  dk