Testing oracles

Reference solvers and checkers used by the tests, the parity harness and downstream users (dyng::testing).

enum class dyng::testing::cbst_op_status

How an operation of the model ended.

Values:

enumerator ok

it completed

enumerator error

it failed and the original throws (cbst_op_result::error_type)

enumerator process_exit

it failed and the original ends the process

enumerator undefined

the original’s result is not defined (a race, an out-of-bounds access, an endless chain); the model cannot predict it (cbst_op_result::message)

using dyng::testing::cycle_histogram = std::vector<std::uint64_t>

A cycle histogram: counts[len] is the number of directed simple cycles of length len (entries 0 and 1 are always 0).

std::int64_t dyng::testing::cbst_rank_of_position(std::int64_t position, std::int64_t num_nodes) noexcept

The in-order rank of the node at heap position position of a complete binary search tree with num_nodes nodes (the CBST layout of both originals).

With k = floor(log2(position + 1)) and L = floor(log2(num_nodes)), the rank is min(i, i - i/2 + (num_nodes + 1 - 2^L)) - 1 for i = (2(position + 1 - 2^k) + 1) * 2^(L - k), all in 64 bits.

Parameters:

• position – [in] The heap position, 0 <= position < num_nodes.

• num_nodes – [in] The number of nodes, at least 1.

Returns:

The rank, in [0, num_nodes), or -1 when the arguments are out of range.

cbst_layout_check dyng::testing::check_cbst_layout(std::int64_t num_nodes, bool search_every_key = true)

The layout checks of ESCHER-GPU’s tests/cbst_test.cu on the model’s layout function.

Keys 1..n are placed at their heap positions with row k at offset 4(k - 1); the check counts (1) ranks that do not form a permutation, (2) heap positions whose in-order traversal rank is wrong, (3) keys a BST search from the root does not find (searched for every key when search_every_key, else for a deterministic sample of at most 65,536 keys), (4) found nodes whose offset is not that of the key’s row and (5) positions whose key, recovered by the layout formula, differs from the key stored there.

Parameters:

• num_nodes – [in] The tree size, 1 <= num_nodes <= 2^30.

• search_every_key – [in] Search every key (cost n log n) or a sample.

Returns:

The findings.

template<typename vertex_t, typename edge_t, typename weight_t>
sssp_tree_check dyng::testing::check_sssp_tree(const csr_view<vertex_t, edge_t, weight_t> &out, vertex_t source, array_view<const std::int64_t> distances, array_view<const vertex_t> parents, const check_sssp_options &opt = {})

Check distances and parents of a shortest-path tree (a port of MOSP’s checkSospTree()).

The reference distances (and, in canonical mode, parents) come from dijkstra(). Parent consistency: the source and unreachable vertices have parent -1; every other vertex v has a parent p with an edge (p,v) of positive weight and dist[p] + w(p,v) == dist[v]. Canonical: p is the lowest id among all such in-neighbours. The in-edges are rebuilt from out here, so the check does not rely on the graph’s own transposition.

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• out – [in] The out-edge CSR the tree belongs to (host memory).

• source – [in] The source vertex.

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

• parents – [in] One parent per vertex (host memory).

• opt – [in] Objective and mode.

Throws:

• invalid_argument_error – if the array sizes differ from the vertex count or the objective is out of range.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The findings.

template<typename vertex_t, typename edge_t, typename weight_t>
sssp_tree_check dyng::testing::check_sssp_tree(const graph<vertex_t, edge_t, weight_t> &g, vertex_t source, array_view<const std::int64_t> distances, array_view<const vertex_t> parents, const check_sssp_options &opt = {})

Check a tree of a graph (see the csr_view overload).

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• g – [in] The graph.

• source – [in] The source vertex.

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

• parents – [in] One parent per vertex (host memory).

• opt – [in] Objective and mode.

Throws:

• invalid_argument_error – on size or objective mismatches.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The findings.

template<typename vertex_t, typename edge_t, typename weight_t>
sssp_tree_check dyng::testing::check_sssp_tree(const graph<vertex_t, edge_t, weight_t> &g, const sssp::result<vertex_t> &r, bool require_canonical = true)

Check an sssp result against its graph (source and objective taken from the result).

A result of the CUDA backend (device arrays) is copied to the host first.

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• g – [in] The graph the result matches.

• r – [in] The result.

• require_canonical – [in] Parents must be the lowest-id tight in-neighbours.

Throws:

• invalid_argument_error – on size mismatches or a moved-from result.

• out_of_memory_error – if host memory cannot be allocated.

• cuda_error – if a device result cannot be copied.

Returns:

The findings.

template<typename vertex_t, typename edge_t, typename weight_t>
cycle_histogram dyng::testing::oracle_simple_cycles(const csr_view<vertex_t, edge_t, weight_t> &graph, int max_length = -1)

Directed simple cycles by length, each counted once, by a dynamic program over vertex subsets (CycleEnumeration-GPU’s oracle_simple_cycles).

For every start vertex s the program counts simple paths s -> … -> v over vertex subsets whose other members are all greater than s, and closes them with an edge v -> s; each cycle is produced once, from its minimum vertex. Self-loops and repeated neighbours are ignored; 2-cycles (u -> v -> u) count.

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type (ignored).

Parameters:

• graph – [in] The out-edge CSR (host memory), at most 16 vertices.

• max_length – [in] Longest counted cycle (>= 2), or -1 for no bound.

Throws:

• invalid_argument_error – if the graph has more than 16 vertices, max_length is neither -1 nor >= 2, or the view is not on the host.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The histogram, of size max_length + 1 (no bound: max(num_vertices, 2) + 1).

template<typename vertex_t, typename edge_t, typename weight_t>
cycle_histogram dyng::testing::brute_force_simple_cycles(const csr_view<vertex_t, edge_t, weight_t> &graph, int max_length = -1)

Directed simple cycles by length by exhaustive DFS (CycleEnumeration-GPU’s count_simple_cycles_bruteforce): a cycle is counted from its minimum vertex as the root.

Every row entry is followed, so a graph with parallel edges counts a cycle once per choice of parallel edges (a simple graph, e.g. under multi_edges::forbid, counts each cycle once).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type (ignored).

Parameters:

• graph – [in] The out-edge CSR (host memory).

• max_length – [in] Longest counted cycle (>= 2), or -1 for no bound.

Throws:

• invalid_argument_error – if max_length is neither -1 nor >= 2 or the view is not on the host.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The histogram, of size max_length + 1 (no bound: max(num_vertices, 2) + 1).

template<typename vertex_t, typename edge_t, typename weight_t>
csr<vertex_t, edge_t, weight_t> dyng::testing::edge_set_after_batch(const csr_view<vertex_t, edge_t, weight_t> &graph, const edge_batch_view<vertex_t, weight_t> &batch)

The edge set after a batch, computed without the library’s apply: (E minus Del) plus Ins, self-loop insertions ignored, the vertex count grown to the largest inserted id + 1 (the reference graph of CycleEnumeration-GPU’s arbitrary-batch tests).

Deletions are applied before insertions, both as sets. The result has sorted rows without repeats and no weight columns.

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type (ignored).

Parameters:

• graph – [in] The out-edge CSR before the batch (host memory).

• batch – [in] The batch (host memory; ids >= 0).

Throws:

• invalid_argument_error – if an id is negative or an array is not on the host.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The out-edge CSR after the batch.

template<typename vertex_t, typename edge_t, typename weight_t>
sssp_tree<vertex_t> dyng::testing::dijkstra(const csr_view<vertex_t, edge_t, weight_t> &out, vertex_t source, int objective = 0)

Dijkstra from source with ties broken towards the lowest parent id (the canonical tree); a port of MOSP’s dijkstraCsrGraph().

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• out – [in] The out-edge CSR (host memory, objective-major weights, weights >= 1).

• source – [in] The source vertex.

• objective – [in] The weight column.

Throws:

• invalid_argument_error – if objective is out of range or the view is not on the host.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The canonical tree; all vertices unreachable if source is out of range.

template<typename vertex_t, typename edge_t, typename weight_t>
sssp_tree<vertex_t> dyng::testing::dijkstra(const graph<vertex_t, edge_t, weight_t> &g, vertex_t source, int objective = 0)

Dijkstra on a graph’s out-edges (see the csr_view overload).

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• g – [in] The graph (host storage).

• source – [in] The source vertex.

• objective – [in] The weight column.

Throws:

• invalid_argument_error – if objective is out of range.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The canonical tree.

line_graph_rows dyng::testing::rebuild_line_graph(const std::vector<std::int64_t> &h2v_offsets, const std::vector<std::int32_t> &h2v_members, std::int32_t num_vertices)

The line graph of a hypergraph, rebuilt from its hyperedges (MOSP_ESCHER’s rebuildLineGraph).

A hyperedge with an empty row is dead: it has an empty line-graph row and is nobody’s neighbour. Repeated members of a row count once.

Parameters:

• h2v_offsets – [in] The hyperedges by id: id i has the members h2v_members[h2v_offsets[i] .. h2v_offsets[i + 1]) (the layout of hypergraph::h2v() copied to the host).

• h2v_members – [in] The members, in [0, num_vertices).

• num_vertices – [in] Vertices.

Throws:

• std::invalid_argument – for malformed offsets or a member out of range.

• std::bad_alloc – if host memory cannot be allocated.

Returns:

One row per id (h2v_offsets.size() - 1 rows).

template<typename vertex_t>
csr<vertex_t, std::int64_t, std::int32_t> dyng::testing::combined_graph_reference(const std::vector<std::vector<vertex_t>> &parents, vertex_t source, const std::vector<std::int32_t> &preferences = {})

The combined graph of K shortest-path trees (a port of MOSP’s combinedGraphReference()).

Edge (p, v) is in the combined graph iff p is the parent of v in some tree T_i; its weight is L * (K + 1) - sum_{i : Parent_i[v] == p} L / Pref_i, with L = lcm(preferences) (1 for no preferences). Rows list their edges in the order of the heads v, and for one head in objective order of the first tree that contains the edge. Solving it with dijkstra() from source gives the canonical MOSP tree (its distances in units of 1/L).

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

vertex_t – Vertex id type.

Parameters:

• parents – [in] K parent arrays of n entries each (-1: none).

• source – [in] The source (it has no in-edge).

• preferences – [in] K preferences >= 1, or none (all ones).

Throws:

• invalid_argument_error – if the arrays differ in length, a parent is out of range, or the preferences are not K values >= 1 with lcm <= 2^20, or K is not in [1, 64].

• out_of_memory_error – if host memory cannot be allocated.

Returns:

The combined graph (int64 edge offsets, one int32 weight column).

template<typename vertex_t, typename edge_t, typename weight_t>
std::vector<std::int64_t> dyng::testing::mosp_path_costs_reference(const csr_view<vertex_t, edge_t, weight_t> &out, const std::vector<vertex_t> &parent, vertex_t source, int num_objectives = 0)

The objective values of the path from source to every vertex along a tree (MOSP’s mospPathCosts(), written independently): the weights of the tree edge (p, v) are those of the first edge from p to v in p’s row; columns 0..num_objectives-1 are summed.

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

• vertex_t – Vertex id type.

• edge_t – Edge offset type.

• weight_t – Weight type.

Parameters:

• out – [in] The graph’s out-edges (host memory).

• parent – [in] The tree (n entries, -1 for the source and unreachable vertices).

• source – [in] The source.

• num_objectives – [in] Number of weight columns to sum (0: every column of out).

Throws:

• invalid_argument_error – if a tree edge is not an edge of out, the tree has a cycle, num_objectives is out of range, or the view is not in host memory.

• out_of_memory_error – if host memory cannot be allocated.

Returns:

n * K values, vertex-major; infinite_distance<int64_t>() for vertices the tree does not connect to the source.

struct cbst_layout_check

#include <dyng/testing/cbst_host_model.hpp>

The findings of check_cbst_layout().

Public Functions

inline bool ok() const noexcept

Whether the layout passed.

Returns:

true if every counter is 0.

Public Members

std::int64_t num_nodes = 0

the tree size checked

std::int64_t not_a_permutation = 0

ranks out of range or repeated

std::int64_t not_in_order = 0

in-order traversal positions with a wrong rank

std::int64_t not_found = 0

keys a search from the root does not reach

std::int64_t wrong_offset = 0

keys found at a node that holds another row

std::int64_t inverse_mismatches = 0

positions whose recovered key differs

struct cbst_host_policy

#include <dyng/testing/cbst_host_model.hpp>

How a cbst_host_model behaves where the originals differ (and where the dynG presets will choose): payload growth, compaction, failures, the construct, scratch buffers.

The presets reproduce each original: escher_gpu() is ESCHER-GPU@abcf9b2, mosp_escher() is MOSP_ESCHER@4b86159. dyng_default()

is the target policy of PLAN 6.4.5 (“compact first, then

grow, fail only at the int32 offset limit”), provisional until the dynG store’s presets are merged (M8a step 4). Every field can be set on its own.

Public Types

enum class growth_rule

What happens when an operation needs more payload than the capacity.

Values:

enumerator none

fail (MOSP_ESCHER: a fixed capacity)

enumerator escher_gpu

grow to max(needed + needed/4, 3 * capacity / 2), at most INT_MAX (ESCHER-GPU)

enum class compaction_rule

Whether and where the payload is compacted.

Values:

enumerator none

never (ESCHER-GPU)

enumerator mosp_escher

MOSP_ESCHER’s trigger points: a fill whose overflow segments do not fit (compact, then refill the rest once), an insert whose surplus rows do not fit (compact before appending them), and compact().

enum class failure_rule

How a failure is reported.

Values:

enumerator process_exit

the original ends the process (ESCHER-GPU: exit(2) / checkCuda’s exit)

enumerator exception

the original throws (MOSP_ESCHER: escher::EscherError)

enum class occupancy_rule

The tail occupancy of a constructed row.

Values:

enumerator scan_payload

the values before the row’s terminator, whatever the caller passes (ESCHER-GPU’s initTailMetadata)

enumerator caller_counts_or_zero

the caller’s row counts, or 0 without them (MOSP_ESCHER)

enumerator caller_counts_or_scan

the caller’s row counts, or the scan without them

enum class scratch_rule

How the per-operation input buffers grow.

Values:

enumerator exact

to the operation’s size (ESCHER-GPU’s reserveScratch)

enumerator geometric

by +n/2+1 steps from the current size (MOSP_ESCHER’s ensureScratchCapacity)

Public Members

std::string name

the preset name (reports)

growth_rule growth = growth_rule::escher_gpu

payload growth

compaction_rule compaction = compaction_rule::none

payload compaction

failure_rule failure = failure_rule::process_exit

how failures are reported

occupancy_rule occupancy = occupancy_rule::scan_payload

construct occupancy

scratch_rule scratch = scratch_rule::exact

scratch growth

bool validate_construct = false

reject negative sizes and a payload above the capacity with an error (MOSP_ESCHER); ESCHER-GPU returns without building the tree when the payload does not fit

bool clamp_fill_tail = false

a tail with occupancy above its capacity has no room (MOSP_ESCHER’s max(0, …)); unclamped it is undefined

bool has_rebuild = true

rebuild() exists (ESCHER-GPU’s rebuildFromDevice)

bool has_compact = false

compact() exists (MOSP_ESCHER)

bool counts_bin_launches = true

degree-bin launches are counted (ESCHER-GPU)

std::string error_type

the exception type a failure reports (“escher::EscherError” for MOSP_ESCHER)

std::int64_t max_payload = 2147483647

the largest payload capacity a growth reaches (2^31 - 1: the int32 offsets; tests lower it)

std::int64_t compaction_headroom = 0

after an operation that compacted at a trigger point, grow by the growth rule when fewer than capacity / compaction_headroom slots are free, to the capacity that leaves that many (at most max_payload); 0: never (dyng_default(): 8)

Public Static Functions

static cbst_host_policy escher_gpu()

ESCHER-GPU@abcf9b2: growth, no compaction, process exit on failure, scanned occupancy, exact scratch, rebuild and launch counters.

Returns:

The preset.

static cbst_host_policy mosp_escher()

MOSP_ESCHER@4b86159: a fixed capacity, compaction at its trigger points, then escher::EscherError; validated construct with the caller’s row counts, the fill clamps, geometric scratch, compact().

Returns:

The preset.

static cbst_host_policy dyng_default()

dynG’s default, the target policy of PLAN 6.4.5 (M8a step 5): MOSP_ESCHER’s compaction at its trigger points first, then growth by ESCHER-GPU’s rule where MOSP_ESCHER throws or fewer than 1/8 of the slots stay free after a compaction (compaction_headroom), a failure only beyond max_payload (dyng::capacity_error); scanned occupancy when the caller gives no counts; the construct validation and the fill clamps; geometric scratch; rebuild, compact() and the launch counters.

Returns:

The preset.

static bool from_name(const std::string &name, cbst_host_policy &out)

The preset of a name: “escher_gpu”, “mosp_escher” or “dyng_default”.

Parameters:

• name – [in] The name.

• out – [out] The preset.

Returns:

false if the name is unknown.

struct cbst_op_result

#include <dyng/testing/cbst_host_model.hpp>

The outcome of one operation of the model.

Public Members

cbst_op_status status = cbst_op_status::ok

how it ended

std::string error_type

the original’s exception type (status error)

std::string message

what failed (status other than ok)

std::vector<std::int32_t> mapping

insert: the key of every input item

std::int64_t compact_return = 0

compact(): the new bump pointer

std::int64_t reusable_slots = -1

insert: D, the deleted slots at entry

bool grew = false

the payload capacity grew

std::int64_t compactions = 0

payload compactions run

bool compaction_changed = false

a compaction moved a row, changed a length or lowered the bump pointer

std::array<std::int64_t, 9> bin_launches = {}

degree-bin launches, (fill, reuse, unfill) x (thread, warp, block): one per non-empty bin

struct cbst_key_record

#include <dyng/testing/cbst_host_model.hpp>

One key of a model tree, as the originals’ state digests describe it.

Public Members

std::int32_t key = 0

the key (1-based in both originals)

std::int32_t avail = 0

1: a deleted key whose slot an insert may reuse

std::int32_t length = 0

slots of the first segment, the terminator included

std::int32_t size = 0

the node’s size field (the payload size it was built at)

std::int32_t occupancy = 0

values in the tail segment

std::int32_t tail_capacity = 0

usable slots of the tail segment

std::int32_t value = 0

offset of the first segment

std::int32_t tail_base = 0

offset of the tail segment

std::int32_t segments = 1

segments the row walk visited

std::int32_t row_len = 0

values of the row

bool terminated = true

the row walk ended at a terminator inside the payload

std::vector<std::int32_t> row

the row in read order

struct cbst_model_event

#include <dyng/testing/cbst_host_model.hpp>

A payload growth or compaction of a model tree.

Public Types

enum class kind

What happened.

Values:

enumerator growth

the payload capacity grew

enumerator compaction

the payload was compacted

Public Members

kind what = kind::growth

growth or compaction

std::int64_t op_index = 0

the tree’s operation (0-based count of operations)

std::int64_t before = 0

capacity (growth) or bump pointer (compaction) before

std::int64_t after = 0

capacity or bump pointer after

class cbst_host_model

#include <dyng/testing/cbst_host_model.hpp>

A sequential host model of one CBST of ESCHER-GPU@abcf9b2 / MOSP_ESCHER@4b86159.

The operations take the originals’ inputs: keys, the flat values of every item and their inclusive prefix sums (item i owns values [prefix[i-1], prefix[i])). Keys are those of the originals (1-based; requested insert keys are ignored, as by both originals). The model is not thread-safe; copies are independent.

Public Functions

cbst_host_model(cbst_host_policy policy, std::int64_t payload_capacity, std::int32_t alignment = 4, std::string name = {})

An empty tree (the originals’ CBSTOperations constructor).

Parameters:

• policy – [in] The behaviour.

• payload_capacity – [in] The payload capacity in values.

• alignment – [in] The row alignment of surplus inserts.

• name – [in] The dataset name (reports).

~cbst_host_model()

Releases the model.

cbst_host_model(const cbst_host_model &other)

A deep copy.

Parameters:

other – [in] The model.

cbst_host_model &operator=(const cbst_host_model &other)

A deep copy.

Parameters:

other – [in] The model.

Returns:

This model.

cbst_host_model(cbst_host_model &&other) noexcept

Moves.

Parameters:

other – [inout] The model.

cbst_host_model &operator=(cbst_host_model &&other) noexcept

Moves.

Parameters:

other – [inout] The model.

Returns:

This model.

cbst_op_result construct(const std::vector<std::int32_t> &keys, const std::vector<std::int32_t> &starts, const std::vector<std::int32_t> &flat, const std::vector<std::int32_t> *row_counts = nullptr)

Builds the tree over a flattened payload (constructCBST).

Parameters:

• keys – [in] The keys in sorted order, one per row.

• starts – [in] The offset of every row in flat.

• flat – [in] The flattened rows (flat.size() values are used).

• row_counts – [in] The caller’s row counts (MOSP_ESCHER’s rowOccupancy), or nullptr.

Returns:

The outcome.

cbst_op_result rebuild(const std::vector<std::int32_t> &starts, const std::vector<std::int32_t> &flat, std::int64_t flat_size, std::int64_t payload_capacity)

Rebuilds the tree over a new payload with keys 1..n (rebuildCBSTFromDevice).

Parameters:

• starts – [in] The offset of every row.

• flat – [in] The payload (its used prefix).

• flat_size – [in] The used payload size.

• payload_capacity – [in] The new capacity.

Returns:

The outcome.

cbst_op_result insert(const std::vector<std::int32_t> &keys, const std::vector<std::int32_t> &payload, const std::vector<std::int32_t> &prefix)

Inserts rows: best-fit reuse of deleted slots, then surplus keys (insertCBST).

Parameters:

• keys – [in] The requested keys (ignored, as by both originals; only their number).

• payload – [in] The values of every item.

• prefix – [in] The inclusive prefix sums of the item sizes.

Returns:

The outcome; mapping holds the key of every item.

cbst_op_result erase(const std::vector<std::int32_t> &keys)

Marks keys as deleted (deleteCBST); the rows keep their values.

Parameters:

keys – [in] The keys; missing keys are ignored.

Returns:

The outcome.

cbst_op_result append(const std::vector<std::int32_t> &keys, const std::vector<std::int32_t> &payload, const std::vector<std::int32_t> &prefix)

Appends values to rows (fillCBST): into the tail, then overflow segments.

Parameters:

• keys – [in] The keys, one per item.

• payload – [in] The values of every item.

• prefix – [in] The inclusive prefix sums of the item sizes.

Returns:

The outcome.

cbst_op_result remove_values(const std::vector<std::int32_t> &keys, const std::vector<std::int32_t> &values, const std::vector<std::int32_t> &prefix)

Removes every occurrence of values from rows (unfillCBST).

Parameters:

• keys – [in] The keys, one per item.

• values – [in] The values to remove of every item.

• prefix – [in] The inclusive prefix sums of the removal counts.

Returns:

The outcome.

cbst_op_result compact()

Compacts the payload (MOSP_ESCHER’s compactCBST).

Returns:

The outcome; compact_return is the new bump pointer.

const cbst_host_policy &policy() const noexcept

The policy.

Returns:

The policy.

const std::string &name() const noexcept

The dataset name.

Returns:

The name.

std::int64_t num_records() const noexcept

The record count of the tree (the originals’ numRecords).

Returns:

The count.

std::int64_t num_nodes() const noexcept

The nodes that exist (0 when the original allocated none).

Returns:

The count.

std::int64_t payload_capacity() const noexcept

