
Boost : 
From: jsiek_at_[hidden]
Date: 19991202 03:49:46
This is not a proposal for a library. It is a proposal for an
interface (or set of "concepts" in the SGI STL meaning of the term).
This is the interface for the graph library described in "The Generic
Graph Component Library", OOPSLA'99 (though the interface has evolved
since the paper was submitted). The library itself would not be
acceptable for boost due to the copyright. However, the copyright does
not cover the interface (would that even be possible?). In many ways,
the interface is more important that the library itself. The interface
is designed to leave open the implementation of many different graph
representations, including the typical adjacencylist and
adjacencymatrix classes of implementation, but also including just an
iteratorrange of edges, or even a solely pointerbased graph
representation. The interface is also designed to make graph
algorithm highly reusable, similar to the way iterators and
functors make STL reusable.
The first two concepts are pretty straightforward, Vertex and Edge. A
traits class is defined for each concept for access to associated
types, and the operations are expressed as global functions. I choose
global functions because it is the most extensible access method, and
leaves open the most possibilities for reuse, ie. the objects do not
have to be of class type, and if they are imported from a third party
(or if they are part of a legacy code) it is easy to add the global
functions after the fact.
concept Vertex
==============
V is a type that models Vertex
u is an object of type V
v is an object of type V
Valid Expressions Description
 
vertex_traits<V>::edgelist_type A type that models ContainerRef*
vertex_traits<V>::vertexlist_type A type that models ContainerRef
out_edges(v) Returns on object of edgelist_type
in_edges(v)* Returns on object of edgelist_type
adj(v) Returns on object of vertexlist_type
u == v Compare two vertices for equality
u != v Compare two vertices for inequality
* in_edges() is optional since most graphs don't provide efficient access
* for a description of ContainerRef see below
The adj() function is somewhat redundant, since the adjacent edges can
be obtained through the out_edges() method, however I figured it might
be a nice convenience.
The Vertex concept refines Assignable, DefaultConstructible, and
EqualityComparable.
The equality test checks to see if the two vertex objects refer to the
same conceptual vertex in the graph. It assumed that copies of a
vertex object will yield true when compared for equality to the
original vertex.
concept VertexWithID
====================
Often times a "unique ID" is associated with each vertex. This
can be accessed with the index() function.
v is a VertexWithID
Valid Expressions Description
 
index(v) Returns some Integral type
concept ContainerRef
====================
Perhaps I need a better name for this concept. It is a stripped down STL
Container. A ContainerRef object does not "own" the underlying data
the way an STL Container does. It should be implementable by a couple
of iterators. Currently I use the normal STL c.begin(), c.end() syntax
but it might be beneficial to move to the begin(c), end(c) syntax
of the boost arrays.
concept Edge
============
This is really not much more than a pair warmedover to fit the graph
abstraction terminology. For undirected edges we still use the
source(e) and target(e) functions, but they lose their normal
connotations.
E is a type that models Edge
e is an object of type E
Valid Expressions Description
 
edge_traits<E>::vertex_type A type that models Vertex
source(e) Returns an object of vertex_type
target(e) Returns an object of vertex_type
concept GraphDecorator
======================
There is always a need to associate properties with vertices and edges
such as color, weight, distance, etc. Generic graph algorithms need a
consistent syntax for accessing these properties. I propose
operator[]. This is consistent with the notation in several textbooks,
and it is also compatible with the C++ builtin array types, or any
RandomAccessIterator. Of course, there are lots of ways that property
access can be implemented, but this concept just requires that the
operator[] be the syntax used. One downside of the operator[] is that
it must be a member function, which makes this less extensible than
using a nonmember function. However, I felt that the benefits of
easeofuse with RandomAccessIterators more important. Here are some
examples of GraphDecorator's being used:
c = color[v];
weight[e] = w;
Valid Expressions Description
 
<decoratorname> [i] i is an Index (see below)
concept Index
=============
This is anything that can be used as the "index" for some
GraphDecorator. This is a bit subtle, sort of a mutually recursive
definition since it is really dependent on the particular
GraphDecorator type. Often times Vertex type and Edge types will
model Index.
concept EdgeI
=============
This is short for "an Edge where the source and target are only
guaranteed to be usable as indices for some decorator", i.e., the
source and target do not have to satisfy the full Vertex requirements.
The situation where this concept is used is when one wants to use
integers to represent vertices, std::pair to represent edges, and some
RandomAccessIterators to represent the decorators. Algorithms that
deal with this kind of representation traverse a collection of edges,
instead of traversing along the adjacency structure.
concept GraphVisitor
====================
The STL algorithms use functors to parameterize generic algorithms.
Similarly, one would want to supply callbacks in order to
parameterize generic graph algorithms. We identified several common
"events" at which basic graph algorithms such as BFS and DFS should be
parameterized, an made each of these a member function of the
GraphVisitor.
visitor is a GraphVisitor
v is a Vertex
e is an Edge
Valid Expressions Description
 
visitor.initialize(v) Called on each vertex before start of algorithm
visitor.start(v) Invoked on the "source" or "starting" vertex
visitor.discover(v) Called when vertex is first touched by algorithm
visitor.finish(v) Called after all adjacent have been discovered
visitor.process(e) Called when an edge is encountered
Here's a quick example of what it looks like to write a graph
algorithm using this interface. This algorithm is pretty much straight
from the CLR. To create a truly generic BFS one would want to abstract
out a bunch more stuff, like the queue type and add in a GraphVisitor
to replace the operations on the various decorators (color, distance,
etc.). One would also want to use some kind of traits class to access
the color values.
template <class VertexIterator, class Color,
class Distance, class Predecessor>
void textbook_BFS(VertexIterator first, VertexIterator last,
Color color, Distance d, Predecessor p)
{
typedef typename std::iterator_traits<VertexIterator>::value_type Vertex;
typename vertex_traits<Vertex>::edgelist_type::iterator ei;
Vertex s = *first;
//initialization
for (; first != last, ++first) {
color[*first] = WHITE; // perhaps use color_traits instead
d[*first] = INF;
}
//starting from vertex s
color[s] = GRAY;
d[s] = 0;
std::queue<Vertex> Q;
Q.push(s);
//main algorithm
while (! Q.empty()) {
Vertex u = Q.front();
for (ei = out_edges(u).begin(); ei != out_edges(u).end(); ++ei) {
Vertex v = target(*ei);
if (color[v] == WHITE) {
color[v] = GRAY;
d[v] = d[u] + 1;
p[v] = u;
}
}
Q.pop();
color[u] = BLACK;
}
}
You are welcome to browse the web site describing the Generic Graph
Component Library (I know, its a horrible name, but GTL was already
taken).
http://www.lsc.nd.edu/research/ggcl
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