triangle_delta#

the triangle count of an undirected graph (teaching material). The algorithm page is triangle_delta: the triangle count under edge batches (tutorial).

template<typename vertex_t, typename edge_t, typename weight_t> result dyng::triangle_delta::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 counts 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: undirected (graph_properties::directed = false), sorted rows, no parallel edges; 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 g is directed, has unsorted rows or allows parallel edges, or its placement does not match res.
not_supported_error – if the backend of res is not available for triangle_delta.
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::triangle_delta::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 counts and 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 (an undirected graph changes both directions of every batch edge; 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 triangle_delta.
out_of_memory_error – if memory cannot be allocated.

Returns:

Counters of this update.

DYNG_TRIANGLE_DELTA_TYPES_MESSAGE#: The message of triangle_delta’s static_assert for an unsupported graph type.

struct options#: #include <dyng/triangle_delta.hpp>

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

struct stats : public dyng::update_stats #

#include <dyng/triangle_delta.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 deletions = 0#: Deterministic: undirected edges the batch removed (the change list of count(-)).

std::int64_t insertions = 0#: Deterministic: undirected edges the batch added (the change list of count(+)).

std::uint64_t triangles_removed = 0#: Deterministic: triangles the batch destroyed.

std::uint64_t triangles_added = 0#: Deterministic: triangles the batch created.

class result#

#include <dyng/triangle_delta.hpp>

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

The result owns its values (host memory), 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

std::uint64_t count() const#

The triangle count.

Throws:

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

Returns:

The number of triangles of the graph (host memory on every backend).

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

Returns:: memory_space::host.

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 triangle_delta.
out_of_memory_error – if the copy cannot be allocated.

Returns:

The copy.