Boost logo

Boost :

From: Dietmar Kuehl (dietmar.kuehl_at_[hidden])
Date: 1999-12-08 12:28:18


Hi,
At 04:49 AM 12/8/99 -0500, jsiek_at_[hidden] wrote:
>Here's an attempt at a compromise on the graph structure interface.

Mostly, this looks good to me. There are some details I do not agree
with but I think these should be no problems. I will comment on them
below.

>Basically, I can live with the graph objects, but iterators have to be
>iterators :) (and input iterator or some new tag derived from input
>iterator will do)

As I have mentioned in previous mails, I can live the operator*()
and I don't think that it does cause a problem: Where it would, it
can be just a no-operation returning the iterator. The only case
which is sacrificed is the use of integer types as iterators. Since
this only requires a rather thin wrapper, this should be no problem.
... and it should not cause an overhead with a good compiler.

>First, a suggestion for some names. Instead of "node_pointer" I
>suggest "node_descriptor". Similarly for edge.

Since I was uncomfortable with the "pointer" anyway, this seems
to be an improvement: If descriptor is fine with you, it is with me.
I'm not a native English speaker and descriptor sounds OK.

>Also, I've moved the graph object from being the "this" object, to
>being in the paramter list. I've found that it's easier to extend and
>adapt in the presense of global functions than with member functions.

Since the graph object will not be a fundamental type, this is OK
if the compiler supports Koenig lookup: Otherwise we would have
to decide on a namespace where these functions live in. Since
Boost addresses libraries for conforming compilers, it is reasonable
to assume that solid Koenig lookup is supported. I hope that all
compilers we are using (persumable at least gcc and EDG front end
based compilers) get this right...

>In addition, I've replaces the pairs of functions that end in "_begin"
>and "_end" with a single function that instead returns literally a pair of
>iterators. The begin(p) and end(p) functions below just return the
>first and second element of the pair.

In which namespace do 'begin()' and 'end()' live? Since 'std::pair' is in
defined in namespace 'std' which is by definition closed, it is necessary
to provide the namespace for these functions! I don't think they should
go into the global namespace. Maybe it would be resonable to use
'p.first' and 'p.second' instead?

Personally, I would prefer if there were separate functions to get the
respective iterator, especially as C++ misses such neat assignment
operations as there are in perl where you can assign to a list of
objects at once (well, I think there was a library for this mentioned
somewhere; was it Boost or have seen it in news: I don't know). Is
it save to assume that the overhead involved in creating the pair,
returning it from a function, and selecting only one of the members
is removed by a good compiler, at least if the function is inline? If
not I would like to measure the effect of this before I would accept
it...

I know that the use of two methods is kind of ugly. However, it
solves the problem as hand: Getting a corresponding iterator.

>v is a NodeDescriptor
>e is an EdgeDescriptor
>g is a Graph
>alit is an adjacency list iterator
>elit is an edge list iterator
>nit is a node iterator
>eit is an edge iterator

Is the difference between "edge list iterator" and "edge iterator"
that the former iterates over the edges incident to a node while
the latter iterates over all edges of a graph? If this is the case, I
would suggest renaming "edge list iterator" into "incidence
iterator"! The names are otherwise too close to prevent confusion.
At least I know that I would keep getting confused...

Other than that, I assume that this interface is kind of a "complete"
interface conforming to several requirements which have to be
factored out: Not all algorithms need all of these properties and
thus it is neither necessary nor desirable to require all of the
properties. I made the same assumption in the list of operations
I posted.

>struct graph_traits {
> typedef ... node_descriptor;
> typedef ... edge_descriptor;
> typedef ... adjacency_iterator;
> typedef ... edgelist_iterator;
> typedef ... node_iterator;
> typedef ... edge_iterator;
>};
>
>alit = begin(adj(v,g)) // iterate through the nodes adjacent to node v
>alit = end(adj(v,g))

I would order the arguments the other way around but this is just
a minor detail: I have no problem ordering them this way. One
argument for this order pops to my mind but it is actually no argument:
This way you can use a default argument to provide the graph object
where it is not need. Since we are talking about generic algorithms
where it is always needed, this is not an argument...

>v = *alit // obtain a node descriptor from the adjacency list iterator

Is the intention of the adjacency iterator convenient access to the
node descriptor or is for iteration over the set of the adjacent nodes
excluding multiply visiting a node? For the former case it would be
reasonable although counter intuitive since this iterator might visit
the same node multiple times if there are parallel edges. In the latter
case it is sometimes hard to provide, eg. if a list of incident edges is
stored. I really don't know which of these is the desired behavior.

>v = source(e) // I don't see a need for the graph object on this one
>v = target(e)

Assume a graph representation using a vector for the set of
directed edges. Each node stores the index of the first and one
beyond the last outgoing edge. The incidence iterator can be a
thin wrapper for an integer which is desirable to have efficient
access to the edge ID for use in a property accessor mapping
IDs to properties stored in a vector. The edge descriptor can be
identical to the iterator. However, there is no way to determine
the nodes incident to the edge. The graph object would provide
somehow a reference to the corresponding vector where the edge
can be looked up and with it the corresponding node.

Thus, I think it is reasonable to provide the graph object for these
operations, too. If the operation is such simple that everything is
directly accessible from an edge descriptor, it is likely to be
implemented inline and a minor exercise for the compiler to be as
efficient with graph object as without.

Excellent: Looks like we get agreement on the graph interface
relatively fast, too! Now that is is basically nailed down, we should
invite other parties, eg. those from GTL and LEDA, to participate
in the discussion :-)

Regards,
  dk


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk