sssp#

Dynamic single-source shortest paths. The algorithm page is sssp: dynamic single-source shortest paths.

template<typename vertex_t, typename edge_t, typename weight_t>
result<vertex_t> dyng::sssp::compute(const resources &res, const graph<vertex_t, edge_t, weight_t> &g, vertex_t source, const options &opt = {})#

Compute the canonical shortest-path tree of g from source (the static solve).

The sequential backend runs the Step 2 loop of the sequential engine from the source; the OpenMP backend runs the near-far search of MOSP-OpenMP’s sospFromScratchCpu(), the cuda backend MOSP-CUDA’s sospFromScratchGpu() (the persistent kernel from the source; with the operators engine, its kernels one by one). All return the Dijkstra tree with lowest-id ties.

Synchronization:

Blocks until the work has completed (synchronous). On cuda with the fused engine the stream is synchronized once (the control block of the kernel is read); with the operators engine (engine::operators, or engine::automatic on a device without cooperative launch) 2 + iterations + epochs times (once after the first split, once per push iteration and threshold raise, once in the finalize step). Once more before that if the graph’s current state is not resident on the device yet (its upload, profiler stage graph.upload, completes before the kernel runs).

Backends:

sequential, openmp, cuda

Determinism:

Bit-exact across backends and runs: the Dijkstra tree with lowest-id ties.

Exception safety:

Strong: g is not modified (on cuda its device copy may be uploaded, which changes no observable state), and nothing is kept if the call throws.

Paper:

DynaMOSP (IPDPS 2025; IEEE TPDS 2025): dyng::citation("sssp"), keys dynamosp2025 and dynamosptpds2025 in docs/references.bib.

Template Parameters:

  • vertex_t – Vertex id type (int32_t or int64_t).

  • edge_t – Edge offset type (int32_t or int64_t).

  • weight_t – Integer weight type; the objective’s weights must lie in [1, 2^31 - 1].

Parameters:

  • res – [in] Execution resources (sequential, openmp or cuda).

  • g – [in] The graph (with in-edges stored; built with, or cloned for, the backend of res); it is not modified.

  • source – [in] The source vertex.

  • opt – [in] Options.

Throws:

  • invalid_argument_error – if the source or the objective is out of range, a weight of the objective is below 1, the graph stores no in-edges, distances could exceed 62 bits, or g belongs to another backend than res.

  • not_supported_error – if the backend of res is not built, or on cuda if the engine of options::cuda_engine cannot run (engine::fused without cooperative launch).

  • out_of_memory_error – if host or device memory cannot be allocated.

  • cuda_error – if the CUDA runtime reports an error (cuda backend).

Returns:

The result, matching g.version().

template<typename vertex_t, typename edge_t, typename weight_t>
stats dyng::sssp::update(const resources &res, graph<vertex_t, edge_t, weight_t> &g, const edge_batch_view<vertex_t, weight_t> &batch, result<vertex_t> &r)#

Apply a batch of edge changes to g and update the shortest-path tree r.

The batch is applied under g.properties().semantics (for graph_properties::mosp_compatible() exactly as MOSP’s applyChangeBatch()). Step 1 invalidates the subtrees below deleted or weight-increased tree edges and pulls each invalidated vertex’s and each insertion head’s best in-neighbour; Step 2 relaxes outward until no distance decreases. Postcondition: the distances of r equal those of compute(res, g, r.source(), r.get_options()), and r is a shortest-path tree of the new graph; if r was canonical before the call (it came from compute(), from from_arrays() with canonicalize = true, or from updates of such a result) it equals that compute() exactly (see the tie rule of sssp for trees adopted with canonicalize = false).

Synchronization:

Blocks until the work has completed (synchronous). On cuda the stream is synchronized once per result with the fused engine (the kernel’s control block is read), or 3 + iterations + epochs times per result with the operators engine (engine::operators, or engine::automatic on a device without cooperative launch: once after identify_affected, once after the first split, once per push iteration and threshold raise, once in the finalize step; ADR 0026), and once per batch inside the commit, where the new graph state is uploaded (profiler stage graph.upload; ADR 0017 item 7).

Backends:

sequential, openmp, cuda

Determinism:

Bit-exact across backends and runs (distances, parents, invalidated, affected), for canonical and non-canonical input trees alike, except the parents and affected of non-canonical input trees inside the packing window, which differ between the host backends and cuda (each as its original; sssp, ADR 0029).

Exception safety:

Strong for every error found before the batch is applied (a stale result, an invalid batch, the wrong backend, an unsupported engine, a copy refused by the copy policy, memory for the normalization): g and r are unchanged. Basic for an error after the commit (only an imported tree that was not validated, a CUDA failure or an allocation failure can cause one): g holds the new version and r is poisoned, so every later use of it throws stale_result_error until it is recomputed.

Paper:

DynaMOSP (IPDPS 2025; IEEE TPDS 2025): dyng::citation("sssp"), keys dynamosp2025 and dynamosptpds2025 in docs/references.bib.

Template Parameters:

  • vertex_t – Vertex id type (int32_t or int64_t).

  • edge_t – Edge offset type (int32_t or int64_t).

  • weight_t – Integer weight type; weights must lie in [1, 2^31 - 1].

Parameters:

  • res – [in] Execution resources (sequential, openmp or cuda; g and r must belong to their backend).

  • g – [inout] The graph; the batch is applied to it and its version increases by one.

  • batch – [in] Insertions (upserts), deletions and weight changes (any memory space: the batch is read on the host in this release, so arrays in device memory are copied once under res.get_copy_policy()).

  • r – [inout] Result of compute() or of a previous update() on g.

Throws:

  • stale_result_error – if r.graph_version() != g.version(), r was computed on another graph (or on an earlier state of a graph variable that was reassigned since), or r was left unusable by a failed update.

  • invalid_argument_error – if a batch id or weight is invalid, g or r belongs to another backend than res, or a batch array must be copied and the copy policy is copy_policy::error (nothing is changed); or, only for a tree imported without validation, if the tree has a parent cycle or (cuda) a distance outside the packing bound (then the graph was updated and r is left unusable).

  • not_supported_error – if the backend of res is not built, or on cuda if the engine of the result’s options::cuda_engine cannot run (nothing is changed).

  • out_of_memory_error – if host or device memory cannot be allocated.

  • cuda_error – if the CUDA runtime reports an error (cuda backend; after the batch was applied, r is left unusable).

Returns:

Counters of this update; invalidated and affected are deterministic, iterations, epochs and pushes are not.

DYNG_SSSP_TYPES_MESSAGE#

The message of sssp’s static_assert for an unsupported graph type.

struct options#
#include <dyng/sssp.hpp>

Options of compute() and update() (an aggregate; fields are only ever appended).

Public Members

std::int64_t delta = 0#

Near-far bucket width; 0 = automatic: max(1, 32 * average weight / average out-degree) of the graph before the batch (MOSP’s defaultDelta). A tunable: it changes the schedule, never the result.

int objective = 0#

Which weight column of a multi-weight graph is the edge length. Fixed at compute().

engine cuda_engine = engine::automatic#

Engine of the CUDA backend; ignored by the host backends. engine::fused runs the fused persistent cooperative kernel (MOSP-CUDA’s sospUpdateGpu) and throws not_supported_error on a device without cooperative launch; engine::operators runs the multi-kernel operators engine (the same bytes, on any device); engine::automatic runs the fused engine where it can and the operators engine otherwise. A tunable: it changes the schedule, never the result.

bool validate_inputs = true#

O(n) checks on imported trees in result::from_arrays() (rooted at the source, no parent cycle, distances in range).

struct stats : public dyng::update_stats#
#include <dyng/sssp.hpp>

Counters of one update() (fields are only ever appended).

Public Members

apply_summary batch#

Deterministic: what applying the batch did to the graph.

std::int64_t invalidated = 0#

Deterministic: vertices in invalidated subtrees (below deleted or weight-increased tree edges).

std::int64_t epochs = 0#

Schedule-dependent: raises of the near-far threshold (0 on the sequential backend).

std::int64_t pushes = 0#

Schedule-dependent: vertex expansions of the Step 2 loop.

bool packed_parents = true#

Deterministic per backend (update_stats): false if distances do not fit next to the parent ids in 64-bit words, so the engine kept distances only and recovered every parent with the lowest-id rule after the search. The sequential engine reports the OpenMP engine’s value and applies the same recovery, so both return the same tree; the CUDA engines use MOSP-CUDA’s slightly larger packing limit, so its value can differ inside the packing window (see sssp, ADR 0029).

template<typename vertex_t, typename distance_t = std::int64_t>
class result#
#include <dyng/sssp.hpp>

A shortest-path tree kept up to date by update() (opaque, move-only).

The result owns its distance and parent arrays (host memory, or device memory for the cuda backend), its options and the graph version it matches. The scratch memory of the engines is not part of it: compute() and update() lease the workspace of the resources handle they run with (sized once, then reused), so results computed and updated through one handle, such as the K objectives of dyng::update_each(), share one workspace as MOSP’s objectives share one, and a steady-state update allocates no scratch memory (ADR 0015). The results stay independent: nothing in the workspace carries over from one run to the next.

Thread safety. A result is not thread-safe: its accessors may run concurrently with each other, but not with an update() of it (or a dyng::update() that includes it), which must also not overlap another call on its graph; see graph, “Thread safety”. On CUDA, reading its device arrays on one stream while another stream updates it is undefined unless the streams are ordered.

