Boost.Graph

This is a beta version of Boost. The current version is 1.91.0.

C++ 14 Added in Boost 1.18.0

Categories: Containers , Algorithms , Iterators

The BGL graph interface and graph components are generic, in the same sense as the Standard Template Library (STL).

Documentation www.boost.org/doc/libs/1_92_0_beta1/libs/graph/index.html

GitHub Issues github.com/boostorg/graph/issues

Source Code github.com/boostorg/graph/tree/boost-1.92.0.beta1

This Release

Jeremy W. Murphy

Maintainer

Arnaud Becheler

Maintainer

Dependencies

Library dependencies will be generated soon, please check back later.

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

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>

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 #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(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.

All Time

Jeremy Siek

Contributor

Jeremiah Willcock

Contributor

Douglas Gregor

Contributor

John Maddock

Contributor

Andrew Sutton

Contributor

Vladimir Prus

Contributor

K. Noel Belcourt

Contributor

Beman Dawes

Contributor

Aaron Windsor

Contributor

Dave Abrahams

Contributor

Ronald Garcia

Contributor

nobody

Contributor

jrmarsha

Contributor

Cromwell D. Enage

Contributor

Daniel James

Contributor

Peter Dimov

Contributor

Jan-Grimo Sobez

Contributor

Joris van Rantwijk

Contributor

Murray Cumming

Contributor

Daan Kolthof

Contributor

Jürgen Hunold

Contributor

Lie-Quan Lee

Contributor

Rene Rivera

Contributor

Eric Niebler

Contributor

Sven Gato Redsun

Contributor

E Kawashima

Contributor

sehe

Contributor

Sebastian Brockmeyer

Contributor

Jakob Lykke Andersen

Contributor

Mads Jensen

Contributor

Josef Cibulka

Contributor

Alexander Lauser

Contributor

Marshall Clow

Contributor

Stephen Kelly

Contributor

andrea-cassioli-maersk

Contributor

Alec Edgington

Contributor

Gennaro Prota

Contributor

jiyi

Contributor

Valentyn Shtronda

Contributor

Josh Marshall

Contributor

Andrey Semashev

Contributor

Nicholas Edmonds

Contributor

Darin Adler

Contributor

Stefan Slapeta

Contributor

yi-ji

Contributor

Edward Diener

Contributor

Jonathan Turkanis

Contributor

BenPope

Contributor

Akira Takahashi

Contributor

Maël Valais

Contributor

Daniel Yang

Contributor

Troy D. Straszheim

Contributor

Michael A. Jackson

Contributor

Daniela Engert

Contributor

Steven Watanabe

Contributor

Marcel Raad

Contributor

vslashg

Contributor

George Williams

Contributor

Glen Fernandes

Contributor

Guillaume Melquiond

Contributor

Anthony Van Herrewege

Contributor

Murray Cumming

Contributor

Pavel I. Kryukov

Contributor

Andreas Huber

Contributor

Andy Shulman

Contributor

Matt Barr

Contributor

Arvin Schnell

Contributor

Billy K. Poon

Contributor

Rasmus Ahlberg

Contributor

Denis Davydov

Contributor

John Zhang

Contributor

Jonathan Wakely

Contributor

David Einstein

Contributor

Björn Karlsson

Contributor

Aleksey Gurtovoy

Contributor

marcinz

Contributor

Victor A. Wagner Jr.

Contributor

Mateusz Polnik

Contributor

Justin Viiret

Contributor

Caleb Epstein

Contributor

Kolya Matteo

Contributor

Louis Dionne

Contributor

Viktor T

Contributor

mikael

Contributor

James E. King III

Contributor

Lorenz Breidenbach

Contributor

hermann@stamm-wilbrandt.de

Contributor

Ahmed Charles

Contributor

Andreas Scherer

Contributor

akumta

Contributor

Marc Glisse

Contributor

Arne B

Contributor

felix

Contributor

Jared Grubb

Contributor

Daniel J. H

Contributor

Ola Nilsson

Contributor

coderakki

Contributor

Derek McBlane

Contributor

l00574988

Contributor

Bruno Martinez

Contributor

Joel de Guzman

Contributor

Matt Pulver

Contributor

Tuukka Norri

Contributor

Bryce Adelstein-Lelbach

Contributor

Jens Maurer

Contributor

Antony Polukhin

Contributor

Pavel Samolysov

Contributor

Jean-Michaël Celerier

Contributor

Alexander Grund

Contributor

Neil Groves

Contributor

Joaquin M. López Muñoz

Contributor

Romain Geissler

Contributor

Jurko Gospodnetić

Contributor

Tinko Bartels

Contributor

etienneINSA

Contributor

Shoaib Meenai

Contributor

hlynurf

Contributor

Nik Reiman

Contributor

Kohei Takahashi

Contributor

Alex Hagen-Zanker

Contributor

Anthony Eden

Contributor

Alexander Zaitsev

Contributor

康小广

Contributor

Ciro Santilli

Contributor

Roland Schwarz

Contributor

Stephan Diederich

Contributor

Katrin Leinweber

Contributor

Alan Somers

Contributor

Jedrzej Solecki

Contributor

Stefan Hammer

Contributor

Fábio Silva

Contributor

Myles1

Contributor

Vadim Peretokin

Contributor

Eugene Zelenko

Contributor

Jared Khan

Contributor

Thomas Witt

Contributor

Alisdair Meredith

Contributor

Ashish Kumar

Contributor

Philip Allgaier

Contributor

char-lie

Contributor

Vicky Vergara

Contributor

Jesse Li

Contributor

Conrad Poelman

Contributor

Jiachen Dong

Contributor

Georgy Guminov

Contributor

Julien DELACROIX

Contributor

Noel Belcourt

Contributor

Francois Kritzinger

Contributor

ꓪꓱꓱꓠꓛꓧ

Contributor