dynG: dynamic graph and hypergraph updates on GPUs

Alpha: 0.2.0. The latest release is 0.2.0 (pip install dyng): the C++ library, the Python package and the dyng command line, with sssp, cycle_count and mosp stable (SemVer applies from 0.1.0; to mosp from 0.2.0), the sssp operators engine, the CUDA plugin wheels (pip install "dyng[cu13]" / "dyng[cu12]") and the teaching algorithms dynamic_bfs and triangle_delta (see Install). The other algorithms of the table are planned for later releases.

dynG is a C++17/CUDA library with Python bindings that keeps the results of graph and hypergraph algorithms up to date while the structure changes in batches of insertions, deletions and weight changes, without recomputing from scratch. It unifies the research codes of several published systems for dynamic graphs and hypergraphs on GPUs into one library with one API, one update model, sequential, OpenMP and CUDA backends, and parity tests against the original implementations.

Keywords: dynamic graph, batch update, GPU, CUDA, OpenMP, hypergraph, shortest paths, cycle counting, triad counting, label propagation.

Documentation: https://dyng-dev.github.io/dyng/ (getting started, tutorials, the algorithm pages, the C++ and Python API reference; built from docs/ on every push to main).

Algorithms

Algorithm	Computes	Container	Family	Backends	Status	Paper
sssp	dynamic single-source shortest paths	graph	fixed point	sequential, OpenMP, CUDA	stable	DynaMOSP (IPDPS 2025, TPDS 2025)
cycle_count	k-bounded directed simple-cycle histograms	graph	aggregate delta	sequential, OpenMP, CUDA	stable	TruCy / DynTruCy
mosp	multi-objective shortest paths	graph	fixed point	sequential, OpenMP, CUDA	stable	DynaMOSP (IPDPS 2025, TPDS 2025)
dynamic_bfs	BFS hop levels from a source (teaching material)	graph	fixed point	sequential, OpenMP, CUDA	tutorial	- (tutorial)
triangle_delta	the triangle count of an undirected graph (teaching material)	graph	aggregate delta	sequential, OpenMP, CUDA	tutorial	- (tutorial)
triad_count	hypergraph h-motif triad counts	hypergraph	aggregate delta	sequential, OpenMP, CUDA	stable	ESCHER / ESCHER+
label_propagation	binary harmonic label propagation under vertex batches	graph	fixed point	sequential, CUDA	planned (0.4)	DynLP (ICS 2026)
hyper_sssp	shortest hyperpaths	hypergraph	fixed point	sequential, CUDA	planned (0.4)	H-SOSP (IA3 2026)

Each algorithm has a documentation page (docs/algorithms); the table is generated from the algorithms' manifests by scripts/regen.py.

Quickstart

Python (pip install dyng, or pip install . in a clone, see Install):

import dyng

# A weighted directed graph: edges 0->1 (4), 0->2 (1), 2->1 (2), 1->3 (1).
g = dyng.Graph.from_edges([0, 0, 2, 1], [1, 2, 1, 3], [4, 1, 2, 1])
tree = dyng.sssp.compute(g, source=0)              # shortest paths from vertex 0
print(tree.distances.tolist())

batch = dyng.EdgeBatch(insert=([2], [3], [1]), delete=([2], [1]))
stats = dyng.sssp.update(g, batch, tree)           # applies the batch, repairs the tree
print(tree.distances.tolist(), stats.invalidated)

prints

[0, 3, 1, 4]
[0, 4, 1, 2] 2

C++ (the same steps):

#include <dyng/dyng.hpp>
#include <iostream>

int main() {
  auto res = dyng::resources::sequential();               // or openmp(), cuda()
  dyng::edge_list<std::int32_t, std::int32_t> edges{4, {0, 0, 2, 1}, {1, 2, 1, 3}, {4, 1, 2, 1}, 1};
  auto g = dyng::graph<>::from_edges(res, edges.view());  // 4 vertices, one weight per edge
  auto tree = dyng::sssp::compute(res, g, /*source=*/0);  // shortest paths from vertex 0
  dyng::edge_batch<std::int32_t, std::int32_t> batch;
  batch.delete_edge(2, 1);
  batch.insert_edge(2, 3, {1});
  auto st = dyng::sssp::update(res, g, batch.view(), tree);  // applies the batch, repairs the tree
  for (auto d : dyng::to_vector(res, tree.distances())) std::cout << d << ' ';
  std::cout << "| invalidated " << st.invalidated << '\n';
}

prints

0 4 1 2 | invalidated 2

Both quickstarts are run by the test suite (python/tests/test_doc_snippets.py and the CTest example.readme_quickstart), so they always match the library. The command line does the same on files in the original tools' formats: dyng sssp update --graph G --changes DIR --out OUT (CLI reference).

