Quick Start
You are viewing the master version of this library.
The master and develop pages are shown here to provide access to the newest in-development in-progress documentation. See the "Documentation" link on this page.
Other aspects of the page will reflect the previous official version, or not be available until the next release.
Contributors: This Release
Boost Graph Library
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.
Building from source
For working on BGL itself (building Boost from source, running the test suite), see CONTRIBUTING.md.
Latest Boost.Graph posts
All Contributors
<h1>Boost Graph Library</h1> <p><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://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg" alt="CI" /></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> <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>Building from source</h2> <p>For working on BGL itself (building Boost from source, running the test suite), see <a href="CONTRIBUTING.md">CONTRIBUTING.md</a>.</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://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://github.com/boostorg/graph/actions/workflows/ci.yml"><img src="https://github.com/boostorg/graph/actions/workflows/ci.yml/badge.svg" alt="CI" /></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> <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>Building from source</h2> <p>For working on BGL itself (building Boost from source, running the test suite), see <a href="CONTRIBUTING.md">CONTRIBUTING.md</a>.</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.
