Boost logo

Boost :

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



 Jeremy Siek
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (650) 933-8724
 and cell phone: (415) 377-5814
 C++ Library & Compiler Group fax: (650) 932-0127
 SGI www:

Boost list run by bdawes at, gregod at, cpdaniel at, john at