The Boost Graph Library (BGL)
A C++ library of graph algorithms and data structures, generic enough to work on your existing graph representation without conversion.
Features
-
Multiple representations for your graph data, each with different performance trade-offs
-
Generic algorithms that work across any graph representation, with fine control on allocations
-
Extensible algorithms: inject your own logic at key points during traversal using visitor hooks
Example
The example below brings together the three ideas that run through the library.
You choose how the graph is stored: this one uses an adjacency_list, but adjacency_matrix or compressed_sparse_row_graph would run the same algorithm.
The results stay in your own containers, which the algorithm reaches through property maps that separate where data lives from how it is read.
And you hook into the traversal with a visitor that reacts to events as the breadth-first search expands, recording each vertex’s distance and predecessor along the way.
Following the predecessor map back from the target then gives the shortest path.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Vertex = Graph::vertex_descriptor;
// Undirected graph given as a list of (source, target) vertex-index pairs
std::vector<std::pair<int,int>> edges = {
{0,1},{0,3},{0,18},{1,2},{1,19},{2,3},{2,8},{3,4},{4,5},{4,8},
{5,6},{5,18},{6,7},{6,12},{7,8},{7,11},{8,9},{9,10},{9,19},{10,11},
{10,15},{11,12},{11,14},{12,13},{13,14},{13,17},{14,15},{14,17},
{15,16},{16,17},
};
// Build the graph from the edge list
constexpr int num_vertices = 20;
Graph g(edges.begin(), edges.end(), num_vertices);
const Vertex source = 9;
const Vertex target = 13;
// External storage for the results, one slot per vertex
std::vector<int> distance_storage(boost::num_vertices(g));
std::vector<Vertex> predecessor_storage(boost::num_vertices(g));
// Three property maps:
// vertex -> its index (provided by the graph type)
auto vertex_index_map = boost::get(boost::vertex_index, g);
// vertex -> BFS distance from the source (wraps distance_storage)
auto distance = boost::make_iterator_property_map(distance_storage.begin(), vertex_index_map);
// vertex -> its parent in the BFS tree (wraps predecessor_storage)
auto predecessor = boost::make_iterator_property_map(predecessor_storage.begin(), vertex_index_map);
boost::breadth_first_search(g, source,
boost::visitor(boost::make_bfs_visitor(std::make_pair(
boost::record_distances(distance, boost::on_tree_edge()),
boost::record_predecessors(predecessor, boost::on_tree_edge())))));
// Walk back from target to source through the predecessor map
for (auto v = target; v != source; v = boost::get(predecessor, v))
std::cout << v << ' ';
std::cout << source << '\n';
}13 12 11 10 9Get started
Representing your Graph.
BGL provides several graph representations (adjacency_list, adjacency_matrix,
compressed_sparse_row_graph), each with different trade-offs in memory layout,
insertion speed, and traversal performance. Choosing the right one is the first
decision you make.
Understanding Property maps. Algorithms need data attached to vertices and edges: weights, colors, distances. Property maps decouple how that data is stored (a vector, a map, a struct member) from how algorithms access it. Understanding this mechanism is essential for using any BGL algorithm beyond trivial examples.
Injecting Visitors. Visitors are what make BGL algorithms adaptable to your problem without modifying library code. Rather than writing a new algorithm from scratch, you inject custom logic into an existing one at specific event points (vertex discovered, edge relaxed, etc.).
Requirements
-
C++14 or later
-
Boost headers: BGL is part of the Boost distribution and requires no separate install. It is header-only, so no build step is needed. The only exceptions are the GraphViz parser and the GraphML parser.
-
Compile with
-O2or-O3. Template-heavy code is significantly slower in debug builds, to the point of being misleading about real performance.
Help and feedback
Bug reports and confirmed problems. Search before opening a new one. |
|
Questions, design ideas, and general conversation about the library. |
|
General Boost development list. Use the |
|
Real-time chat. Request an invite, then join the |
Authors
The Boost Graph Library was originally created by Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine, who also wrote its reference text, The Boost Graph Library: User Guide and Reference Manual. Many other contributors have extended the library since.
How to cite
If you use the Boost Graph Library in academic work, please cite the reference book:
Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine.
The Boost Graph Library: User Guide and Reference Manual.
Addison-Wesley Professional, 2002.@book{siek2002boost,
title = {The Boost Graph Library: User Guide and Reference Manual},
author = {Siek, Jeremy G. and Lee, Lie-Quan and Lumsdaine, Andrew},
publisher = {Addison-Wesley Professional},
year = {2002}
}