cycle_count#

Exact k-bounded directed simple-cycle histograms and their dynamic update (TruCy / DynTruCy). The algorithm page is cycle_count: exact k-bounded directed simple-cycle histograms.

enum class dyng::cycle_count::search_method : std::uint8_t#

The search of compute().

Values:

enumerator johnson#

Johnson’s circuit search from each root (the smallest vertex of its cycles).

enum class dyng::cycle_count::cycle_mode : std::uint8_t#

Which cycles are counted.

Values:

enumerator simple#

static directed simple cycles (time-window and temporal cycles follow in 0.5)

enum class dyng::cycle_count::cuda_scheduler : std::uint8_t#

How the CUDA backend schedules the static count (CycleEnumeration-GPU’s --cuda-scheduler).

Values:

enumerator work_queue#

a resident grid claims work items from a global counter (the default)

enumerator naive#

one thread per root vertex (for debugging and parity checks)

enum class dyng::cycle_count::cuda_work_items : std::uint8_t#

The work items of the work-queue scheduler (CycleEnumeration-GPU’s --cuda-work-items).

Every item is a path prefix from the smallest vertex of the cycles it counts; every cycle has exactly one prefix of each kind, so the choice never changes the counts, only the balance of the search trees over the device.

Values:

enumerator automatic#

edges up to k = 3 and at k = 4 below 16 edges per vertex, two-hop otherwise

enumerator roots#

one item per root vertex

enumerator edges#

one item per edge r -> v1 with v1 > r

enumerator two_hop#

one item per path r -> v1 -> v2 (v1, v2 > r), numbered implicitly

std::string_view dyng::cycle_count::to_string(search_method m) noexcept#

The lower-case name of a search method (“johnson”).

Parameters:

m – [in] The method.

Returns:

A static string naming m (the enumerator’s name).

std::string_view dyng::cycle_count::to_string(cycle_mode m) noexcept#

The lower-case name of a cycle mode (“simple”).

Parameters:

m – [in] The mode.

Returns:

A static string naming m (the enumerator’s name).

std::string_view dyng::cycle_count::to_string(cuda_scheduler s) noexcept#

The lower-case name of a CUDA scheduler (“work_queue”, “naive”).

Parameters:

s – [in] The scheduler.

Returns:

A static string naming s (the enumerator’s name).

std::string_view dyng::cycle_count::to_string(cuda_work_items w) noexcept#

The lower-case name of a work-item kind (“automatic”, “roots”, “edges”, “two_hop”).

Parameters:

w – [in] The kind.

Returns:

A static string naming w (the enumerator’s name).

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

Count the directed simple cycles of g by length (the static solve).

Every cycle is counted once, from its smallest vertex as the root: the search from a root extends paths through larger vertices only and counts a cycle whenever an edge closes back to the root. The sequential backend is CycleEnumeration-GPU’s sequential Johnson (path-membership blocking with a bound, Johnson’s blocked lists without one), the OpenMP backend its OpenMP counter (roots in parallel, dynamic schedule, one histogram per thread), the CUDA backend its work-queue counter (a resident grid claims edge or two-hop prefix items, options::work_items; options::scheduler naive: one thread per root) on the resident device graph.

Synchronization:

Blocks until the work has completed (synchronous). The histogram is complete on return (a host array on every backend).

Backends:

sequential, openmp, cuda

Determinism:

Exact values: identical histograms on every backend and thread count.

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:

TruCy / DynTruCy (submitted to IEEE Transactions on Computers): dyng::citation("cycle_count"), key trucy2026 in docs/references.bib. Exact counts; the kappa-truncated search of the paper is not implemented.

Template Parameters:

  • vertex_t – Vertex id type (int32_t).

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

  • weight_t – Weight type (unweighted or int32_t; weights are ignored).

Parameters:

  • res – [in] Execution resources.

  • g – [in] The graph (sorted rows, no parallel edges); it is not modified (on cuda its device copy is uploaded if it is not resident).

  • opt – [in] Options.

Throws:
Returns:

The histogram, matching g.version().

