dynG#

dynamic graph and hypergraph updates on GPUs

dynG is a C++17/CUDA library with a Python package 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. Every algorithm follows one update model, the template of The update model, and has the same two verbs: compute() for the static result and update() for a batch. Each port is proved equal to the pinned original research code by a parity harness.

Warning

Alpha: 0.2.0. The latest release is 0.2.0 (pip install dyng; see the Roadmap): sssp, cycle_count and mosp are stable (SemVer applies from 0.1.0; to mosp from 0.2.0), the teaching algorithms dynamic_bfs and triangle_delta have the maturity tutorial (written for Your first dynamic algorithm), and the CUDA plugin wheels are on PyPI too (pip install "dyng[cu13]" / "dyng[cu12]", Install). The other algorithms of the table are planned for later releases.

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 (ESCHER store)	aggregate delta	sequential, OpenMP, CUDA	planned (0.3)	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)

The Algorithms page explains the columns; the Roadmap says what each release will contain.

Install#

pip install dyng                       # the Python package (CPU backends), from PyPI
pip install "dyng[cu13]"               # with the CUDA plugin (cu12 for CUDA 12 drivers)
pip install -U "dyng[cu13]"            # upgrading from 0.1.0 (without -U pip keeps 0.1.0)

or build from source (the C++ library, the CUDA backend, the development tools):

git clone https://github.com/dyng-dev/dyng.git
cd dyng
conda env create -f environment.yml    # the pinned tools: CMake, Ninja, clang-format, Doxygen, Sphinx
source scripts/dev_env.sh              # activates the environment
cmake --preset dev && cmake --build --preset dev && ctest --preset dev
pip install -e . --no-build-isolation -Ceditable.rebuild=true -Cbuild-dir=build   # Python

Install has the requirements, the presets and how to use dynG from your own CMake project.

A first update#

In Python (A first update in Python):

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)

In C++, from examples/cpp/first_update.cpp, which CTest builds and runs (A first update in C++):

auto res = backend == "sequential" ? dyng::resources::sequential()
           : backend == "cuda"     ? dyng::resources::cuda()
                                   : dyng::resources::openmp();

dyng::edge_list<std::int32_t, std::int32_t> edges;
edges.num_vertices = 4;
edges.num_weights = 1;
edges.add_edge(0, 1, {4});
edges.add_edge(0, 2, {1});
edges.add_edge(2, 1, {2});
edges.add_edge(1, 3, {1});
auto g = dyng::graph<>::from_edges(res, edges.view());  // int32 ids, offsets and weights

auto tree = dyng::sssp::compute(res, g, /*source=*/0);  // canonical tree: lowest-id ties

dyng::edge_batch<std::int32_t, std::int32_t> batch;
batch.delete_edge(2, 1);
batch.insert_edge(2, 3, {1});
dyng::sssp::stats st = dyng::sssp::update(res, g, batch.view(), tree);  // applies the batch

How to cite#

If you use dynG in academic work, please cite the software and the paper behind each algorithm you use. How to cite has the BibTeX entries (from docs/references.bib, the same entries that dyng::citation() and dyng.citation() return) and the CITATION.cff record that GitHub’s “Cite this repository” button uses.

Contents#

Getting started

Getting started

Tutorials

Tutorials

How-to guides

How-to guides

Explanation

Explanation

Reference

History

History

Developer

Project

dynG is licensed under the Apache License 2.0 and is not affiliated with Gunrock or RAPIDS, whose designs inspired it.