Quick Overview

Just like STL works with vectors, lists, and sets using the same algorithms, BGL works with different graph structures using the same algorithms.

What is a Graph?

A graph consists of:

A set of vertices (or nodes)
A set of edges (or arcs) that connect the vertices

A directed graph with 5 vertices, 11 edges.

Terminology for directed graphs:

Out-edges: Edges leaving a vertex. Example: {(0,1),(0,2),(0,3),(0,4)} are all out-edges of vertex 0.
In-edges: Edges entering a vertex. Example: {(0,4),(2,4),(3,4)} are all in-edges of vertex 4.

The BGL Approach

Graph algorithms are mathematically described using simple operations (accessing edges, traversing vertices) that are independent of implementation details: the data structure is abstracted away. This allows the same algorithm description to work on different graph representations.

Just like STL algorithms work on different containers, the BGL uses C++ generic programming to implement this mathematical abstraction and gives users practical benefits:

Users can choose the right structure for each problem: adjacency lists for sparse graphs, matrices for dense graphs, or custom domain-specific types, all compatible with the same algorithms
Users can integrate BGL with existing code: costly graph data conversions can be avoided, since BGL algorithms operate directly on user-defined graph representations via simple concept requirements
Users benefit from zero runtime overhead: generic code compiles into fully specialized machine code, avoiding the runtime costs associated with virtual dispatch
Users can evolve graph designs without breaking algorithms: graph structures can change as requirements evolve without requiring algorithm rewrites

BGL achieves this through an STL-like design based on iterators and concepts, extended with graph-specific abstractions: vertex iterators, edge iterators, adjacency iterators, visitors (for custom actions during traversal), and property accessors (for custom access to data attached to vertices and edges).

**Figure:** The analogy between the STL and the BGL.

Basic Graph Types

To allow users to balance memory usage, performance, and functionality, the BGL provides several graph data structures, with adjacency_list being the most commonly used, with template parameters that let users select the underlying structures to tailor the graph to their needs:

Edge storage Selectors (vecS, listS, setS): How edges are stored per vertex, affecting insertion/removal speed and parallel edge support
Vertex storage Selectors (vecS, listS, setS): How vertices are stored, affecting memory layout and descriptor stability
Directionality Selectors (directedS, undirectedS, bidirectionalS): Which traversal operations are available

While this makes the type declarations verbose, it's how BGL delivers the performance flexibility and zero-cost abstraction mentioned above. See Choosing a Graph Structure for detailed guidance on these choices.

Example

BGL's generic interface lets the same algorithm work with different graph types. This example shows how you can write an algorithm once and use it with any graph structure.

See on Compiler Explorer.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/connected_components.hpp>
#include <iostream>
#include <vector>

template<typename Graph>
auto count_components(const Graph& g) {
    auto components = std::vector<int>(num_vertices(g));
    return connected_components(g, components.data());
}

int main()
{   
    // Fast iteration, O(V+E) memory, allows parallel edges
    using ListGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;

    // Prevents parallel edges, O(V+E) memory, O(log E) edge ops  
    using SetGraph = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>;

    // Best for dense graphs, O(1) edge queries, O(V²) memory
    using MatrixGraph = boost::adjacency_matrix<boost::undirectedS>;
    
    auto g1 = ListGraph(15);
    auto g2 = SetGraph(15);
    auto g3 = MatrixGraph(15);
    
    // Component 1: triangle (0-1-2)
    add_edge(0, 1, g1); add_edge(0, 1, g2); add_edge(0, 1, g3);
    add_edge(1, 2, g1); add_edge(1, 2, g2); add_edge(1, 2, g3);
    add_edge(2, 0, g1); add_edge(2, 0, g2); add_edge(2, 0, g3);
    
    // Component 2: chain (5-6-7-8)
    add_edge(5, 6, g1); add_edge(5, 6, g2); add_edge(5, 6, g3);
    add_edge(6, 7, g1); add_edge(6, 7, g2); add_edge(6, 7, g3);
    add_edge(7, 8, g1); add_edge(7, 8, g2); add_edge(7, 8, g3);
    
    // Component 3: pair (10-11)
    add_edge(10, 11, g1); add_edge(10, 11, g2); add_edge(10, 11, g3);
    
    // Vertices 3, 4, 9, 12, 13, 14 are isolated (6 singletons)
    auto expected = 3 + 6;

    // Same generic algorithm works on all graph types
    assert(count_components(g1) == expected);
    assert(count_components(g2) == expected);
    assert(count_components(g3) == expected);    
}

See a more complexe example in examples/quick_tour.cpp.