The payload capacity.

Returns:

The capacity in values.

std::int64_t bump() const noexcept

The bump pointer (the used payload prefix).

Returns:

The offset.

std::int32_t alignment() const noexcept

The row alignment of surplus inserts.

Returns:

The alignment.

std::int64_t scratch_items() const noexcept

The item capacity of the scratch buffers.

Returns:

The capacity.

std::int64_t scratch_payload() const noexcept

The value capacity of the scratch buffers.

Returns:

The capacity.

std::int64_t device_bytes() const noexcept

ESCHER-GPU’s DynamicHypergraph::deviceBytes() formula on the model’s sizes.

Returns:

72 bytes per record, 4 per payload value, 20 per scratch item, 4 per scratch value.

std::int64_t reusable_slots() const noexcept

The deleted slots (the root’s subtree_avail), or -1 without nodes.

Returns:

D.

std::vector<std::int32_t> keys() const

The keys in BST (in-order) order.

Returns:

The keys.

std::vector<std::int32_t> subtree_avail() const

The deleted slots of every subtree, by heap position.

Returns:

The counts.

std::vector<cbst_key_record> records() const

Every key’s record and row, in BST order.

Returns:

The records.

bool record(std::int32_t key, cbst_key_record &out) const

One key’s record and row.

Parameters:

• key – [in] The key.

• out – [out] The record.

Returns:

false if no node holds the key.

const std::vector<cbst_model_event> &events() const noexcept

The growths and compactions so far.

Returns:

The events.

std::int64_t num_operations() const noexcept

The operations applied so far.

Returns:

The count.

bool exited() const noexcept

Whether a failed operation ended the original’s process (the tree takes no more operations: they return cbst_op_status::undefined).

Returns:

true after a process_exit.

std::vector<std::string> check() const

The model’s own consistency check: subtree_avail sums (MOSP_ESCHER’s checkSubtreeAvail), BST order of the keys, rows that end inside the payload.

Returns:

The problems found (empty: none).

struct check_sssp_options

#include <dyng/testing/check_sssp.hpp>

Options of check_sssp_tree().

Public Members

int objective = 0

the weight column

bool require_canonical = true

parents must be the lowest-id tight in-neighbours

struct sssp_tree_check

#include <dyng/testing/check_sssp.hpp>

The findings of check_sssp_tree() (MOSP’s TreeCheck).

Public Functions

inline bool ok() const noexcept

Whether the tree passed.

Returns:

true if nothing was found (non-canonical parents count only in canonical mode).

std::string summary() const

A one-line summary of the counters.

Returns:

The summary.

Public Members

std::int64_t distance_mismatches = 0

dist[v] differs from Dijkstra

std::int64_t inconsistent_parents = 0

no edge (p,v) with w > 0 and d[p] + w == d[v]

std::int64_t non_canonical_parents = 0

consistent, but not the lowest id

std::int64_t parent_mismatches = 0

parent differs from Dijkstra (canonical mode only)

bool require_canonical = true

the mode the check ran in

template<typename vertex_t>
struct sssp_tree

#include <dyng/testing/dijkstra.hpp>

A shortest-path tree on the host.

Template Parameters:

vertex_t – Vertex id type.

Public Members

std::vector<std::int64_t> distances

infinite_distance<int64_t>() if unreachable

std::vector<vertex_t> parents

-1 for the source and unreachable vertices

struct line_graph_rows

#include <dyng/testing/line_graph_oracle.hpp>

A line graph as a CSR: row i (hyperedge id i) lists neighbours[offsets[i] .. offsets[i + 1]), sorted.

Public Functions

inline std::int64_t num_ids() const noexcept

Number of rows (ids).

Returns:

offsets.size() - 1.

inline std::vector<std::int64_t> row(std::int64_t id) const

The row of an id.

Parameters:

id – [in] An id in [0, num_ids()).

Returns:

Its neighbours, sorted.

Public Members

std::vector<std::int64_t> offsets = {0}

num_ids() + 1 offsets

std::vector<std::int64_t> neighbours

the neighbour ids of every row, rows back to back