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.
# 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| Requirement | Minimum Version | Notes |
|---|---|---|
| CMake | 3.20+ | Build system |
| C++ Compiler | GCC 11+ or Clang 14+ | C++20 support required |
| oneTBB | 2021+ | Parallel backend |
macOS (Homebrew):
brew install cmake gcc tbbUbuntu/Debian:
sudo apt install cmake g++-11 libtbb-devIntel oneAPI (all platforms):
# Download from:
# https://www.intel.com/content/www/us/en/developer/articles/tool/oneapi-standalone-components.html#onetbbmkdir build && cd build
cmake ..
make -j8cmake .. -DNWGRAPH_BUILD_TESTS=ON \
-DNWGRAPH_BUILD_EXAMPLES=ON \
-DNWGRAPH_BUILD_BENCH=ON
make -j8| 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/
├── 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
cmake .. -DCMAKE_CXX_COMPILER=g++-11If CMake cannot find TBB:
TBBROOT=/opt/intel/oneapi/tbb/2021.5.1 cmake ..NWGraph documentation is built using Sphinx with Doxygen integration.
# Install Python dependencies
pip install sphinx sphinx_rtd_theme breathe exhale sphinxcontrib-bibtex
# Install Doxygen
brew install doxygen # macOS
sudo apt install doxygen # UbuntuOption 1: Via CMake (recommended)
cmake .. -DNWGRAPH_BUILD_DOCS=ON
make docsOption 2: Direct Sphinx build
cd doc-src/sphinx
pip install -r requirements.txt
make html| 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
cmake .. -DNWGRAPH_BUILD_BENCH=ON
make bench -j8./bench/gapbs/bfs -f ../test/data/karate.mtx -n 3 --verify
./bench/gapbs/cc -f ../test/data/karate.mtx --verify| 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 |
# 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# 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 4cmake .. -DNWGRAPH_BUILD_EXAMPLES=ON
make -j8./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 MSTNWGraph/
├── 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
- 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
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.
BSD-3-Clause