mosp#

Dynamic multi-objective shortest paths. The algorithm page is mosp: dynamic multi-objective shortest paths.

constexpr int dyng::mosp::max_objectives = 64#

The largest number of objectives (weight columns used); MOSP’s originals allow 32.

A later release may raise the limit (a relaxation: every call accepted before is still accepted); it never lowers it.

constexpr std::int64_t dyng::mosp::max_preference_scale = std::int64_t{1} << 20#

The largest preference scale L = lcm(Pref) (MOSP’s preferenceScale limit, 2^20).

As for max_objectives, a later release may raise the limit but never lowers it.

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

Compute the K canonical shortest-path trees of g from source, the combined graph, its shortest-path tree (the MOSP tree) and the path costs (the static solve).

The K trees are sssp::compute() of the objectives; the combined graph is built from their parents and solved with the same engine (the original’s Steps 2-3).

Synchronization:

Blocks until the work has completed (synchronous).

Backends:

sequential, openmp, cuda

Determinism:

Bit-exact across backends and runs (every tree canonical, lowest-id ties).

Exception safety:

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

Paper:

DynaMOSP (IPDPS 2025; IEEE TPDS 2025): dyng::citation("mosp"), 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; every 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, at least one weight column; 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 is out of range, the options are invalid (a preference below 1, not one preference per objective (or none), lcm above max_preference_scale, num_objectives out of [0, num_weights], more than max_objectives objectives, a negative delta), a weight is below 1, the graph stores no in-edges or has no weight column, 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.

  • 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::mosp::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 K trees, the MOSP tree and the path costs of r.

The batch is applied once (under g.properties().semantics; graph_properties:: mosp_compatible() reproduces MOSP’s applyChangeBatch()). The K objectives are updated by sssp one after the other (stage mosp.objective around each, its sssp.* stages inside), then the combined graph is rebuilt (mosp.combine), solved (mosp.combined_sssp) and the path costs are recomputed (mosp.path_costs). Postcondition: r equals compute(res, g, r.source(), r.get_options()) exactly if its trees were canonical (from compute(), or from_arrays() with canonicalize = true); otherwise as sssp’s tie rule describes for each tree, and the MOSP tree is the canonical tree of the combined graph of the K updated trees.

Synchronization:

Blocks until the work has completed (synchronous).

Backends:

sequential, openmp, cuda

Determinism:

Bit-exact across backends and runs (trees, combined arrays, path costs, affected, combined_edges and the objectives’ deterministic counters), except for non-canonical imported trees inside sssp’s packing window, where the K trees (and so the combined arrays and path costs) 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; basic after the commit (g holds the new version and r is poisoned until it is recomputed).

Paper:

DynaMOSP (IPDPS 2025; IEEE TPDS 2025): dyng::citation("mosp").

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.

