...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. Consequently, these abstractions must also be represented in computer programs. A standardized generic interface for traversing graphs is of utmost importance to encourage reuse of graph algorithms and data structures. Part of the Boost Graph Library is an interface for how the structure of a graph can be accessed using a generic interface that hides the details of the graph data structure implementation. This is an ``open'' interface in the sense that any graph library that implements this interface will be interoperable with the BGL generic algorithms and with other algorithms that also use this interface. BGL provides some general purpose graph classes that conform to this interface, but they are not meant to be the ``only'' graph classes; there certainly will be other graph classes better for certain situations. We believe that the main contribution of the BGL is the formulation of this interface.

The BGL graph interface and graph components are *generic* in the
same sense as the the Standard Template Library (STL) [2].
In the following sections we review the role that generic programming
plays in the STL and compare that to how we applied generic
programming in the context of graphs.

Of course, if you are already are familiar with generic programming, please dive right in! Here's the Table of Contents.

The source for the BGL is available as part of the Boost distribution which you can download from here.

There are three ways in which the STL is generic.

First, each algorithm is written in a data-structure neutral way,
allowing a single template function to operate on many different
classes of containers. The concept of an iterator is the key
ingredient in this decoupling of algorithms and data-structures. The
impact of this technique is a reduction in the STL's code size from
*O(M*N)* to *O(M+N)*, where *M* is the number of
algorithms and *N* is the number of containers. Considering a
situation of 20 algorithms and 5 data-structures, this would be the
difference between writing 100 functions versus only 25 functions! And
the differences continues to grow faster and faster as the number of
algorithms and data-structures increase.

The second way STL is generic is that its algorithms and containers are extensible. The user can adapt and customize the STL through the use of function objects. This flexibility is what makes STL such a great tool for solving real-world problems. Each programming problem brings its own set of entities and interactions that must be modeled. Function objects provide a mechanism for extending the STL to handle the specifics of each problem domain.

The third way that STL is generic is that its containers are
parameterized on the element type. Though hugely important, this is
perhaps the least ``interesting'' way in which STL is generic.
Generic programming is often summarized by a brief description of
parameterized lists such as `std::list<T>`. This hardly scratches
the surface!

Like the STL, there are three ways in which the BGL is generic.

First, the graph algorithms of BGL are written to an interface that abstracts away the details of the particular graph data-structure. Like the STL, the BGL uses iterators to define the interface for data-structure traversal. There are three distinct graph traversal patterns: traversal of all vertices in the graph, through all of the edges, and along the adjacency structure of the graph (from a vertex to each of its neighbors). There are separate iterators for each pattern of traversal.

This generic interface allows template functions such as `breadth_first_search()`
to work on a large variety of graph data-structures, from graphs
implemented with pointer-linked nodes to graphs encoded in
arrays. This flexibility is especially important in the domain of
graphs. Graph data-structures are often custom-made for a particular
application. Traditionally, if a programmer wants to reuse an
algorithm implementation they must convert/copy their graph data into
the graph library's prescribed graph structure. This is the case with
libraries such as LEDA, GTL, Stanford GraphBase, and especially true
of graph algorithms written in Fortran. This severely limits the reuse
of their graph algorithms.

In contrast, custom-made (or even legacy) graph structures can be used
as-is with the generic graph algorithms of BGL using *external
adaptation* (see Section How to
Convert Existing Graphs to BGL). External adaptation wraps a new
interface around a data-structure without copying and without placing
the data inside adaptor objects. The BGL interface was carefully
designed to make this adaptation easy. To demonstrate this, we have
built interfacing code for using LEDA graphs, Stanford GraphBase
graphs, and even Fortran-style arrays in BGL graph algorithms.

Second, the graph algorithms of BGL are extensible. BGL introduces the
notion of a *visitor* which is just a function object with
multiple methods. In graph algorithms there are often several key
``event points'' at which it is useful to insert user-defined
operations. The visitor object has a different method that is invoked
at each event point. The particular event points and corresponding
visitor methods depend on the particular algorithm. They often
include methods like `start_vertex()`,
`discover_vertex()`, `examine_edge()`,
`tree_edge()` and `finish_vertex()`.

The third way that BGL is generic is analogous to the parameterization
of the element-type in STL containers, though again the story is a bit
more complicated for graphs. We need to associate values with both the
vertices and the edges of the graph (we will call an associated value
a property). In addition, it will often be necessary to associate
multiple properties with each vertex and edge, which is what we mean
by multi-parameterization. Similar to how the `std::list<T>`
class has the parameter `T` for its element type, BGL graph
classes have template parameters for vertex and edge ``properties''. A
property specifies the parameterized type of the property and also assigns
an identifying tag to the property, which is used to distinguish
between the multiple properties. The property value attached to a
particular vertex or edge can be obtained via a *property
map*, of which there is one for each property.

Traditional graph libraries and graph structures fall down when it comes to the parameterization of graph properties. This is one of the primary reasons that graph data-structures must be custom-built for applications. The parameterization of properties in the BGL graph classes makes them well suited for re-use.

The BGL algorithms consist of a core set of algorithm *patterns*
(implemented as generic algorithms) and a larger set of graph
algorithms. The core algorithm patterns are

- Breadth First Search
- Depth First Search
- Uniform Cost Search

The algorithm patterns by themselves do not compute any meaningful quantities over graphs, they are merely building blocks for constructing graph algorithms. The graph algorithms in BGL currently include

- Dijkstra's Shortest Paths
- Bellman-Ford Shortest Paths
- Johnson's All-Pairs Shortest Paths
- Kruskal's Minimum Spanning Tree
- Prim's Minimum Spanning Tree
- Connected Components
- Strongly Connected Components
- Dynamic Connected Components (using Disjoint Sets)
- Topological Sort
- Transpose
- Reverse Cuthill Mckee Ordering
- Smallest Last Vertex Ordering
- Sequential Vertex Coloring

BGL currently provides two graph classes that implement a generalized adjacency list and an edge list adaptor.

`adjacency_list``adjacency_matrix``edge_list`

The `adjacency_list` class is the general purpose ``swiss army
knife'' of graph classes. It is highly parameterized so that it can be
optimized for different situations: the graph is directed or
undirected, allow or disallow parallel edges, efficient access to just
the out-edges or also to the in-edges, fast vertex insertion and
removal at the cost of extra space overhead, etc.

The `edge_list` class is an adaptor that takes any kind of edge
iterator and implements an EdgeListGraph.

Copyright © 2000-2001 |
Jeremy Siek,
Indiana University (jsiek@osl.iu.edu) Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Andrew Lumsdaine, Indiana University (lums@osl.iu.edu) |