Template Parameters:

  • vertex_t – Vertex id type (int32_t or int64_t).

  • distance_t – Distance type: std::int64_t, the only width in 0.1 (the packed (distance, id) words and the engines are 64-bit); the parameter keeps room for a later width, and another value fails to compile.

Public Functions

result(result &&other) noexcept#

Move constructor.

Parameters:

other – [inout] The result to move from; it may only be assigned to or destroyed after.

result &operator=(result &&other) noexcept#

Move assignment.

Parameters:

other – [inout] The result to move from; it may only be assigned to or destroyed after.

Returns:

*this.

result(const result&) = delete#

not copyable: use clone()

result &operator=(const result&) = delete#

not copyable: use clone()

~result()#

releases the arrays

vertex_t source() const noexcept#

The source vertex.

Returns:

The source (invalid_id() for a moved-from result).

array_view<const distance_t> distances() const#

The distances.

Throws:
Returns:

One distance per vertex (host memory; device memory for a result of the cuda backend, see space()); infinite_distance<distance_t>() for vertices that cannot be reached. Valid until the next update() of this result.

array_view<const vertex_t> parents() const#

The parents (the tree).

Throws:
Returns:

One parent per vertex (host memory; device memory for a result of the cuda backend): an in-neighbour on a shortest path, the lowest-id one unless kept from a non-canonical input tree (see the tie rule of sssp); -1 for the source and unreachable vertices. Valid until the next update().

const options &get_options() const#

The options.

Throws:
Returns:

The options given at compute() or from_arrays(), as changed by set_options().

void set_options(const options &opt)#

Change the tunables (delta, cuda_engine, validate_inputs).

Exception safety:

Strong: every check runs before the options change.

Parameters:

opt – [in] The new options; objective must stay the same.

Throws:
std::uint64_t graph_version() const noexcept#

The graph version this result matches.

Returns:

The version of the graph after the last compute() / update() of this result.

memory_space space() const noexcept#

The memory space of the arrays.

Returns:

memory_space::device for a result of the cuda backend, memory_space::host otherwise.

result clone(const resources &res) const#

A deep copy (arrays, options, version) for the resources res.

The copy belongs to the backend of res (its arrays are copied between host and device memory as needed): this is how a result moves between the host backends and cuda. Also sizes the pooled workspace of res for the graph (a no-op if it is large enough), so the first update of the copy through res allocates no scratch memory.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources of the copy.

Throws:
Returns:

The copy.

Public Static Functions

template<typename edge_t, typename weight_t>
static result from_arrays(const resources &res, const graph<vertex_t, edge_t, weight_t> &g, vertex_t source, array_view<const distance_t> distances, array_view<const vertex_t> parents, bool canonicalize = true, const options &opt = {})#

Adopt an existing tree of g (e.g. read from MOSP’s distance and tree files).

With canonicalize, every parent is replaced by the lowest-id in-neighbour u with dist[u] + w(u,v) == dist[v] (MOSP’s canonicalizeTree()), so that later updates produce the canonical tree (equal to compute()). Without it the parents are kept as given, as MOSP’s mosp driver keeps them; later updates then keep the tie parents of the vertices they do not re-evaluate (the tie rule of sssp), identically on every backend except inside the packing window, where the host backends recover every parent with the lowest-id rule and cuda keeps them (each backend as its original; sssp, ADR 0029). With opt.validate_inputs the tree is checked in O(n): array sizes, source at distance 0 without a parent, distances in [0, (n - 1) * max weight] or unreachable (>= infinite_distance() / 2, stored as infinite_distance()), unreachable vertices without a parent, every other vertex with a reachable parent, and no parent cycle (every chain ends at the source); on the OpenMP backend the checks run in parallel and report the same first problem as the sequential ones. The caller guarantees that the tree is a shortest-path tree of g. Also sizes the pooled workspace of res for the graph (once for all results built through res; ADR 0015). The tree is imported and checked in host memory on every backend (on cuda it is then uploaded, profiler stage sssp.upload); the arrays may be in any memory space, and arrays in device memory are copied to the host once under res.get_copy_policy() (host arrays for a cuda result are this function’s own import, not an implicit copy).

Synchronization:

Blocks until the work has completed (synchronous).

Exception safety:

Strong: g and the arrays are not modified, and nothing is kept if the call throws.

Template Parameters:

  • edge_t – Edge offset type of the graph.

  • weight_t – Weight type of the graph.

Parameters:

  • res – [in] Execution resources (the graph must belong to their backend).

  • g – [in] The graph the tree belongs to (with in-edges stored).

  • source – [in] The source vertex.

  • distances – [in] One distance per vertex (any memory space).

  • parents – [in] One parent per vertex, -1 for none (any memory space).

  • canonicalize – [in] Apply the lowest-id tie rule to the parents (default true).

  • opt – [in] Options (objective = the weight column the tree belongs to).

Throws:
Returns:

The result, matching g.version().