Parameters:

  • res – [in] Execution resources (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 (with the graph’s number of weights each), deletions and weight changes (any memory space; read on the host in this release).

  • 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 r was left unusable by a failed update.

  • invalid_argument_error – if a batch id or weight is invalid or the batch has insertions with another number of weights than the graph (a batch without insertions is accepted whatever its number of weights), 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, for trees imported without validation, as sssp::update() (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 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 (after the batch was applied, r is left unusable).

Returns:

Counters of this update; affected counts the vertices whose combined distance or MOSP parent changed (deterministic).

DYNG_MOSP_TYPES_MESSAGE#

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

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

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

Public Members

std::vector<std::int32_t> preferences#

One preference per objective, each >= 1 (a lower value is a higher priority); empty = all ones. lcm(preferences) must not exceed max_preference_scale. Fixed at compute().

std::int64_t delta = 0#

Near-far bucket width of the K sssp updates; 0 = automatic per objective (sssp’s rule). The combined solve always uses the automatic width of the combined graph, as the originals do. A tunable: it changes the schedule, never the result.

engine cuda_engine = engine::automatic#

Engine of the CUDA backend for the K sssp updates and the combined solve (see sssp::options::cuda_engine); ignored by the host backends. A tunable.

bool compute_path_costs = true#

Compute the path costs (Step 3’s last line) in compute() and update(). Changeable with result::set_options(), but not a tunable in sssp’s sense: it decides what the result holds. path_costs() throws if it was false at the last compute() or update(); set_options() takes effect at the next update() (costs computed before stay readable until then, and costs are not readable before an update() recomputes them).

bool validate_inputs = true#

O(K n) checks on imported trees in result::from_arrays() (sssp’s checks, per objective).

int num_objectives = 0#

The objectives: the first num_objectives weight columns of the graph; 0 = every column (MOSP’s MospOptions::numberOfObjectives). Fixed at compute().

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

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

The common counters of update_stats mean, for mosp: affected (deterministic) the vertices whose combined distance or MOSP parent changed; iterations and frontier_visits (schedule-dependent) the sums over the K sssp updates and the combined solve; converged (deterministic) true unless an objective’s update reported otherwise; fallback_used (deterministic) true if an objective’s update used a fallback (the combined graph is always solved from scratch, which is the algorithm, not a fallback); engine_used (deterministic per backend) the engine of the K updates (the first objective’s; all K run the same engine).

Public Members

apply_summary batch#

Deterministic: what applying the batch did to the graph.

std::vector<sssp::stats> objectives#

The K sssp updates, in objective order (each counter deterministic or schedule-dependent as sssp::stats documents it).

std::int64_t combined_edges = 0#

Deterministic: edges of the combined graph.

std::int64_t preference_scale = 0#

Deterministic: L = lcm(preferences), the unit of the combined distances is 1/L.

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

The K shortest-path trees, the MOSP tree and the path costs kept up to date by update() (opaque, move-only).

The result owns its arrays (host memory, or device memory for the cuda backend, except the path costs, which are host memory on every backend), its options and the graph version it matches. Like sssp results, it leases the engines’ scratch memory from its resources handle (ADR 0015).

Thread safety. As sssp::result: accessors may run concurrently with each other, not with an update() of the result.

Template Parameters:

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

  • distance_t – Distance type: std::int64_t (as sssp::result).

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).

int num_objectives() const noexcept#

The number of objectives K.

Returns:

K (0 for a moved-from result).

array_view<const distance_t> distances(int objective) const#

The distances of one objective’s tree.

Parameters:

objective – [in] The objective, in [0, num_objectives()).

Throws:
Returns:

One distance per vertex (infinite_distance<distance_t>() if unreachable); device memory for a result of the cuda backend. Valid until the next update().

array_view<const vertex_t> parents(int objective) const#

The parents of one objective’s tree.

Parameters:

objective – [in] The objective, in [0, num_objectives()).

Throws:
Returns:

One parent per vertex, -1 for the source and unreachable vertices; device memory for a result of the cuda backend. Valid until the next update().

array_view<const distance_t> combined_distances() const#

The distances in the combined graph.

Throws:
Returns:

One distance per vertex, in units of 1/L (L = preference_scale()); infinite_distance<distance_t>() if unreachable; device memory for the cuda backend. Valid until the next update().

array_view<const vertex_t> combined_parents() const#

The MOSP tree: the canonical shortest-path tree of the combined graph.

Throws:
Returns:

One parent per vertex, -1 for the source and unreachable vertices; device memory for the cuda backend. Valid until the next update().

array_view<const distance_t> path_costs() const#

The path costs: the K objective values of the MOSP path to every vertex (MOSP’s mospPathCosts: the weights of the tree edge (p, v) are those of the first edge from p to v in the graph’s row order).

Throws:
Returns:

n * K values, vertex-major (costs[v * K + k]); infinite_distance<distance_t>() for unreachable vertices. Host memory on every backend (a later release that computes the costs on the device makes that an appended option, so this accessor keeps returning host memory by default). Valid until the next update().

std::int64_t preference_scale() const noexcept#

The preference scale L = lcm(preferences) (the unit of the combined distances is 1/L).

Returns:

L (0 for a moved-from result).

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 changeable options (the tunables delta and cuda_engine, and compute_path_costs and validate_inputs).

The new options take effect at the next update(); in particular compute_path_costs does not change what path_costs() returns or throws until then.

Exception safety:

Strong: every check runs before the options change, and nothing after the checks allocates.

Parameters:

opt – [in] The new options; preferences and num_objectives 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 trees and the combined arrays.

Returns:

memory_space::device for a result of the cuda backend, memory_space::host otherwise (the path costs are host memory on every backend).

result clone(const resources &res) const#

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

As sssp::result::clone(): the copy belongs to the backend of res, and the K trees’ clones size the pooled sssp workspace of res for the graph.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources of the copy (any backend of mosp: the arrays are copied between host and device memory as needed).

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 array_view<const distance_t>> distances, array_view<const array_view<const vertex_t>> parents, bool canonicalize = true, const options &opt = {})#

Adopt K existing trees of g (e.g. MOSP’s obj<k>/distancesOriginal.txt and SSSPTreeOriginal.txt) and build the combined graph, the MOSP tree and the path costs.

Every tree is imported as sssp::result::from_arrays() imports it (with canonicalize and opt.validate_inputs applied to each); then the combined graph is built from the K trees and solved, as at the end of an update().

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 trees belong to (with in-edges stored).

  • source – [in] The source vertex.

  • distances – [in] K views of n distances (host memory: the list; any memory space: the arrays).

  • parents – [in] K views of n parents, -1 for none.

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

  • opt – [in] Options; K = the number of views, which must equal the objectives the options select (opt.num_objectives, or every weight column).

Throws:
Returns:

The result, matching g.version().