Boost Graph Library

The Boost Graph Library (BGL) is a generic library that allows users to:

1. Represent graph data using different structures (adjacency matrix, adjacency list, compressed sparse row, vectors of vectors, user-defined data structures).
2. Attach user-defined data to vertices, edges, or the graph itself.
3. Run a large number of algorithms on the graph.
4. Inject user logic into algorithms using visitor hooks.

Example

Try it on Compiler Explorer

#include<boost/graph/adjacency_list.hpp>
#include<boost/graph/dijkstra_shortest_paths.hpp>
#include<boost/graph/visitors.hpp>
#include<iostream>
#include<limits>
#include<vector>structCity {};
structRoad { int cost; };
usingnamespaceboost;using Graph = adjacency_list<vecS, vecS, directedS, City, Road>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
intmain() {
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 storageauto 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 = 4

Algorithms

BGL ships dozens of graph algorithms: shortest paths (Dijkstra, Bellman-Ford, A*, Floyd-Warshall, Johnson), spanning trees (Kruskal, Prim), maximum flow (Edmonds-Karp, push-relabel, Boykov-Kolmogorov), traversal (BFS, DFS, topological sort), planarity testing, isomorphism, component decomposition, and more.

See the full algorithm reference for the complete catalogue.

Help and feedback

• GitHub Issues for bug reports. Search before opening a new one.
• GitHub Discussions for questions, design ideas, and general conversation about the library.
• Boost mailing list for general Boost development. Use the [graph] tag in the subject line.
• CppLang Slack for real-time chat. Request an invite, then join the #boost channel.
• Direct contact with maintainers: see CONTRIBUTING.md#maintainers.

Using BGL

Install Boost via your package manager:

Manager	Command
vcpkg	vcpkg install boost-graph
Conan	conan install --requires=boost/[*]
apt (Debian/Ubuntu)	sudo apt install libboost-graph-dev
Homebrew (macOS)	brew install boost

Then wire it into CMake:

find_package(BoostREQUIREDCOMPONENTSgraph)
target_link_libraries(my_appPRIVATEBoost::graph)

Most of BGL is header-only. Linking Boost::graph is only required for the GraphViz and GraphML parsers.

Building from source

For working on BGL itself (building Boost from source, running the test suite), see CONTRIBUTING.md.