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
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>
#include <limits>
#include <vector>
struct City {};
struct Road { int cost; };
using namespace boost;
using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
int main() {
Graph g(4);
add_edge(0, 1, Road{1}, g);
add_edge(1, 2, Road{2}, g);
add_edge(0, 2, Road{10}, g);
add_edge(2, 3, Road{1}, g);
// Storage: you control allocation, lifetime, and container type
std::vector<Vertex> storage_pred(num_vertices(g));
std::vector<int> storage_dist(num_vertices(g));
// Property maps: lightweight views into the storage
auto index_map = get(vertex_index, g);
auto costs_map = get(&Road::cost, g);
auto predecessor_map = make_iterator_property_map(storage_pred.begin(), index_map);
auto distance_map = make_iterator_property_map(storage_dist.begin(), index_map);
dijkstra_shortest_paths(g, vertex(0, g),
predecessor_map, distance_map,
costs_map, index_map,
std::less<int>(), std::plus<int>(),
std::numeric_limits<int>::max(), 0,
dijkstra_visitor<null_visitor>());
for (auto v : make_iterator_range(vertices(g)))
std::cout << "distance to " << v << " = " << storage_dist[v] << "\n";
}distance to 0 = 0
distance to 1 = 1
distance to 2 = 3
distance to 3 = 4Get 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.