template<typename vertex_t, typename edge_t, typename weight_t>
stats dyng::cycle_count::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 the histogram r.

The batch is reduced to its net structural change (see cycle_count), the cycles through the deleted edges are subtracted on the graph before the batch, the batch is applied once, and the cycles through the inserted edges are added on the graph after it; each affected cycle is attributed to exactly one change edge (the smallest id on it among its phase’s changes). Postcondition: r equals compute(res, g, r.get_options()) exactly. Without a bound the update enumerates every simple path from each change edge’s head back to its tail, which can take exponential time even when few cycles close (see options::max_length); its bookkeeping costs what the searches find, not the vertex count.

Synchronization:

Blocks until the work has completed (synchronous). The graph and the histogram are updated on return.

Backends:

sequential, openmp, cuda

Determinism:

Exact values: identical histograms and counters on every backend and thread count.

Exception safety:

Strong for every error found before the batch is applied (the ones marked “nothing is

changed” above, and allocation failures of the normalization):

g and r are unchanged. Basic for an error after the commit (a negative bucket, a count past 2^64 - 1 in the merge, a CUDA or allocation failure): g holds the new version and r is poisoned, so every later use of it throws stale_result_error until it is recomputed.

Paper:

TruCy / DynTruCy (submitted to IEEE Transactions on Computers): dyng::citation("cycle_count"), key trucy2026 in docs/references.bib.

Template Parameters:

  • vertex_t – Vertex id type (int32_t).

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

  • weight_t – Weight type (unweighted or int32_t).

Parameters:

  • res – [in] Execution resources.

  • g – [inout] The graph; the batch is applied to it and its version increases by one (on cuda, under batch_semantics::set() without weight columns, on the resident device copy).

  • batch – [in] Insertions and deletions (host memory, or device memory under the copy policy of res).

  • 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 the batch is invalid for the graph’s batch_semantics, the graph does not have sorted rows or allows parallel edges, g belongs to another backend than res, or on cuda the effective bound after the batch (with every vertex the batch names) would exceed 64 (nothing is changed).

  • not_supported_error – if the backend of res is not available for cycle_count, or options::cuda_engine is engine::operators on cuda (nothing is changed).

  • internal_error – if a bucket would become negative (then the graph was updated and r is left unusable).

  • capacity_error – if a count exceeds 2^64 - 1 (host backends, and on cuda the host-side merge of the two phases; the per-length device sums of a phase wrap at 2^64 as the original’s do; raised after the batch was applied, it leaves r unusable), or if on cuda the normalized batch has 0x7f7f7f7f (2,139,062,143) or more deletions or insertions, the limit of the backend’s 32-bit change ids (nothing is changed).

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

  • cuda_error – if the CUDA runtime reports an error.

Returns:

Counters of this update (all deterministic).

DYNG_CYCLE_COUNT_TYPES_MESSAGE#

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

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

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

max_length, method and mode are fixed at compute() (the histogram counts the cycles they define). cuda_engine, scheduler and work_items are tunables: they choose how the cuda backend searches, never what it counts, and result::set_options() changes them.

Public Members

int max_length = -1#

Longest counted cycle, >= 2; or -1 for no bound (every simple cycle, however long; the default, as the original’s). update() keeps the bound of compute(). A bound above the vertex count costs nothing extra (no simple cycle is longer than n).

Cost without a bound: only compute() on the sequential backend is Johnson’s algorithm (blocked lists; time O((n + m)(c + 1)) for c cycles). compute() on the openmp backend (the original’s OpenMP counter) and update() on every backend enumerate simple paths (from each root, and through each change edge), so their time grows with the number of simple paths, exponentially even on graphs with few or no cycles (a layered DAG). For an unbounded count of a large sparse graph use the sequential backend, or set a bound. The searches keep their paths on explicit stacks: a long path costs memory, never the thread’s stack.

On the cuda backend the searches keep their paths in thread-local arrays of at most 64 vertices: the effective bound min(max_length, n) (min(-1 -> n, n) without a bound) must be at most 64, or compute() and update() throw invalid_argument_error (a bound above 64 is accepted while the graph has at most 64 vertices, as the original’s). As in the original, compute() of a graph without edges returns the zero histogram before it checks the bound; update() checks it on every batch. Fixed at compute().