Status

Area	State
Core (resources, backends, memory, arrays, errors, logging, profiler)	working on the host (M1a) and on CUDA (M1b: streams, stream-ordered memory resources, device buffers, profiler device times)
Graph container (compact rows, MOSP and CycleEnumeration batch semantics, weighted and unweighted graphs), MOSP-format and edge-list I/O	working; under MOSP semantics the updated CSR is byte-identical to MOSP-OpenMP's applyChangeBatch (M1a); under set semantics (batch_semantics::set(), graph_properties::cycle_enum_compatible()) a batch is applied as CycleEnumeration-GPU's prepare_batch + apply_batch on the host (M2a) and, on a resident CUDA graph without weight columns, merged on the device (build_next_rows_kernel; the host copy is downloaded only when read, M2b, ADR 0020)
sssp: dynamic single-source shortest paths (DynaMOSP SOSP update), sequential and OpenMP	working; byte-identical to MOSP-OpenMP@c352151 on its 495-case golden corpus (parity certificate)
sssp on CUDA (the fused persistent cooperative kernel)	working (M1b); byte-identical to MOSP-CUDA@e220ee2 on the same corpus, cross-backend equal, performance gates recorded (M1b certificate)
cycle_count: exact k-bounded directed cycle histograms (TruCy/DynTruCy update), sequential and OpenMP	working (M2a); bit-identical to CycleEnumeration-GPU@0a976ad on its 24-case golden corpus (parity certificate)
cycle_count on CUDA (the work-queue static counters, the update on a resident device graph)	working (M2b); bit-identical to CycleEnumeration-GPU@0a976ad's CUDA backend on its golden corpus and cross-backend equal, within the CUDA performance gates in both scopes (at the boost lock: static kernels 0.67-1.00x, updates 0.39-0.93x, chained updates on the resident graph 0.23-0.89x; the COLLAB update is read at the base lock, ADR 0021) and the original's device memory (M2b certificate)
sssp's CUDA operators engine and mosp: multi-objective shortest paths (DynaMOSP MOSP update) on every backend, with dyng.mosp and dyng mosp	working (M7; mosp stable from 0.2.0): the operators engine byte-identical to the fused one; mosp byte-identical to MOSP-OpenMP@c352151 and MOSP-CUDA@e220ee2 (combined graph and path costs included) and within their gates (M7 record; the release gates of 0.2.0 in benchmarks/results/0.2.0/)
Hypergraph container (dyng::hypergraph and dyng.Hypergraph on the ESCHER store: best-fit id reuse under both id_reuse orders, the sorted-merge line graph, .hg / .dgb I/O, generators) on every backend	working (M8a/M8b, on the development branch; the headers are frozen and stable from 0.3.0, pending the author's confirmation at the release): ids, rows and line graphs equal to ESCHER-GPU@abcf9b2 and MOSP_ESCHER@4b86159 on their batch records, device memory equal to ESCHER-GPU's store accounting (M8b record)
triad_count: the h-motif triads of a hypergraph (ESCHER/ESCHER+) on every backend, with dyng.triad_count and dyng triad_count	working (M9a/M9b, on the development branch; frozen and stable from 0.3.0, pending the author's confirmation at the release): exact against ESCHER-GPU@abcf9b2 on its 300-case golden set, by key and by content (cuda on every case, the host backends on the cases of their coverage table), and within its timing and memory gates (M9a record, M9b record)
experimental::count_local_patterns<op_t>: a new hypergraph pattern, given as an Op, on triad_count's engine (C++ and nvcc)	experimental (M9b, ADR 0058; may change in any minor release): triad_count's four patterns through it equal triad_count bit for bit; the tutorial's Ops exact against a brute force under updates
label_propagation (DynLP), hyper_sssp (H-SOSP)	planned (0.4)
Python package dyng (the sequential and OpenMP backends; import dyng) and the dyng command line	working: on PyPI since 0.1.0 (pip install dyng), a CPU wheel for CPython >= 3.12 (abi3, manylinux_2_28 x86_64) (M5), byte-identical to the originals on the Python-level parity subset; the CUDA plugin wheels dyng-cu12 / dyng-cu13 (pip install "dyng[cu13]"; M6a) on PyPI since 0.2.0

The name

dynG = dynamic graphs. The name is written dynG (lower-case dyn, capital G); all code identifiers are lower case (namespace dyng, #include <dyng/...>, import dyng). dynG is inspired by Gunrock and follows ideas of RAPIDS cuGraph and RAFT, but it is not affiliated with either project.

Install

Python package

pip install dyng                         # from PyPI: 0.2.0 (Python >= 3.12, Linux x86-64)
pip install "dyng[cu13]"                 # with the CUDA backend (NVIDIA driver of CUDA 13; "dyng[cu12]": CUDA 12)
pip install -U "dyng[cu13]"              # upgrading from 0.1.0: without -U pip keeps 0.1.0, which has no CUDA extras
pip install .                            # or from a clone (builds the C++ core; needs CMake >= 3.30 and a C++17 compiler)

The wheel contains the sequential and OpenMP backends and the dyng command line. The CUDA backend comes with the plugin wheels: pip install "dyng[cu13]" for an NVIDIA driver of CUDA 13 (driver 580 or newer), pip install "dyng[cu12]" for CUDA 12 (driver 525 or newer); the plugins bring their own CUDA runtime (no toolkit needed) and need a GPU of compute capability 7.5 or newer (install guide).

For development: pip install -e . --no-build-isolation -Ceditable.rebuild=true -Cbuild-dir=build in the dyng-dev environment (below), then ci/python.sh runs the stubs check and the pytest suite.

C++ library from source

Requirements: Linux, a C++17 compiler (GCC >= 11 or Clang >= 15; CI builds with GCC 12/13 and Clang 17/18), CMake >= 3.30, Ninja, and optionally OpenMP and the CUDA toolkit (>= 12.4; an sm_75 or newer GPU to run the CUDA backend). No GPU is needed for the CPU backends.

git clone https://github.com/dyng-dev/dyng.git
cd dyng
conda env create -f environment.yml      # the dyng-dev environment: cmake, ninja, clang-format, ...
source scripts/dev_env.sh                # activates it and sets DYNG_SCRATCH (and nvcc if present)

cmake --preset dev                       # Debug, tests on, warnings as errors
cmake --build --preset dev
ctest --preset dev                       # unit, randomized and fixture-parity tests (no GPU)

ci/check.sh                              # the full local gate: format, cpu-only + dev presets, REUSE, docs

Other presets: cpu-only (Release, CPU backends), release, relwithdebinfo, asan, tsan, tsan-openmp (the sanitizers; ci/sanitizers.sh) and parity (the flags of the original research codes, used for parity and performance runs). ci/docs.sh builds the documentation site (Doxygen with warnings as errors, Sphinx, link check) into build/docs/html; ci/docs.sh --doxygen-only (or the target docs-doxygen) runs only the Doxygen check of the public headers.

Build with CUDA

The CUDA backend needs the CUDA toolkit >= 12.4 (CUDA 13.1 is the development toolkit) and, to run, a GPU of compute capability 7.5 (Turing) or newer. scripts/dev_env.sh puts /usr/local/cuda-13.1/bin on PATH when it exists (set DYNG_CUDA_HOME for another toolkit). The CPU presets above never build CUDA; the CUDA presets are separate:

source scripts/dev_env.sh
cmake --preset dev-cuda                  # Debug, this machine's GPUs (native), host code -Werror
cmake --build --preset dev-cuda
ctest --preset dev-cuda -L gpu           # the CUDA tests (each skips when no device is visible)
ctest --preset dev-cuda -L cpu           # the CPU suites in the CUDA build

ci/gpu_local.sh                          # the local GPU gate (below)
ci/build_cuda.sh                         # compile-only release build, as cuda-build.yml does

Preset	Use
dev-cuda	development: Debug, native architectures, tests on
release-cuda	the release architecture list (sm_75 to sm_120 SASS plus PTX)
parity-cuda	the flags of MOSP-CUDA (-O3 -lineinfo, sm_86): parity and performance runs
sanitize-cuda	for compute-sanitizer runs
ci-cuda13, ci-cuda12	compile-only builds of .github/workflows/cuda-build.yml (no GPU needed)

DYNG_CUDA_ARCHITECTURES chooses native (the default; without a visible GPU the configure step warns and uses the release list), release or an explicit list (for example -DDYNG_CUDA_ARCHITECTURES=86). ci/gpu_local.sh builds dev-cuda and then runs ctest -L gpu and ctest -L cpu, the sssp golden corpus on the cuda backend (when the goldens exist, see below), compute-sanitizer --tool memcheck over every GPU test executable, --tool synccheck over the CUDA sssp suite and the clang-tidy naming check on the CUDA branches; it prints a Markdown summary and fails when the test GPU is not visible (the CUDA tests would skip). On a shared machine choose the test GPU with DYNG_TEST_GPU (default 1: GPU 0 is kept for timing runs); every heavy step takes the shared lock $DYNG_SCRATCH/perf.lock (DYNG_PERF_LOCK= disables it) and DYNG_GPU_SKIP="memcheck tidy" skips steps by name. ci/gpu_local.sh --preset sanitize-cuda uses another CUDA preset. ci/check.sh takes the same shared lock for its heavy steps.

Run the example

examples/cpp/sssp_update.cpp reads a graph in MOSP's CSR text format, computes a shortest-path tree, applies a batch with sssp::update() and writes the updated tree in MOSP's file format (CTest checks that the file equals the original's output):

case=cpp/tests/data/mosp_graph_io/testCase0
mkdir -p out
build/dev/examples/cpp/sssp_update $case/graphCsr $case/insert.txt $case/delete.txt out openmp
# +0 -1 edges, invalidated 0, affected 2, engine fused   (then the profiler's stage CSV)
cmp out/SSSPTreeUpdated.txt cpp/tests/data/mosp_sssp/testCase0/updated/obj0/SSSPTreeUpdated.txt

In a CUDA build the last argument can be cuda (build/dev-cuda/examples/cpp/sssp_update ... out cuda): the graph and the tree then live on GPU 0 and the fused kernel runs the update, with the same output file.

examples/cpp/cycle_count_update.cpp counts the directed cycles of length 2..k of an edge-list graph (a TUDataset *_A.txt file loads directly), applies a generated batch with cycle_count::update() and prints the histogram in CycleEnumeration-GPU's CSV format; dyng-compat-cycle-enum reproduces the original cycle-enum CLI.

Run the parity check

The parity harness (parity/README.md) builds the pinned originals MOSP-OpenMP@c352151 and MOSP-CUDA@e220ee2 from git archive copies in $DYNG_SCRATCH, exports their golden outputs (495 cases, about 185 MB, outside the repository) and replays them against dynG byte for byte on every backend:

git clone https://github.com/SMShovan/MOSP-OpenMP.git ~/Projects/MOSP-OpenMP   # the originals, once
git clone https://github.com/SMShovan/MOSP-CUDA.git ~/Projects/MOSP-CUDA
parity/build_reference.sh MOSP-OpenMP    # scratch copy of the pinned original, built
parity/build_reference.sh MOSP-CUDA      # the CUDA original (needs nvcc)
parity/export_goldens.py                 # the sssp golden corpus in $DYNG_SCRATCH/goldens
ci/check.sh --parity                     # the gate plus `ctest --preset parity -L parity` (CPU)
cmake --preset parity-cuda && cmake --build --preset parity-cuda
parity/compare.py --exe build/parity-cuda/tools/compat/dyng-compat-mosp --configs cuda

cycle_count has its own corpus from CycleEnumeration-GPU@0a976ad (parity/build_reference.sh CycleEnumeration-GPU, parity/export_goldens.py cycle_count, replayed by parity/compare.py cycle_count; see parity/README.md).

parity/perf_ab.py runs the performance A/B against the unpatched originals under the exclusive perf lock (parity/README.md). The committed records are the M1a, M1b, M2a and M2b parity certificates.

Using the library from C++

find_package(dyng 0.3 REQUIRED)
target_link_libraries(my_app PRIVATE dyng::dyng)

The quickstart is a complete program. With resources::cuda() the graph and the tree live in device memory: read the results with dyng::to_vector(res, tree.distances()), as the quickstart does. examples/cpp/sssp_update.cpp runs the same steps on MOSP's text files, and dyng-compat-mosp (tools/compat, built by the dev and parity presets and their CUDA twins) reproduces the output files of MOSP's mosp driver for parity runs.

How to cite

If you use dynG in academic work, please cite the software (CITATION.cff; GitHub shows a "Cite this repository" button) and the paper behind each algorithm you use. dyng::citation("sssp") returns the BibTeX; the entries live in docs/references.bib.

If you use	Please also cite
sssp, mosp	DynaMOSP (IPDPS 2025) and its journal version (IEEE TPDS 2025)
cycle_count	TruCy / DynTruCy (IEEE Transactions on Computers, submitted)
triad_count, the ESCHER hypergraph storage	ESCHER (IPDPS 2026) and ESCHER+ (IEEE TKDE 2026)
label_propagation	DynLP (ACM ICS 2026)
hyper_sssp	H-SOSP (IA3 workshop at SC 2026)

License

dynG is licensed under the Apache License 2.0. Redistributions must keep the attribution notices in NOTICE (Apache-2.0 section 4(d)).

Acknowledgements

dynG grew out of doctoral research at the Missouri University of Science and Technology, advised by Prof. Sajal K. Das, with the co-authors listed in AUTHORS.md.

Contributing

See CONTRIBUTING.md, GOVERNANCE.md, MAINTAINERS.md, the Code of Conduct, SUPPORT.md and SECURITY.md. Design decisions are recorded as ADRs in docs/adr/.