The Boost Graph Library (BGL)

Production-ready graph algorithms for modern C++

The BGL is a header-only library included with Boost. Get it from:

GitHub repository (development and contributions)
Official Boost releases (stable distributions)

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. Consequently, these abstractions must also be represented in computer programs. Compared to other graph libraries, the BGL takes a fundamentally different approach. Rather than forcing your data into a prescribed graph structure, BGL algorithms work directly with your existing representations, from simple std::vector<std::vector<int>> adjacency lists to sophisticated custom pointer-based graphs.

Key advantages:

You can choose the optimal graph representation for your problem (dense graphs use matrices, sparse graphs use lists, etc.)
Templated algorithms automatically specialize to your particular structure (no abstraction cost)
You can also use BGL algorithms with your own private data structures (no conversion overhead)

The trade-off is explicitness, that can feel like verbosity: because BGL doesn't make assumptions about how your graph stores edges, you specify structure through template parameters and access data through property maps.

Quick example: Dijkstra's shortest path in modern C++

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <vector>
#include <cassert>

// specify structure through template parameters
struct Edge { int weight; };
using SwissArmyGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, Edge>;

int main() {
    SwissArmyGraph g(5);
    add_edge(0, 1, Edge{.weight = 7}, g);
    add_edge(0, 2, Edge{.weight = 9}, g);
    add_edge(1, 3, Edge{.weight = 10}, g);
    add_edge(2, 3, Edge{.weight = 2}, g);
    
    // specify data access through property maps
    std::vector<int> distances(num_vertices(g));
    auto dist_map = boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, g));    
    auto weight_map_param = boost::weight_map(get(&Edge::weight, g));
    auto params = weight_map_param.distance_map(dist_map);

    dijkstra_shortest_paths(g, 0, params);
    assert(distances[3] == 11 && "Shortest path 0→2→3");
}

See on Compiler Explorer →

Comparison to other Graph Libraries

	NetworkX	igraph	BGL
Language	Python	C (with Python/R bindings)	C++
Graph representation	Fixed (dict-based)	Fixed (internal C struct)	Flexible (templates adapt to your structure)
Runtime overhead	Interpreted Python	Data conversion to/from igraph format	Zero-cost abstraction (inlined templates)
Algorithm coverage	Extensive (~220-300 algorithms)	Comprehensive (~120 algorithms)	Core set (85 algorithms, extensible)
Use with existing data	Must convert to NetworkX graph	Must copy into igraph object	Works directly (external adaptation)
Learning curve	Easy	Moderate	Steep (C++ templates & concepts)

When to use each:

NetworkX: Rapid prototyping, interactive analysis, extensive algorithm library, ease of use over performance
igraph: Fast execution in Python/R workflows, willing to convert data, need compiled performance without C++ complexity
BGL: Performance-critical C++ systems, existing graph data structures, compile-time specialization, or when zero abstraction cost is essential

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)