Design Rationale

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 that 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!

First, the graph algorithms of the 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 programmers want 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; it is 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 the BGL, using external adaptation (see Section How to Convert Existing Graphs to the 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 a variety of graph structures (LEDA graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in BGL graph algorithms.

Second, the graph algorithms of the BGL are extensible. The BGL introduces the notion of a visitor [15], 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 the 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 (called "properties") with both the vertices and the edges of the graph. In addition, it will often be necessary to associate multiple properties with each vertex and edge; this is what we mean by multi-parameterization. The STL std::list<T> class has a parameter T for its element type. Similarly, 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, following the C++ traits technique [19]. This tag is used to distinguish between the multiple properties which an edge or vertex may have. A property value that is attached to a particular vertex or edge can be obtained via a property map. There is a separate property map 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.