Who Uses the Boost Graph Library

Geometry

CGAL

Standard computational-geometry library

A 3D mesh is a graph. BGL algorithms run on meshes directly, and min cut segments them. (source)

Geometry

SFCGAL

3D geometry library behind PostGIS’s 3D functions

Validity checks build a graph of geometry parts and test whether they are connected. (source)

Geometry

IfcOpenShell

Open toolkit for BIM (IFC building models)

Converts solids to half-space trees in its CGAL geometry kernel. (source)

Geometry

OpenCamLib

CNC toolpath library used by FreeCAD’s CAM workbench

Half-edge diagram for toolpath geometry, and metric TSP to order cuts. (source)

Robotics

OMPL

Motion-planning library behind MoveIt

Roadmap of collision-free poses, with A* finding a path through it. (source)

Robotics

GTSAM

Robot localization and mapping (SLAM)

Spanning tree over pose measurements gives the optimizer its initial guess. (source)

Robotics

Lanelet2

HD-map framework for automated driving (used by Autoware)

Lanes form a routing graph, with filtered views for drivable-only routes. (source)

Robotics

Tesseract

Industrial robot motion-planning framework

Robot links and joints form a scene graph, checked for trees and cycles. (source)

Vision and 3D

PCL

Point Cloud Library (lidar, depth cameras)

Separates objects from background by cutting a graph of neighboring points. (source)

Vision and 3D

COLMAP

Reference photo-to-3D reconstruction tool

Surface meshing labels space as inside or outside the object with a min s-t cut (BK max flow). (source)

Vision and 3D

AliceVision

Photogrammetry framework behind Meshroom

Max flow extracts surfaces, and graph cuts find panorama seams. (source)

Desktop

FreeCAD

Parametric 3D CAD

Topological sort gives the recompute order, and strong components detect cycles. (source)

Desktop

Krita

Digital painting

Colorize mask fill via graph cut on the pixel grid. (source)

Desktop

digiKam

Photo management

Image version-history graph. (source)

Desktop

Fritzing

Electronics prototyping and PCB design

Wire and part connectivity: max flow, spanning tree, transitive closure. (source)

Desktop

ossia score / libossia

Interactive media sequencer for shows and installations

Real-time audio/video dataflow graph: topological order, transitive closure. (source)

Desktop

Rocs (KDE)

Graph-theory teaching IDE from KDE Education

Automatic graph layouts (force-directed, circle, random) and random graph generation. (source)

GIS

pgRouting

Routing extension for PostGIS

Road networks as graphs: shortest routes, travel-time areas. (source)

Databases

MariaDB OQGRAPH

SQL database, via an optional plugin

SQL queries over hierarchies and networks. (source)

Chemistry

RDKit

Leading cheminformatics toolkit

Every molecule, atoms and bonds, is stored as a BGL adjacency_list. (source)

Mathematics

SageMath

Open-source mathematics system

Its graph module delegates about 20 algorithms to BGL. (source)

Graph analysis

graph-tool

Python network-analysis library

BGL is its C engine and the programming model for its C extensions. It also ships 15 patched BGL headers. (source)

Simulation

deal.II

Finite-element library

Renumbers mesh unknowns so sparse matrices become banded and solvers run faster. (source)

Simulation

Trilinos

Sandia’s numerical-solver suite

GraphViz export of multigrid aggregation graphs. (source)

Simulation

GUDHI

INRIA topological data analysis library

Builds simplicial complexes from neighborhood graphs of data points. (source)

Simulation

Siconos

Nonsmooth dynamics simulator (contact, friction, switching circuits)

Interacting bodies and constraints are stored as a graph. (source)

Genomics

AUGUSTUS

Standard gene-prediction tool

Comparative mode aligns genomes as a graph to predict genes jointly. (source)

Genomics

ABySS

Short-read genome assembler

Assembly-graph algorithms written against BGL graph concepts. (source)

Genomics

Delly

Structural-variant caller

Clusters reads supporting the same variant via connected components. (source)

Genomics

Shasta

Long-read (nanopore) genome assembler

Read graph and assembly graphs, simplified with dominator trees. (source)

Genomics

MetaBAT

Metagenome binning tool

Its legacy MetaBAT 1 binner, still shipped, stores the contig graph in BGL. (source)

Genomics

BAli-Phy

Leading Bayesian tool for joint alignment and phylogeny estimation

Orders its model computations and alignment columns with topological sort and strong components. (source)

Genomics

progressiveMauve

Whole-genome multiple aligner

Orders aligned segments with topological sort and shortest paths. (source)

Proteomics

OpenMS

Mass-spectrometry data analysis platform

Protein inference splits the protein-peptide graph into independent components. (source)

Proteomics

TopPIC

Widely used top-down proteomics suite

TopMG represents proteoforms as "mass graphs" and aligns spectra against them. (source)

Particle physics

CMSSW (CERN)

CMS experiment software

Module dependency graph analysis and drawing. (source)

Particle physics

Gaudi (CERN)

LHCb/ATLAS framework

Scheduler reads a precedence graph to parallelize algorithms. (source)

Security

Vectorscan (Hyperscan fork)

High-speed regex engine for IDS (Snort, Suricata)

Regexes compile to automata, which are graphs, optimized with graph algorithms. (source)

Compilers

SDCC

C compiler for 8-bit microcontrollers

Register allocation over a tree decomposition of the control-flow graph. (source)

Compilers

ROSE

LLNL source-to-source compiler framework

Control-flow graphs, dominators and program-dependence graphs. (source)

Compilers

XIR (AMD Vitis AI)

Graph IR for AI accelerators

Neural networks as graphs: topological order and subgraph matching (VF2). (source)

Optimization

MiniZinc

Constraint-modelling language and toolchain

Minimum cut of the constraint graph (Stoer-Wagner). (source)

Optimization

pagmo

ESA’s parallel global-optimization library

Islands exchange solutions along a migration-topology graph. (source)

Optimization

toulbar2

INRAE solver for cost-function networks

Decomposes the constraint graph (orderings, spanning trees, components) to split problems. (source)

Logistics

Maersk (internal)

Container shipping

Routing and cargo allocation as shortest-path and max-flow problems. (source)

Economics

Dynare

Macroeconomic modelling tool used by central banks

Matching and strong components split models into blocks solved in sequence. (source)

Crystallography

cctbx

Crystallography toolbox behind Phenix

Python bindings to BGL: min cut, and max clique for structure matching. (source)

Crystallography

DIALS

X-ray diffraction data processing

Connected components group diffraction-spot pixels. (source)

Hardware

UHD (Ettus)

Driver for USRP software-defined radios

FPGA processing blocks form a graph traversed to set up streaming. (source)

Games

Battle for Wesnoth

Open-source strategy game

Detects cycles in its config-schema inheritance (DFS back edges). (source)

Games

FreeOrion

Open-source space strategy game

Starlane pathfinding and supply-network propagation. (source)

Games

scummvm-tools

Official tool suite of the ScummVM game-engine project

Its script decompiler builds a control-flow graph and exports it to GraphViz. (source)

Other

Ledger

Plain-text double-entry accounting

Commodity price graph, with Dijkstra finding conversion chains between currencies. (source)

Other

libkleo (KDE)

KDE PIM crypto-key library

Topological sort to display key and certificate hierarchies. (source)