Quick Start
Boost Graph Library
CAUTION: Boost.Graph in Boost 1.93 deprecates support for C++14 and will require C++17 from Boost 1.95 onwards (see discussion #613).
The Boost Graph Library (BGL) is a generic library that allows users to:
- Represent graph data using different structures (adjacency matrix, adjacency list, compressed sparse row, vectors of vectors, user-defined data structures).
- Attach user-defined data to vertices, edges, or the graph itself.
- Run a large number of algorithms on the graph.
- Inject user logic into algorithms 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 = 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
#boostchannel. - 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(Boost REQUIRED COMPONENTS graph)
target_link_libraries(my_app PRIVATE Boost::graph)
Most of BGL is header-only. Linking Boost::graph is only required for the GraphViz and GraphML parsers.
Contributing
Bug fixes, new algorithms, documentation and performance work are all welcome. CONTRIBUTING.md covers building Boost from source, running the test suite, and the pull request process.
Latest Boost.Graph posts
<h1>Boost Graph Library</h1> <p><a href="https://github.com/boostorg/graph/tree/master"><img src="https://img.shields.io/badge/branch-master-brightgreen.svg" alt="Branch" /></a> <a href="https://www.boost.org/doc/libs/master/libs/graph/doc/html/graph/index.html"><img src="https://img.shields.io/badge/docs-master-brightgreen.svg" alt="Documentation" /></a> <a href="https://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg?branch=master" alt="CI" /></a> <a href="https://codecov.io/gh/boostorg/graph/branch/master"><img src="https://codecov.io/gh/boostorg/graph/branch/master/graph/badge.svg" alt="codecov" /></a> <a href="https://pdimov.github.io/boostdep-report/master/graph.html"><img src="https://img.shields.io/badge/deps-master-brightgreen.svg" alt="Deps" /></a> <a href="https://regression.boost.org/master/developer/graph.html"><img src="https://img.shields.io/badge/matrix-master-brightgreen.svg" alt="Enter the Matrix" /></a><br/> <a href="https://github.com/boostorg/graph/tree/develop"><img src="https://img.shields.io/badge/branch-develop-brightgreen.svg" alt="Branch" /></a> <a href="https://www.boost.org/doc/libs/develop/libs/graph/doc/html/graph/index.html"><img src="https://img.shields.io/badge/docs-develop-brightgreen.svg" alt="Documentation" /></a> <a href="https://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg?branch=develop" alt="CI" /></a> <a href="https://codecov.io/gh/boostorg/graph/branch/develop"><img src="https://codecov.io/gh/boostorg/graph/branch/develop/graph/badge.svg" alt="codecov" /></a> <a href="https://pdimov.github.io/boostdep-report/develop/graph.html"><img src="https://img.shields.io/badge/deps-develop-brightgreen.svg" alt="Deps" /></a> <a href="https://regression.boost.org/develop/developer/graph.html"><img src="https://img.shields.io/badge/matrix-develop-brightgreen.svg" alt="Enter the Matrix" /></a><br/> <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/index.html"><img src="https://img.shields.io/badge/docs-boost.org-blue.svg" alt="Docs" /></a> <a href="https://en.cppreference.com/w/cpp/14"><img src="https://img.shields.io/badge/C%2B%2B-14-blue.svg" alt="C++14" /></a> <a href="https://www.boost.org/LICENSE_1_0.txt"><img src="https://img.shields.io/badge/License-BSL_1.0-blue.svg" alt="License: BSL-1.0" /></a> <a href="https://github.com/boostorg/boost/releases"><img src="https://img.shields.io/github/v/release/boostorg/boost?label=Boost&color=orange" alt="Boost release" /></a></p> <blockquote> <p><strong>CAUTION</strong>: Boost.Graph in Boost 1.93 deprecates support for C++14 and will require C++17 from Boost 1.95 onwards (see discussion <a href="https://github.com/boostorg/graph/discussions/613">#613</a>).</p> </blockquote> <p>The Boost Graph Library (BGL) is a generic library that allows users to:</p> <ol> <li>Represent graph data using different structures (adjacency matrix, adjacency list, compressed sparse row, vectors of vectors, user-defined data structures).</li> <li>Attach user-defined data to vertices, edges, or the graph itself.</li> <li>Run a large number of algorithms on the graph.</li> <li>Inject user logic into algorithms using visitor hooks.</li> </ol> <h2>Example</h2> <p><a href="https://godbolt.org/z/9Esszr9Ga">Try it on Compiler Explorer</a></p> <pre class="highlightjs highlight"><code class="language-cpp hljs">#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"; } </code></pre> <pre class="highlightjs highlight"><code class="language- hljs">distance to 0 = 0 distance to 1 = 1 distance to 2 = 3 distance to 3 = 4 </code></pre> <h2>Algorithms</h2> <p>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.</p> <p>See the <a href="https://becheler.github.io/graph/graph/algorithms/overview.html">full algorithm reference</a> for the complete catalogue.</p> <h2>Help and feedback</h2> <ul> <li><strong><a href="https://github.com/boostorg/graph/issues">GitHub Issues</a></strong> for bug reports. Search before opening a new one.</li> <li><strong><a href="https://github.com/boostorg/graph/discussions">GitHub Discussions</a></strong> for questions, design ideas, and general conversation about the library.</li> <li><strong><a href="http://lists.boost.org/mailman/listinfo.cgi/boost-users">Boost mailing list</a></strong> for general Boost development. Use the <code>[graph]</code> tag in the subject line.</li> <li><strong>CppLang Slack</strong> for real-time chat. <a href="https://cppalliance.org/slack/">Request an invite</a>, then join the <code>#boost</code> channel.</li> <li><strong>Direct contact with maintainers</strong>: see <a href="CONTRIBUTING.md#maintainers">CONTRIBUTING.md#maintainers</a>.</li> </ul> <h2>Using BGL</h2> <p>Install Boost via your package manager:</p> <table> <thead> <tr> <th align="left">Manager</th> <th align="left">Command</th> </tr> </thead> <tbody> <tr> <td align="left"><a href="https://vcpkg.io">vcpkg</a></td> <td align="left"><code>vcpkg install boost-graph</code></td> </tr> <tr> <td align="left"><a href="https://conan.io">Conan</a></td> <td align="left"><code>conan install --requires=boost/[*]</code></td> </tr> <tr> <td align="left">apt (Debian/Ubuntu)</td> <td align="left"><code>sudo apt install libboost-graph-dev</code></td> </tr> <tr> <td align="left">Homebrew (macOS)</td> <td align="left"><code>brew install boost</code></td> </tr> </tbody> </table> <p>Then wire it into CMake:</p> <pre class="highlightjs highlight"><code class="language-cmake hljs">find_package(Boost REQUIRED COMPONENTS graph) target_link_libraries(my_app PRIVATE Boost::graph) </code></pre> <p>Most of BGL is header-only. Linking <code>Boost::graph</code> is only required for the GraphViz and GraphML parsers.</p> <h2>Contributing</h2> <p>Bug fixes, new algorithms, documentation and performance work are all welcome. <a href="CONTRIBUTING.md">CONTRIBUTING.md</a> covers building Boost from source, running the test suite, and the pull request process.</p>
-
Code Commits Commits authored to any Boost repository. With 1 contribution, you will earn the bronze badge for Code Commits.
-
Documentation Doc contributions using standardised Boost tooling (Antora / BoostLook). With 1 contribution, you will earn the bronze badge for Documentation.
-
Library Authoring Authored an original Boost library accepted into the collection. With 1 contribution, you will earn the bronze badge for Library Authoring.
-
Library Maintenance Number of libraries actively maintained. With 1 contribution, you will earn the bronze badge for Library Maintenance.
-
Library Review Formal review submissions on Boost proposals. With 1 contribution, you will earn the bronze badge for Library Review.
-
Library Versioning Authored new versions / releases of Boost libraries. With 10 contributions, you will earn the bronze badge for Library Versioning.
-
Mailing List Participation Participation on the Boost developers mailing list. With 1 contribution, you will earn the bronze badge for Mailing List Participation.
-
News Posts Published Articles / news posts published on Boost.org. With 1 contribution, you will earn the bronze badge for News Posts Published.
<h1>Boost Graph Library</h1> <p><a href="https://github.com/boostorg/graph/tree/master"><img src="https://img.shields.io/badge/branch-master-brightgreen.svg" alt="Branch" /></a> <a href="https://www.boost.org/doc/libs/master/libs/graph/doc/html/graph/index.html"><img src="https://img.shields.io/badge/docs-master-brightgreen.svg" alt="Documentation" /></a> <a href="https://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg?branch=master" alt="CI" /></a> <a href="https://codecov.io/gh/boostorg/graph/branch/master"><img src="https://codecov.io/gh/boostorg/graph/branch/master/graph/badge.svg" alt="codecov" /></a> <a href="https://pdimov.github.io/boostdep-report/master/graph.html"><img src="https://img.shields.io/badge/deps-master-brightgreen.svg" alt="Deps" /></a> <a href="https://regression.boost.org/master/developer/graph.html"><img src="https://img.shields.io/badge/matrix-master-brightgreen.svg" alt="Enter the Matrix" /></a><br/> <a href="https://github.com/boostorg/graph/tree/develop"><img src="https://img.shields.io/badge/branch-develop-brightgreen.svg" alt="Branch" /></a> <a href="https://www.boost.org/doc/libs/develop/libs/graph/doc/html/graph/index.html"><img src="https://img.shields.io/badge/docs-develop-brightgreen.svg" alt="Documentation" /></a> <a href="https://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg?branch=develop" alt="CI" /></a> <a href="https://codecov.io/gh/boostorg/graph/branch/develop"><img src="https://codecov.io/gh/boostorg/graph/branch/develop/graph/badge.svg" alt="codecov" /></a> <a href="https://pdimov.github.io/boostdep-report/develop/graph.html"><img src="https://img.shields.io/badge/deps-develop-brightgreen.svg" alt="Deps" /></a> <a href="https://regression.boost.org/develop/developer/graph.html"><img src="https://img.shields.io/badge/matrix-develop-brightgreen.svg" alt="Enter the Matrix" /></a><br/> <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/index.html"><img src="https://img.shields.io/badge/docs-boost.org-blue.svg" alt="Docs" /></a> <a href="https://en.cppreference.com/w/cpp/14"><img src="https://img.shields.io/badge/C%2B%2B-14-blue.svg" alt="C++14" /></a> <a href="https://www.boost.org/LICENSE_1_0.txt"><img src="https://img.shields.io/badge/License-BSL_1.0-blue.svg" alt="License: BSL-1.0" /></a> <a href="https://github.com/boostorg/boost/releases"><img src="https://img.shields.io/github/v/release/boostorg/boost?label=Boost&color=orange" alt="Boost release" /></a></p> <blockquote> <p><strong>CAUTION</strong>: Boost.Graph in Boost 1.93 deprecates support for C++14 and will require C++17 from Boost 1.95 onwards (see discussion <a href="https://github.com/boostorg/graph/discussions/613">#613</a>).</p> </blockquote> <p>The Boost Graph Library (BGL) is a generic library that allows users to:</p> <ol> <li>Represent graph data using different structures (adjacency matrix, adjacency list, compressed sparse row, vectors of vectors, user-defined data structures).</li> <li>Attach user-defined data to vertices, edges, or the graph itself.</li> <li>Run a large number of algorithms on the graph.</li> <li>Inject user logic into algorithms using visitor hooks.</li> </ol> <h2>Example</h2> <p><a href="https://godbolt.org/z/9Esszr9Ga">Try it on Compiler Explorer</a></p> <pre class="highlightjs highlight"><code class="language-cpp hljs">#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"; } </code></pre> <pre class="highlightjs highlight"><code class="language- hljs">distance to 0 = 0 distance to 1 = 1 distance to 2 = 3 distance to 3 = 4 </code></pre> <h2>Algorithms</h2> <p>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.</p> <p>See the <a href="https://becheler.github.io/graph/graph/algorithms/overview.html">full algorithm reference</a> for the complete catalogue.</p> <h2>Help and feedback</h2> <ul> <li><strong><a href="https://github.com/boostorg/graph/issues">GitHub Issues</a></strong> for bug reports. Search before opening a new one.</li> <li><strong><a href="https://github.com/boostorg/graph/discussions">GitHub Discussions</a></strong> for questions, design ideas, and general conversation about the library.</li> <li><strong><a href="http://lists.boost.org/mailman/listinfo.cgi/boost-users">Boost mailing list</a></strong> for general Boost development. Use the <code>[graph]</code> tag in the subject line.</li> <li><strong>CppLang Slack</strong> for real-time chat. <a href="https://cppalliance.org/slack/">Request an invite</a>, then join the <code>#boost</code> channel.</li> <li><strong>Direct contact with maintainers</strong>: see <a href="CONTRIBUTING.md#maintainers">CONTRIBUTING.md#maintainers</a>.</li> </ul> <h2>Using BGL</h2> <p>Install Boost via your package manager:</p> <table> <thead> <tr> <th align="left">Manager</th> <th align="left">Command</th> </tr> </thead> <tbody> <tr> <td align="left"><a href="https://vcpkg.io">vcpkg</a></td> <td align="left"><code>vcpkg install boost-graph</code></td> </tr> <tr> <td align="left"><a href="https://conan.io">Conan</a></td> <td align="left"><code>conan install --requires=boost/[*]</code></td> </tr> <tr> <td align="left">apt (Debian/Ubuntu)</td> <td align="left"><code>sudo apt install libboost-graph-dev</code></td> </tr> <tr> <td align="left">Homebrew (macOS)</td> <td align="left"><code>brew install boost</code></td> </tr> </tbody> </table> <p>Then wire it into CMake:</p> <pre class="highlightjs highlight"><code class="language-cmake hljs">find_package(Boost REQUIRED COMPONENTS graph) target_link_libraries(my_app PRIVATE Boost::graph) </code></pre> <p>Most of BGL is header-only. Linking <code>Boost::graph</code> is only required for the GraphViz and GraphML parsers.</p> <h2>Contributing</h2> <p>Bug fixes, new algorithms, documentation and performance work are all welcome. <a href="CONTRIBUTING.md">CONTRIBUTING.md</a> covers building Boost from source, running the test suite, and the pull request process.</p>
-
Achievement-based Reflects the depth of your contributions. Accumulate achievements to unlock five tiers; Bronze, Silver, Gold, Platinum and Diamond.
-
Tenure-based Awarded in recognition of your time on the platform. The longer you've been part of the Boost community, the higher the tier you unlock.
-
Boost day celebration A celebration of the day you joined Boost. Awarded annually to mark another year as part of the community.
