
Boost : 
From: jsiek_at_[hidden]
Date: 19991210 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 nontrivial 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 polyalgorithm 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: (650) 9338724
and cell phone: (415) 3775814
C++ Library & Compiler Group fax: (650) 9320127
SGI www: http://www.lsc.nd.edu/~jsiek/

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