The first C++ library to apply the principles of generic programming to the construction of the advanced data structures and algorithms used in graph computations. Offers the key to unlocking the power of the BGL for the C++ programmer looking to extend the reach of generic programming beyond the Standard Template Library. Softcover. CD-ROM included.

Jeremy G. Siek is a leading expert in C++ and generic programming and is currently pursuing his doctoral degree at Indiana University. He is interested in the design of programming languages that support generic programming and in high performance libraries. Jeremy is a member of the ISO C++ Standards Committee and is an active member of the Boost C++ Library Group, where he has contributed several libraries in addition to the BGL.

Lie-Quan (Rich) Lee developed the first version of the BGL. A doctoral candidate at the University of Notre Dame, his research interests include generic programming, scientific component libraries, and high performance computing. Rich is an active member of the Boost C++ Library Group.

Andrew Lumsdaine is an Associate Professor in the Computer Science Department and Associate Director of the Open Systems Laboratory at Indiana University. In addition to generic programming and software engineering, his research program includes projects in computational science and engineering, parallel and distributed computing, mathematical software, and numerical analysis. Andrew is a member of the ISO C++ Standards Committee and the Boost C++ Library Group.

0201729148AB11212001

The graph abstraction is a powerful problem-solving tool used to describe relationships between discrete objects. Many practical problems can be modeled in their essential form by graphs. Such problems appear in many domains: Internet packet routing, telephone network design, software build systems, Web search engines, molecular biology, automated road-trip planning, scientific computing, and so on. The power of the graph abstraction arises from the fact that the solution to a graph-theoretic problem can be used to solve problems in a wide variety of domains. For example, the problem of solving a maze and the problem of finding groups of Web pages that are mutually reachable can both be solved using depth-first search, an important concept from graph theory. By concentrating on the essence of these problemsthe graph model describing discrete objects and the relationships between themgraph theoreticians have created solutions to not just a handful of particular problems, but to entire families of problems. Now a question arises. If graph theory is generally and broadly applicable to arbitrary problem domains, should not the software that implements graph algorithms be just as broadly applicable? Graph theory would seem to be an ideal area for software reuse. However, up until now the potential for reuse has been far from realized. Graph problems do not typically occur in a pure graph-theoretic form, but rather are embedded in larger domain-specific problems. As a result, the data to be modeled as a graph are often not explicitly represented as a graph but are instead encoded in some application-specific data structure. Even in the case where the application data are explicitly represented as a graph, the particular graph representation chosen by the programmer might not match the representation expected by a library that the programmer wants to use. Moreover, different applications may place different time and space requirements on the graph data structure. This implies a serious problem for the graph library writer who wants to provide reusable software, for it is impossible to anticipate every possible data structure that might be needed and to write a different version of the graph algorithm specifically for each one. The current state of affairs is that graph algorithms are written in terms of whatever data structure is most convenient for the algorithm and users must convert their data structures to that format in order to use the algorithm. This is an inefficient undertaking, consuming programmer time and computational resources. Often, the cost is perceived not to be worthwhile, and the programmer instead chooses to rewrite the algorithm in terms of his or her own data structure. This approach is also time consuming and error prone, and will tend to lead to sub-optimal solutions since the application programmer may not be a graph algorithms expert. Generic Programming The Standard Template Library (STL) was introduced in 1994 and was adopted shortly thereafter into the C++ Standard. The STL was a library of interchangeable components for solving many fundamental problems on sequences of elements. What set the STL apart from libraries that came before it was that each STL algorithm could work with a wide variety of sequential datastructures: linked-lists, arrays, sets, and so on. The iterator abstraction provided an interface between containers and algorithms and the C++ template mechanism provided the needed flexibility to allow implementation without loss of efficiency. Each algorithm in the STL is a function template parameterized by the types of iterators upon which it operates. Any iterator that satisfies a minimal set of requirements can be used regardless of the data structure traversed by the iterator. The systematic approach used in the STL to construct abstractions and interchangeable components is called generic programming. Generic programming lends itself well to solving the reusability problem for graph libraries. With generic programming, graph algorithms can be made much more flexible, allowing them to be easily used in a wide variety applications. Each graph algorithm is written not in terms of a specific data structure, but instead to a graph abstraction that can be easily implemented by many different data structures. Writing generic graph algorithms has the additional advantage of being more natural; the abstraction inherent in the pseudo-code description of an algorithm is retained in the generic function. The Boost Graph Library (BGL) is the first C++ graph library to apply the notions of generic programming to the construction of graph algorithms. Some BGL History The Boost Graph Library began its life as the Generic Graph Component Library (GGCL), a software project at the Lab for Scientific Computing (LSC). The LSC, under the direction of Professor Andrew Lumsdaine, was an interdisciplinary laboratory dedicated to research in algorithms, software, tools, and run-time systems for high-performance computational science and engineering.2Special emphasis was put on developing industrial-strength, high performance software using modern programming languages and techniquesmost notably, generic programming. Soon after the Standard Template Library was released, work began at the LSC to apply generic programming to scientific computing. The Matrix Template Library (MTL) was one of the first projects. Many of the lessons learned during construction of the MTL were applied to the design and implementation of the GGCL. The LSC has since evolved into the Open Systems Laboratory (OSL) http://www.osl.iu.edu.Although the name and location have changed, the research agenda remains the same. An important class of linear algebra computations in scientific computing is that of sparse matrix computations, an area where graph algorithms play an important role. As the LSC was developing the sparse matrix capabilities of the MTL, the need for high-performance reusable (and generic) graph algorithms became apparent. However, none of the graph libraries available at the time (LEDA, GTL, Stanford GraphBase) were written using the generic programming style of the MTL and the STL, and hence did not fulfill the flexibility and high-performance requirements of the LSC. Other researchers were also expressing interest in a generic C++ graph library. During a meeting with Bjarne Stroustrup, we were introduced to several individuals at AT&T who needed such a library. Other early work in the area of generic graph algorithms included some codes written by Alexander Stepanov, as well as Dietmar Kuhl's master's thesis. With this in mind, and motivated by homework assignments in his algorithms class ,Jeremy Siek began prototyping an interface and some graph classes in the spring of1998. Lie-Quan Lee then developed the first version of the GGCL, which became his master's thesis project. During the following year, the authors began collaborating with Alexander Stepanov and Matthew Austern. During this time, Stepanov's disjoint-sets-based connected components implementation was added to the GGCL, and work began on providing concept documentation for the GGCL, similar to Austern's STL documentation. During this year the authors also became aware of Boost and were excited to find an organization interested in creating high-quality, open source C++ libraries. Boost included several people interested in generic graph algorithms, most notably Dietmar Kuhl. Some discussions about generic interfaces for graph structures resulted in a revision of the GGCL that closely resembles the current Boost Graph Library interface. On September 4, 2000, the GGCL passed the Boost formal review (managed by David Abrahams) and became the Boost Graph Library. The first release of the BGL was September 27, 20