[boost] an interface for graph algorithms

From: jsiek_at_[hidden]
Date: 1999-12-02 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 adjacency-list and
adjacency-matrix classes of implementation, but also including just an
iterator-range of edges, or even a solely pointer-based 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 warmed-over 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 non-member function. However, I felt that the benefits of
ease-of-use with RandomAccessIterators more important. Here are some
examples of GraphDecorator's being used:

c = color[v];

weight[e] = w;

Valid Expressions          Description
--------------------       -------------------------
<decorator-name> [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 call-backs 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: [phone]
 and                         cell phone: [phone]
 C++ Library & Compiler Group       fax: [phone]
 SGI                                www: http://www.lsc.nd.edu/~jsiek/
----------------------------------------------------------------------