[boost] Re: graph structure interface compomise?

From: jsiek_at_[hidden]
Date: 1999-12-10 19:58:30

Dietmar Kuehl writes:
 > 
 > - In the mathematical definition of the graph I dislike a particular
 >   implied restriction: Sets, by definition, do not include multiple
 >   copies of the same elements. That is, the definition of a graph
 >   you have given rules out parallel edges. This is rather typical

Good point, I've changed it to say "E is a collection of edges".
I think "set" is still appropriate for the vertices, yes?

 > - Although they are low, there are requirements imposed on the
 >   descriptor types: These types have to be Assignable (this reminds
 >   me that the value type for the property accessors also has to be
 >   assignable for all property accessors except
 > ReadablePropertyAccessor;
 >   this is not yet mentioned...) and potentially even EqualiyComparable.

Yes, I can think of at one place in GGCL algorithms where equality
is needed. I'll go with both Assignable and EqualityComparable.

 > - We need to define exactly what an adjacency iterator iterates over.
 >   There are two options (I can see...):
 >   - The *set* of adjacent edges. In this case there would be
 > significant
 >     difference to incidence iterators, eg. because the cardinality of
 >     the resulting nodes differs if parallel edges are present. However,
 >     this is in general non-trivial to achieve and I can't think of an
 >     algorithm which really needs this feature.
 >   - Adjacency iterators are basically the same as incidence iterators
 >     except that they directly access the corresponding node. That is,
 >     an adjacency iterator 'ait' can be implemented in terms of an
 >     incidence iterator 'iit', ie. basically 'operator*()' for 'ait'
 > does
 >     this: 'return target(*iit, g)'. Of course, for specific graphs
 >     there can be better implementations (eg. an implementation which
 >     does not require a reference to the graph object).

I vote for the second option for now, just because it is easier to
implement. If this causes serious problems down the road it can
be changed.

 >   
 > - A minor nit making no semantic difference: Since the incidence
 >   iterator is likely to iterate over the outgoing edges for a node,
 >   it might be counterintuitive to call it "InIt" although I can see
 >   the logic of the name :-)

Ok, i've changed it to "IncIt", though if you can think of something
better I'm all ears.

 > 
 > - The valid expression should include the following operations:
 > 
 >     expression      type  semantic
 >     *ait            V         obtain a vertex descriptor from an
 >                               adjacency iterator
 >     *iit            E         obtain an edge descriptor from an
 >                               incidence iterator
 >     *vit            V         obtain a vertex descriptor from a
 >                               vertex iterator
 >     *eit            E         obtain an edge descriptor from an
 >                               edge iterator

This seems a bit redundant since these requirements are stated in
InputIterator. I've added specific requirements for the value types of
the iterators.

 > - What is the "head" or "source" vertex of a graph? Where is it
 >   used?

I was thinking about a tree representation where there is no
vertices backbone nor a list of edges. Perhaps "root" would
be a better name?

 > 
 > A major issue is how to document and determine at compile time
 > requirements for graphs. My preference would go a different approach
 > especially with respect to orthogonal requirements: There are
 > application
 > where the list of all edges are required, applications where the list
 > of
 > all nodes are required, as well as applications where neither or both
 > are required. A graph supporting these featues just lists them in its
 > traits, a graph not supporting them does nothing, in particular does
 > not provide typedefs for the corresponding types: If they are accessed
 > by an algorithm it is an error anyway.

Yes, this is a big issue. I like your ideas so far.  Perhaps it would
be beneficial to start a "catalogue" of algorithms, listing the
requirements and the places were there is a poly-algorithm based
on different requirements (where one would need to dispatch).
I'll go through the GGCL algorithms...

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