BoostC++ Libraries
...one of the most highly regarded and expertly designed C++ library projects in the world.
—Herb Sutter andAndrei Alexandrescu,C++ Coding Standards
BoostC++ Libraries...one of the most highly regarded and expertly designed C++ library projects in the world.
—Herb Sutter andAndrei Alexandrescu,C++ Coding Standards
Graphs are mathematical abstractions that are useful for solving manytypes of problems in computer science. Consequently, theseabstractions must also be represented in computer programs. Astandardized generic interface for traversing graphs is of utmostimportance to encourage reuse of graph algorithms and data structures.Part of the Boost Graph Library is a generic interface that allowsaccess to a graph's structure, but hides the details of theimplementation. This is an “open” interface in the sense that anygraph library that implements this interface will be interoperablewith the BGL generic algorithms and with other algorithms that alsouse this interface. The BGL provides some general purpose graph classesthat conform to this interface, but they are not meant to be the“only” graph classes; there certainly will be other graph classesthat are better for certain situations. We believe that the maincontribution of the The BGL is the formulation of this interface.
The BGL graph interface and graph components aregeneric, in thesame sense as the Standard Template Library (STL) [2].In the following sections, we review the role that generic programmingplays in the STL and compare that to how we applied genericprogramming in the context of graphs.
Of course, if you are already familiar with generic programming,please dive right in! Here's theTable of Contents. For distributed-memoryparallelism, you can also look at theParallel BGL.
The source for the BGL is available as part of the Boost distribution,which you candownload from here.
DON'T! The Boost Graph Library is a header-only library anddoes not need to be built to be used. The only exceptions are theGraphViz input parser and theGraphML parser.
When compiling programs that use the BGL,be sure to compilewith optimization. For instance, select “Release” mode withMicrosoft Visual C++ or supply the flag-O2 or-O3to GCC.
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 differentclasses of containers. The concept of an iterator is the keyingredient in this decoupling of algorithms and data-structures. Theimpact of this technique is a reduction in the STL's code size fromO(M*N) toO(M+N), whereM is the number ofalgorithms andN is the number of containers. Considering asituation of 20 algorithms and 5 data-structures, this would be thedifference between writing 100 functions versus only 25 functions! Andthe differences continues to grow faster and faster as the number ofalgorithms and data-structures increase.
The second way that STL is generic is that its algorithms and containersare extensible. The user can adapt and customize the STL through theuse of function objects. This flexibility is what makes STL such agreat tool for solving real-world problems. Each programming problembrings its own set of entities and interactions that must bemodeled. Function objects provide a mechanism for extending the STL tohandle the specifics of each problem domain.
The third way that STL is generic is that its containers areparameterized on the element type. Though hugely important, this isperhaps the least “interesting” way in which STL is generic.Generic programming is often summarized by a brief description ofparameterized lists such asstd::list<T>. This hardly scratchesthe surface!
Like the STL, there are three ways in which the BGL is generic.
First, the graph algorithms of the BGL are written to an interface thatabstracts away the details of the particular graph data-structure.Like the STL, the BGL uses iterators to define the interface fordata-structure traversal. There are three distinct graph traversalpatterns: traversal of all vertices in the graph, through all of theedges, and along the adjacency structure of the graph (from a vertexto each of its neighbors). There are separate iterators for eachpattern of traversal.
This generic interface allows template functions such asbreadth_first_search()to work on a large variety of graph data-structures, from graphsimplemented with pointer-linked nodes to graphs encoded inarrays. This flexibility is especially important in the domain ofgraphs. Graph data-structures are often custom-made for a particularapplication. Traditionally, if programmers want to reuse analgorithm implementation they must convert/copy their graph data intothe graph library's prescribed graph structure. This is the case withlibraries such as LEDA, GTL, Stanford GraphBase; it is especially trueof graph algorithms written in Fortran. This severely limits the reuseof their graph algorithms.
In contrast, custom-made (or even legacy) graph structures can be usedas-is with the generic graph algorithms of the BGL, usingexternaladaptation (see SectionHow toConvert Existing Graphs to the BGL). External adaptation wraps a newinterface around a data-structure without copying and without placingthe data inside adaptor objects. The BGL interface was carefullydesigned to make this adaptation easy. To demonstrate this, we havebuilt interfacing code for using a variety of graph structures (LEDAgraphs, Stanford GraphBase graphs, and even Fortran-style arrays) inBGL graph algorithms.
Second, the graph algorithms of the BGL are extensible. The BGL introduces thenotion of avisitor, which is just a function object withmultiple methods. In graph algorithms, there are often several key“event points” at which it is useful to insert user-definedoperations. The visitor object has a different method that is invokedat each event point. The particular event points and correspondingvisitor methods depend on the particular algorithm. They ofteninclude methods likestart_vertex(),discover_vertex(),examine_edge(),tree_edge(), andfinish_vertex().
The third way that the BGL is generic is analogous to the parameterizationof the element-type in STL containers, though again the story is a bitmore 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 associatemultiple properties with each vertex and edge; this is what we meanby multi-parameterization.The STLstd::list<T> class has a parameterTfor its element type. Similarly, BGL graph classes have templateparameters for vertex and edge “properties”. Aproperty specifies the parameterized type of the property and also assignsan identifying tag to the property. This tag is used to distinguishbetween the multiple properties which an edge or vertex may have. Aproperty value that is attached to aparticular vertex or edge can be obtained via apropertymap. There is a separate property map for each property.
Traditional graph libraries and graph structures fall down when itcomes to the parameterization of graph properties. This is one of theprimary reasons that graph data-structures must be custom-built forapplications. The parameterization of properties in the BGL graphclasses makes them well suited for re-use.
The BGL algorithms consist of a core set of algorithmpatterns(implemented as generic algorithms) and a larger set of graphalgorithms. The core algorithm patterns are
By themselves, the algorithm patterns do not compute any meaningfulquantities over graphs; they are merely building blocks forconstructing graph algorithms. The graph algorithms in the BGL currentlyinclude
The BGL currently provides two graph classes and an edge list adaptor:
Theadjacency_list class is the general purpose “swiss armyknife” of graph classes. It is highly parameterized so that it can beoptimized for different situations: the graph is directed orundirected, allow or disallow parallel edges, efficient access to justthe out-edges or also to the in-edges, fast vertex insertion andremoval at the cost of extra space overhead, etc.
Theadjacency_matrix class stores edges in a|V| x |V|matrix (where|V| is the number of vertices). The elements ofthis matrix represent edges in the graph. Adjacency matrixrepresentations are especially suitable for very dense graphs, i.e.,those where the number of edges approaches|V|2.
Theedge_list class is an adaptor that takes any kind of edgeiterator and implements anEdge List Graph.
| 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) |