search_method method = search_method::johnson#

the search (Johnson); fixed at compute()

cycle_mode mode = cycle_mode::simple#

the cycles counted (simple); fixed at compute()

engine cuda_engine = engine::automatic#

The CUDA engine: automatic and fused select the fused kernels (the work queue of the static count, the per-change searches of the update: the Tier B engine of docs/developer/framework.md); operators throws not_supported_error (cycle_count has no operators engine in 0.1). Ignored on the host backends. A tunable (result::set_options()).

cuda_scheduler scheduler = cuda_scheduler::work_queue#

The scheduler of the static count on the cuda backend (ignored elsewhere). A tunable.

cuda_work_items work_items = cuda_work_items::automatic#

The work items of the work-queue scheduler (ignored elsewhere). A tunable.

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

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

Every counter is deterministic for cycle_count (identical on every backend, thread count and run), including the two that update_stats calls schedule-dependent, because the update has no iterative loop. The inherited fields mean:

Public Members

apply_summary batch#

What applying the batch did to the graph.

std::int64_t deletions = 0#

Edges of the net structural change that were deleted (the change edges of count_minus).

std::int64_t insertions = 0#

Edges of the net structural change that were inserted (the change edges of count_plus).

std::uint64_t cycles_removed = 0#

Cycles of length <= the bound that the batch destroyed (subtracted on G_t).

std::uint64_t cycles_added = 0#

Cycles of length <= the bound that the batch created (added on G_{t+1}).

class result#
#include <dyng/cycle_count.hpp>

A cycle histogram kept up to date by update() (opaque, move-only).

counts()[len] is the number of directed simple cycles of length len; entries 0 and 1 are always 0. The array has bound() + 1 entries, bound() = min(k, max(num_vertices, 2)) for options::max_length = k, max(num_vertices, 2) without a bound: no simple cycle is longer than the vertex count, so the lengths past it (up to k) are not stored and count() returns 0 for them. The array grows with the graph. Counts are 64-bit; on the host backends a count that would exceed 2^64 - 1 throws capacity_error. On cuda the per-length sums on the device wrap at 2^64, as the original’s do; only the host-side merge of an update’s two phases into the histogram is checked (more than 10^19 cycles of one length: not reachable in practice). The scratch memory of the engines is leased from the resources handle (ADR 0015), not owned.

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

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 histogram

array_view<const std::uint64_t> counts() const#

The histogram.

Throws:
Returns:

counts[len] = cycles of length len (host memory), size bound() + 1. Valid until the next update() of this result.

std::uint64_t count(std::int64_t length) const#

The number of cycles of one length.

Parameters:

length – [in] A cycle length (any value; lengths outside [2, bound()] give 0).

Throws:
Returns:

The count.

std::uint64_t total() const#

The number of cycles of every counted length.

Throws:
Returns:

The sum of counts().

std::int64_t bound() const#

The longest length the histogram covers.

Throws:
Returns:

min(options::max_length, max(num_vertices, 2)), or without a bound max(num_vertices, 2), of the graph the result matches (get_options().max_length is the requested bound).

const options &get_options() const#

The options.

Throws:
Returns:

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

void set_options(const options &opt)#

Change the tunables (cuda_engine, scheduler, work_items); the next update() uses them.

Exception safety:

Strong: every check runs before the options change.

Parameters:

opt – [in] The new options; max_length, method and mode must stay the same.

Throws:

  • invalid_argument_error – if opt.max_length, opt.method or opt.mode differs from the result’s, a field holds an invalid value, 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 histogram.

Returns:

memory_space::host (on every backend).

result clone(const resources &res) const#

A deep copy for the resources res (the histogram is a host array on every backend).

Synchronization:

Blocks until the work has completed (synchronous). The copy is complete on return (host memory on every backend).

Parameters:

res – [in] Execution resources of the copy (any backend).

Throws:
Returns:

The copy.