Algorithms#

Every algorithm has the same public shape: a header <dyng/<algo>.hpp> with options, result, stats, compute() and update() (ADR 0006), a sequential reference backend, and a page here with the same nine sections (problem, template mapping, API, backends and determinism, performance, limitations, differences from the paper, mapping from the original code, how to cite).

Algorithm	Computes	Container	Family	Backends	Maturity	Release
sssp: dynamic single-source shortest paths	dynamic single-source shortest paths	graph	fixed point	sequential, OpenMP, CUDA	stable	0.1
cycle_count: exact k-bounded directed simple-cycle histograms	k-bounded directed simple-cycle histograms	graph	aggregate delta	sequential, OpenMP, CUDA	stable	0.1
mosp: dynamic multi-objective shortest paths	multi-objective shortest paths	graph	fixed point	sequential, OpenMP, CUDA	stable	0.2
dynamic_bfs: BFS levels under edge batches (tutorial)	BFS hop levels from a source (teaching material)	graph	fixed point	sequential, OpenMP, CUDA	tutorial	0.2
triangle_delta: the triangle count under edge batches (tutorial)	the triangle count of an undirected graph (teaching material)	graph	aggregate delta	sequential, OpenMP, CUDA	tutorial	0.2
`triad_count`	hypergraph h-motif triad counts	hypergraph (ESCHER store)	aggregate delta	sequential, OpenMP, CUDA	planned	0.3
`label_propagation`	binary harmonic label propagation under vertex batches	graph	fixed point	sequential, CUDA	planned	0.4
`hyper_sssp`	shortest hyperpaths	hypergraph	fixed point	sequential, CUDA	planned	0.4

Columns:

Family: fixed point (a value per element, iterated until nothing changes) or aggregate delta (a global count, updated by one signed recount); see The update model.
Maturity: experimental (may change in any release), stable (SemVer applies from the release that made it stable: 0.1.0 for sssp and cycle_count, 0.2.0 for mosp), tutorial (teaching material for contributors, covered like experimental; not a research algorithm: dynamic_bfs: BFS levels under edge batches (tutorial) and triangle_delta: the triangle count under edge batches (tutorial), the subjects of Your first dynamic algorithm), planned (not written yet). A planned algorithm gets its page when its port starts.
Release: the first release that contains it (Roadmap).

The table is generated from each algorithm’s manifest.toml (and cpp/src/algorithms/planned.toml for the planned ones) by scripts/regen.py, like the README’s and the landing page’s; CI checks that it is up to date (python3 scripts/regen.py --check).