Soon after the Standard Template Library was released, work began at the LSC to apply generic programming to scientific computing. The Matrix Template Library (Jeremy Siek's masters thesis) 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.
Graph algorithms play an important role in sparse matrix computations, so the LSC had a need for a good graph library. However, none of the available graph libraries (LEDA, GTL, Stanford GraphBase) were written using the generic programming style of the STL, and hence did not fulfill the flexibility and high-performance requirements of the LSC. Others were also expressing interest in a generic C++ graph library. During a meeting with Bjarne Stroustrup we were introduced to several people at AT\&T who needed such a library. There had also been earlier work in the area of generic graph algorithms, including some codes written by Alexander Stepanov, and Dietmar Kühl's masters thesis.
With this in mind, and motivated by homework assignments in his algorithms class, Jeremy began prototyping an interface and some graph classes in the spring on 1998. Lie-Quan Lee then developed the first version of GGCL, which became his masters thesis project.
The following year, Jeremy went to work for SGI with Alexander Stepanov and Matt Austern. During this time Alex's disjoint-sets based connected components algorithm was added to GGCL, and Jeremy began working on the concept documentation for GGCL similar to Matt's STL documentation.
While working at SGI, Jeremy heard about Boost and was excited to find a group of people interested in creating high-quality C++ libraries. At boost there were several people interested in generic graph algorithms, most notably Dietmar Kühl. Some discussions about generic interfaces for graph structures resulted in the a revision of GGCL which closely resembles the current Boost Graph Library interface.
On September 4, 2000 GGCL passed the Boost formal review and became the Boost Graph Library (BGL). The first release of BGL was September 27, 2000.
boost_graph rather than bgl-viz.read_graphviz now has a new, Spirit-based parser that works for all graph types and supports arbitrary properties on the graph, from Ron Garcia. The old, Bison-based GraphViz reader has been deprecated and will be removed in a future Boost release.write_graphviz now
supports output of dynamic properties (as read in through the
new read_graphviz).get_property now refers to the
subgraph property, not the root graph's property.| 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) |