[boost] Re: graph structure interface compomise?

From: jsiek_at_[hidden]
Date: 1999-12-08 23:55:12

Fantastic. We're making great progress. Just some replies to your
questions here.

Dietmar Kuehl writes:
 > 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?

The reason I had begin() and end() there was that I was thinking that
perhaps it would be nice to not actually specify the use of std::pair
as the return type, but just require that it is something that works
with begin() and end(). I suppose the begin() and end() functions
could go in the same namespace as the graph library implementations
(and later in std when it gets accepted ;) I've actually wished for
these functions for use with the returned pair of equal_range().  The
begin() and end() aren't terribly important to me, though having
the single function that returns a pair is.

 > 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

Yes, it was posted to Boost. I like it. Here's how it would look with
the graph interface:

tie(first,last) = adj(v,g);

A dumbed-down, two argument version is trivial to implement:

template <class A, class B>
class Tie
{
public:
  Tie(A a, B b) : first(a), second(b) { }
  template <class Pair>
  Tie& operator=(const Pair& p) {
    first = p.first;
    second = p.second;
  }
protected:
  A first;
  B second;
};

template <class A, class B>
Tie<A&,B&> tie(A& a, B& b) {
  return Tie<A&,B&>(a,b);
}

Perhaps just specifying pair is fine, and leave it up to people's
taste as to what they do with it. This is already the approach
taken in STL.

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

My experience with SGI CC, Metrowerks, and KAI C++ would say the
overhead goes away completely (and IMHO the bad compilers just need to
get better).

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

I agree, the names are too close. incidence iterator is OK with me.

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

Yes, it should be factored.

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

I'm not sure either. Perhaps we can find some algorithm examples where
this makes a difference.

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

Or the edge descriptor could just be the edge ID...

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

Fair enough.

 > 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 :-)

Shall we start on a more formal write up of the interface?  Which
format do you prefer, latex? html? (please not MS word :) Do you want
to focus on the write up for PropertyAccessor, and I on the traversal
interface? One request that I have for the document format. The
"concepts" should be documented similarly to Matt Austern's book
(though perhaps using requirement tables closer to how they look in
the standard).

As to getting in touch with the GTL and LEDA folks, sounds good
(though I have to admit I would not want to change much from our
current interface).

Cheers,

Jeremy

----------------------------------------------------------------------
 Jeremy Siek
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
 and                         cell phone: [phone]
 C++ Library & Compiler Group       fax: [phone]
 SGI                                www: http://www.lsc.nd.edu/~jsiek/
----------------------------------------------------------------------