The Boost Graph Library (BGL) is a collection of algorithms and data structures for solving graph problems. Although inventing graph algorithms is typically the domain of theoreticians, you can find applications of graph algorithms in many programming tasks, such as Internet packet routing, software build systems, Web search engines, molecular biology, and automated road-trip planning. What makes the BGL different from other graph libraries is that it was implemented using the same generic programming principles that made the Standard Template Library (STL) so powerful. In particular, the flexibility provided by the generic programming approach makes it much easier to apply the BGL algorithms in a wide variety of real-world situations.
This past December, I co-authored the book The Boost Graph Library (Addison Wesley Longman, 2002), which shows how to use the BGL to solve real-world programming problems, such as internet packet routing, and some fun problems as well, such as computing an actor's "Kevin Bacon number" and computing a knight's tour on a chessboard. In this article, I give a short introduction to the BGL and walk through an example of using the BGL to implements parts of a make-like file-dependency tracking system. But first, the "Boost" in the name of the BGL warrants some explanation.
What Is Boost?
Boost is an Internet community dedicated to building and reviewing C++ libraries. The initial members of Boost were C++ Standards Committee members who wanted to create a forum for developing libraries that might some day become part of the C++ Standard. Since then, Boost has grown to more than 2,000 members. Libraries that pass the Boost review process become part of the Boost Library Collection, which currently includes more than 30 libraries. This collection is not staticnew libraries are continually being added to Boost, and Boost libraries are often updated with improvements and extensions. The Graph Library (formerly known as the Generic Graph Component Library) was accepted into Boost on September 4, 2000.