Boost Graph Lib

The Boost Graph Library (BGL) is a C++ library for representing and computing over graphs, developed by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine at Indiana University around 2000-2001 and distributed as part of the Boost peer-reviewed C++ libraries. It was the first library to apply generic (template-based) programming, in the style of the C++ Standard Template Library, to graph data structures and algorithms. Rather than fixing one graph representation, the BGL defines a set of abstract graph concepts, and algorithms are written against those concepts so they run unchanged across many concrete storage schemes.

Its data model centers on interchangeable container classes. The adjacencylist template is the general-purpose "swiss army knife" graph type, parameterized over the containers used for out-edges and vertices, directedness, and attached properties; adjacencymatrix suits dense graphs; and edge_list adapts a plain sequence of edges. Vertex and edge attributes are handled through property maps, an indirection layer that decouples data from topology, while visitors, function objects invoked at defined event points such as discovering a vertex or examining an edge, let callers hook into algorithm execution without rewriting it.

The library ships a broad algorithm suite: breadth-first and depth-first search, Dijkstra and Bellman-Ford shortest paths, Kruskal and Prim minimum spanning trees, connected and strongly connected components, topological sort, and graph coloring, among others. Most of the BGL is header-only; only a few components, notably the parsers, require compilation.

In the graph-data and format-conversion ecosystem the BGL is primarily an in-memory engine rather than a converter, but it does provide file I/O: readgraphviz/writegraphviz for the format:dot GraphViz language (implemented independently of tool:graphviz, from the DOT spec) and readgraphml/writegraphml for format:graphml. This makes it a natural C++ counterpart to Python's tool:networkx or tool:igraph, and it underpins or interoperates with tools such as tool:ogdf and the newer tool:lemon in the C++ graph space.

Strengths are performance, static type safety, and composability from generic design. The trade-offs are steep: the template-heavy API has a notoriously high learning curve, compiler error messages are dense, and its format support is limited to DOT and GraphML, so broader interchange requires external tooling like tool:graphinout.