dynamic_bfs#

BFS hop levels from a source (teaching material). The algorithm page is dynamic_bfs: BFS levels under edge batches (tutorial).

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

Compute the result of g (the static solve, the oracle of update()).

Synchronization:: Blocks until the work has completed (synchronous).
Backends:: sequential, openmp, cuda
Determinism:: Exact: identical levels on every backend and run.
Paper:: None: teaching material (the tutorial “Your first dynamic algorithm”).
Exception safety:: Strong: g is not modified, and nothing is kept if the call throws.

Template Parameters:

vertex_t – Vertex id type.
edge_t – Edge offset type.
weight_t – Weight type (ignored).

Parameters:

res – [in] Execution resources (sequential, openmp, cuda).
g – [in] The graph, with its in-edges stored (graph_properties::store_transposed, the default); placed as res (host storage for the host backends, a graph built with CUDA resources for cuda); it is not modified.
opt – [in] Options.

Throws:

invalid_argument_error – if the source is not a vertex of g, g does not store its in-edges, or the placement of g does not match res.
not_supported_error – if the backend of res is not available for dynamic_bfs.
out_of_memory_error – if memory cannot be allocated.

Returns:

The result, matching g.version().

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

Apply a batch of edge changes to g and update r.

Postcondition: r equals compute(res, g, r.get_options()) exactly.

Synchronization:: Blocks until the work has completed (synchronous).
Backends:: sequential, openmp, cuda
Determinism:: Exact: identical levels and deterministic counters on every backend and run.
Paper:: None: teaching material (the tutorial “Your first dynamic algorithm”).
Exception safety:: Strong for every error found before the batch is applied (g and r unchanged); basic after the commit (g updated, r poisoned until it is recomputed).

Template Parameters:

vertex_t – Vertex id type.
edge_t – Edge offset type.
weight_t – Weight type (ignored).

Parameters:

res – [in] Execution resources (sequential, openmp, cuda).
g – [inout] The graph; the batch is applied to it and its version increases by one.
batch – [in] Insertions and deletions (weights are ignored).
r – [inout] Result of compute() or of a previous update() on g.

Throws:

stale_result_error – if r.graph_version() != g.version() or r belongs to another graph.
invalid_argument_error – if a batch id or weight is invalid (nothing is changed).
not_supported_error – if the backend of res is not available for dynamic_bfs.
out_of_memory_error – if memory cannot be allocated.

Returns:

Counters of this update.

DYNG_DYNAMIC_BFS_TYPES_MESSAGE#: The message of dynamic_bfs’s static_assert for an unsupported graph type.

struct options#

#include <dyng/dynamic_bfs.hpp>

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

Public Members

std::int64_t source = 0#: The source vertex. Fixed at compute().

struct stats : public dyng::update_stats #

#include <dyng/dynamic_bfs.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 invalidated (the subtrees below the deleted tree edges).

std::int64_t invalidation_rounds = 0#: Deterministic: passes of the invalidation (the roots, then one per tree level below them; 0 without deletions).

class result#

#include <dyng/dynamic_bfs.hpp>

The result kept up to date by update() (opaque, move-only).

The result owns its levels and its BFS tree (host memory for the sequential and OpenMP backends, device memory for cuda), its options and the graph version it matches.

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 values

array_view<const std::int64_t> levels() const#

The hop levels.

Throws:

invalid_argument_error – for a moved-from result.
stale_result_error – if a failed update left the result unusable (poisoned).

Returns:

One level per vertex (in the memory space(): device memory for a result of the cuda backend), -1 for the vertices the source does not reach. Valid until the next update() of this result.

const options &get_options() const#

The options.

Throws:

invalid_argument_error – for a moved-from result.
stale_result_error – if a failed update left the result unusable (poisoned).

Returns:

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

void set_options(const options &opt)#

Change the tunables.

Parameters:

opt – [in] The new options; the ones fixed at compute() must stay the same.

Throws:

invalid_argument_error – if a fixed option differs, or for a moved-from result.
stale_result_error – if a failed update left the result unusable (poisoned).

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

Returns:: memory_space::host for the sequential and OpenMP backends, memory_space::device for cuda.

result clone(const resources &res) const#

A deep copy for the resources res.

Synchronization:: Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources of the copy.

Throws:

invalid_argument_error – for a moved-from result.
stale_result_error – if a failed update left the result unusable (poisoned).
not_supported_error – if the backend of res is not available for dynamic_bfs.
out_of_memory_error – if the copy cannot be allocated.

Returns:

The copy.