NWGraph: Northwest Graph Library

NWGraph is a high-performance header-only generic C++ graph library, based on C++20 concept and range language features. It consists of multiple graph algorithms for well-known graph kernels and supporting data structures. Both sequential and parallel algorithms are available.

Quick Start

# Clone the repository
git clone https://github.com/pnnl/nwgraph.git
cd nwgraph
# Build (tests only)
mkdir build &&cd build
cmake ..
make -j8
# Run tests
ctest

Requirements

Requirement	Minimum Version	Notes
CMake	3.20+	Build system
C++ Compiler	GCC 11+ or Clang 14+	C++20 support required
oneTBB	2021+	Parallel backend

Installing Dependencies

macOS (Homebrew):

brew install cmake gcc tbb

Ubuntu/Debian:

sudo apt install cmake g++-11 libtbb-dev

Intel oneAPI (all platforms):

# Download from:# https://www.intel.com/content/www/us/en/developer/articles/tool/oneapi-standalone-components.html#onetbb

Building NWGraph

Basic Build

mkdir build &&cd build
cmake ..
make -j8

Build Everything

cmake .. -DNWGRAPH_BUILD_TESTS=ON \
-DNWGRAPH_BUILD_EXAMPLES=ON \
-DNWGRAPH_BUILD_BENCH=ON
make -j8

CMake Options

Option	Default	Description
NWGRAPH_BUILD_TESTS	ON	Build unit tests
NWGRAPH_BUILD_EXAMPLES	OFF	Build BGL book examples
NWGRAPH_BUILD_BENCH	OFF	Build GAP benchmarks
NWGRAPH_BUILD_DOCS	OFF	Build documentation
CMAKE_BUILD_TYPE	Release	Build type (Release/Debug)

Build Output

build/
├── test/ # Unit tests
├── examples/bgl-book/ # BGL book examples
└── bench/
├── gapbs/ # GAP Benchmark Suite (bfs, cc, pr, sssp, bc, tc)
└── abstraction_penalty/ # Abstraction penalty benchmarks

Compiler Selection

cmake .. -DCMAKE_CXX_COMPILER=g++-11

TBB Configuration

If CMake cannot find TBB:

TBBROOT=/opt/intel/oneapi/tbb/2021.5.1 cmake ..

Building Documentation

NWGraph documentation is built using Sphinx with Doxygen integration.

Documentation Dependencies

# Install Python dependencies
pip install sphinx sphinx_rtd_theme breathe exhale sphinxcontrib-bibtex
# Install Doxygen
brew install doxygen # macOS
sudo apt install doxygen # Ubuntu

Build Documentation

Option 1: Via CMake (recommended)

cmake .. -DNWGRAPH_BUILD_DOCS=ON
make docs

Option 2: Direct Sphinx build

cd doc-src/sphinx
pip install -r requirements.txt
make html

Documentation Targets

Target	Description
make docs	Build complete documentation (Doxygen + Sphinx)
make docs-html	Build HTML only (faster, uses cached Doxygen)
make docs-clean	Clean built documentation
make docs-open	Build and open in browser (macOS/Linux)

Documentation output: doc-src/sphinx/_build/html/index.html

Running Benchmarks

Build Benchmarks

cmake .. -DNWGRAPH_BUILD_BENCH=ON
make bench -j8

Quick Test

./bench/gapbs/bfs -f ../test/data/karate.mtx -n 3 --verify
./bench/gapbs/cc -f ../test/data/karate.mtx --verify

GAP Benchmark Suite

Kernel	Description	Best Version
bfs	Breadth-First Search	--version 11
sssp	Single-Source Shortest Path	--version 12
pr	PageRank	--version 11
cc	Connected Components	--version 7
bc	Betweenness Centrality	--version 5
tc	Triangle Counting	--version 4

Download GAP Graphs

# List available graphs
./scripts/download_gap_graphs.sh --list
# Download road network (smallest, ~1GB)
./scripts/download_gap_graphs.sh road
# Download all real-world graphs
./scripts/download_gap_graphs.sh all

Example Benchmark Commands

# BFS with direction-optimizing algorithm
./bench/gapbs/bfs -f data/graphs/road.gr --version 11 -n 64
# PageRank with 1000 iterations
./bench/gapbs/pr -f data/graphs/web.mtx -i 1000
# Triangle counting with relabeling
./bench/gapbs/tc -f data/graphs/twitter.el --relabel --upper --version 4

Running Examples

Build Examples

cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make -j8

Run BGL Book Examples

./examples/bgl-book/ch3_toposort # Topological sort
./examples/bgl-book/ch4_kevin_bacon # Six degrees of Kevin Bacon
./examples/bgl-book/ch5_dijkstra # Dijkstra's algorithm
./examples/bgl-book/ch6_kruskal # Kruskal's MST

Project Organization

NWGraph/
├── include/nwgraph/ # Header-only library
│ ├── adaptors/ # Range adaptors (bfs_range, dfs_range, etc.)
│ ├── algorithms/ # Graph algorithms
│ ├── containers/ # Graph containers
│ ├── io/ # I/O utilities
│ └── graph_concepts.hpp # C++20 concepts
├── test/ # Unit tests (Catch2)
├── examples/bgl-book/ # BGL book examples
├── bench/
│ ├── gapbs/ # GAP Benchmark Suite
│ └── abstraction_penalty/ # Abstraction penalty benchmarks
├── doc-src/sphinx/ # Documentation source
└── scripts/ # Utility scripts

Supported File Formats

• Matrix Market (.mtx) - Standard sparse matrix format
• Edge List (.el) - Simple edge pairs
• DIMACS (.gr) - 9th DIMACS Challenge format
• NWGraph Binary (.nw) - Fast native format

References

Lumsdaine, Andrew, et al. "NWGraph: A Library of Generic Graph Algorithms and Data Structures in C++ 20." In 36th European Conference on Object-Oriented Programming (ECOOP) 2022.

License

BSD-3-Clause