Generators#

Seeded generators of graphs, hypergraphs and batches (dyng::generators).

  • generators/hypergraphs.hpp: uniform_hypergraph() and random_hyperedge_batch() with the batch mixes of the conformance kit (insertions, deletions, delete-then-reuse within a batch, heavy deletion, delete-all, re-insert, a batch larger than the hypergraph, duplicate members, dead-id deletions, a skewed hyperedge of 1,100 members, ids at the index limits, the empty batch). Their distributions are the library’s own (std::mt19937_64 and dynG’s uniform integer and shuffle algorithms), so a stream is bit-exact per (seed, major version) with every compiler and standard library; golden hashes in the tests pin it.

  • generators::legacy reproduces the random streams of the original research tools bit for bit, so the inputs of published experiments and of the parity harness can be regenerated without the original code: MOSP’s change generator (mosp_changes), CycleEnumeration-GPU’s batches (cycle_enum_batch), and ESCHER-GPU’s synthetic hypergraph and batch generator (escher_hypergraph, escher_batch_generator, which reads the live state of a dynG hypergraph and shares one std::mt19937_64 with it in ESCHER-GPU’s draw order). These streams follow libstdc++’s algorithms, which dynG reproduces itself; standard_library_matches_legacy_streams() checks at run time that the build’s standard library draws the same (true with libstdc++ 11 and later, which built the originals).

enum class dyng::generators::hyperedge_batch_mix : std::uint8_t#

The kinds of hyperedge batches random_hyperedge_batch() draws (the degenerate cases of the conformance kit among them). k is hyperedge_batch_options::size.

Values:

enumerator insert_only#

k fresh hyperedges

enumerator delete_only#

k distinct live hyperedges deleted

enumerator mixed#

(k + 1) / 2 live hyperedges deleted and (k + 1) / 2 fresh ones inserted

enumerator reuse#

delete-then-reuse within one batch: the k largest live hyperedges deleted and k fresh ones no larger than the smallest of them inserted (they fit the freed slots: under id_reuse::erase_first they take their ids)

enumerator heavy_delete#

nine tenths of the live hyperedges deleted, k fresh ones inserted

enumerator delete_all#

every live hyperedge deleted

enumerator reinsert#

k live hyperedges deleted and their member sets (and weights) inserted again

enumerator larger#

half of the live hyperedges deleted and 2 x live + 3 fresh ones inserted: a batch larger than the hypergraph

enumerator duplicates#

k fresh hyperedges with every member twice (shuffled), and a copy of the live hyperedge with the smallest id (parallel hyperedges)

enumerator dead_ids#

min(k, 2) live hyperedges deleted, the same ids again, a dead id below the id bound (if there is one), the bound and -1 (all skipped by apply()), one fresh insertion

enumerator skewed#

min(k, 2) live hyperedges deleted, one fresh hyperedge of min(n, skewed_cardinality) members and one of 1 member

enumerator limits#

ids at the index limits: the largest live id deleted, deletions of INT64_MIN, INT64_MAX and the id bound, insertions {0, n - 1}, {n - 1} and {0} (with the smallest and the largest weight)

enumerator empty#

no operation

enum class dyng::generators::legacy::mosp_change_mode : std::uint8_t#

How MOSP’s change generator draws a batch (MOSP’s ChangeMode).

Values:

enumerator uniform#

Insertions join two random vertices with random weights in [weight_min, weight_max]; deletions are sampled with replacement from the existing edges.

enumerator targeted#

The thesis workload: insertions join two random vertices with weights below the graph’s average weight of each objective; every deletion removes a distinct edge of an SOSP tree (the Dijkstra tree of any objective from source). Needs libstdc++ (std::shuffle).

enumerator reweight#

Every change overwrites the weights of an existing edge (an insertion of that edge) with new random weights in [weight_min, weight_max].

enumerator increase#

Every change raises all weights of a distinct SOSP-tree edge by a random amount in [1, weight_max], saturating at 2^31 - 1. Needs libstdc++ (std::shuffle).

enum class dyng::generators::legacy::escher_insert_mode : std::uint8_t#

How escher_batch_generator draws the inserted hyperedges (ESCHER-GPU’s InsertMode).

Values:

enumerator random#

fresh hyperedges from escher_hypergraph()’s distribution (A’s default)

enumerator sample#

copies of uniformly sampled live hyperedges (A’s default with –input)

template<typename vertex_t, typename weight_t>
hyperedge_list<vertex_t, weight_t> dyng::generators::uniform_hypergraph(const uniform_hypergraph_options &opt)#

A uniform random hypergraph: hyperedge i (id i of hypergraph::from_hyperedges()) has a uniform cardinality and uniformly drawn distinct members, sorted.

The stream is a function of (options, the library’s major version) alone: std::mt19937_64(seed) (specified by the C++ standard) with the library’s own uniform integer and sampling algorithms, so it is the same with every compiler and standard library. Golden hashes in the tests pin it.

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

opt – [in] The options.

Throws:

  • invalid_argument_error – if a count is negative, there are hyperedges but no vertex, the cardinality range is empty or below 1, n does not fit vertex_t, or the weight range is empty, below 1 or does not fit weight_t.

  • out_of_memory_error – if host memory cannot be allocated.

Returns:

The hyperedges (num_vertices = n).

std::string_view dyng::generators::to_string(hyperedge_batch_mix mix) noexcept#

The name of a hyperedge_batch_mix (“insert_only”, “delete_only”, …).

Parameters:

mix – [in] The mix.

Returns:

Its name.

template<typename vertex_t, typename weight_t>
hyperedge_batch<vertex_t, weight_t> dyng::generators::random_hyperedge_batch(vertex_t num_vertices, const incidence_view<vertex_t> &h2v, array_view<const weight_t> weights, const hyperedge_batch_options &opt)#

A random hyperedge batch for a hypergraph state given by its h2v rows: row i lists the members of the hyperedge with id i (an empty row is a dead id; the number of rows is the id bound), as hypergraph::h2v() returns them.

Live hyperedges are chosen uniformly (in the order of a seeded shuffle of the live ids); deleted ids appear in the batch in that order, insertions after them in generation order. The stream is a function of (state, options, the library’s major version) alone, as for uniform_hypergraph(). The batch names ids of the given state, so it must be applied to that state; its inserted ids are the hypergraph’s choice (hyper_apply_summary::inserted_ids).

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

  • num_vertices – [in] The vertex count n.

  • h2v – [in] The rows by id (host memory).

  • weights – [in] The weights by id (host memory; empty for unweighted or unknown: hyperedge_batch_mix::reinsert then uses weight min_weight).

  • opt – [in] The options.

Throws:
Returns:

The batch.

template<typename vertex_t, typename weight_t>
hyperedge_batch<vertex_t, weight_t> dyng::generators::random_hyperedge_batch(const resources &res, const hypergraph<vertex_t, weight_t> &h, const hyperedge_batch_options &opt)#

A random hyperedge batch for the current state of a hypergraph (its h2v rows and weights, copied to the host for a CUDA hypergraph).

Synchronization:

Blocks until the work has completed (synchronous). Reads the hypergraph’s rows (a copy to the host for a CUDA hypergraph).

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Hyperedge weight type.

Parameters:

  • res – [in] Execution resources of the hypergraph’s backend.

  • h – [in] The hypergraph.

  • opt – [in] The options.

Throws:
Returns:

The batch (see the other overload).

template<typename vertex_t, typename edge_t, typename weight_t>
edge_batch<vertex_t, weight_t> dyng::generators::legacy::mosp_changes(const csr_view<vertex_t, edge_t, weight_t> &graph, const mosp_change_options &opt, mosp_change_report *report = nullptr)#

MOSP’s change generator (generateChangeBatch of MOSP-OpenMP c352151 and MOSP-CUDA e220ee2, the same code; mospPrep changes), bit-exact for a fixed seed.

The batch has one weight per objective of graph (all of its columns) and follows MOSP’s file order: the insertions, then the re-weighted edges (as insertions), then the deletions. Written with io::write_legacy_batch() it is byte-identical to mospPrep changes on the same CSR files (tested against the originals’ outputs). The safe filter applies the batch under graph_properties::mosp_compatible(), as MOSP’s applyChangeBatch() does.

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

  • vertex_t – Vertex id type.

  • edge_t – Edge offset type.

  • weight_t – Weight type (32-bit integer weights, as MOSP’s).

Parameters:
Throws:

  • invalid_argument_error – if the options are invalid (fewer than 2 vertices, no weight column, a negative count, weight_min > weight_max or < 1, source out of range), a local region has fewer than 2 vertices, or no edge is available for deletions or re-weights (MOSP’s error cases).

  • not_supported_error – for the targeted and increase modes in a build without libstdc++.

  • out_of_memory_error – if host memory cannot be allocated.

Returns:

The batch.

template<typename vertex_t, typename edge_t, typename weight_t>
edge_batch<vertex_t, weight_t> dyng::generators::legacy::cycle_enum_batch(const csr_view<vertex_t, edge_t, weight_t> &graph, const cycle_enum_batch_options &opt)#

CycleEnumeration-GPU’s batch generator (generate_batch of commit 0a976ad; cycle-enum --task update), bit-exact for a fixed seed.

Deletions are sampled without replacement from the existing edges (in window), insertions from the directed pairs of the window that are neither edges nor self-loops, as in the original: one std::mt19937_64(seed) draws the window start, shuffles the candidate deletions (libstdc++’s std::shuffle) and draws the insertion endpoints (libstdc++’s std::uniform_int_distribution); dynG reproduces both algorithms, so the batch does not depend on the standard library. The batch is normalized: the deletions, then the insertions, each sorted by (source, destination). Applied under graph_properties::cycle_enum_compatible() it changes the graph exactly as the original’s apply_batch(). For a weighted graph every insertion carries the weight 1 in each weight column (the original’s batches have no weights).

Synchronization:

Blocks until the work has completed (synchronous).

Template Parameters:

  • vertex_t – Vertex id type.

  • edge_t – Edge offset type.

  • weight_t – Weight type (unweighted or integral).

Parameters:
Throws:

  • invalid_argument_error – if a count is negative, the graph has fewer than 2 vertices (and a count is positive), its rows are not sorted and duplicate-free, or there are not enough existing edges or non-edges in the window for the requested counts (the original’s errors).

  • out_of_memory_error – if host memory cannot be allocated.

Returns:

The batch (num_weights of the graph).

bool dyng::generators::legacy::standard_library_matches_legacy_streams()#

Whether this build’s standard library draws std::uniform_int_distribution (with std::mt19937 and std::mt19937_64) and std::shuffle exactly as the reproductions of the legacy generators do: checked at run time by drawing from both.

The legacy streams are computed by dynG’s own reproduction of libstdc++’s algorithms, so they do not depend on the standard library; this check confirms that the standard library of the build is the one the originals were built with (libstdc++ 11 or later: true), i.e. that a program linked with it, like the originals, draws the same streams. Other standard libraries give false.

Throws:

out_of_memory_error – if host memory cannot be allocated.

Returns:

True if every compared draw is equal.

std::string_view dyng::generators::legacy::to_string(escher_insert_mode mode) noexcept#

The name of an escher_insert_mode (“random”, “sample”).

Parameters:

mode – [in] The mode.

Returns:

Its name.

template<typename vertex_t, typename weight_t>
hyperedge_list<vertex_t, weight_t> dyng::generators::legacy::escher_hypergraph(std::mt19937_64 &rng, const escher_hypergraph_options &opt)#

ESCHER-GPU’s synthetic hypergraph (hyperedge2vertex of ESCHER-GPU@abcf9b2), bit-exact for the engine’s state: hyperedge i has a size drawn from [1, max_cardinality] (clamped to the vertex range) and distinct members drawn from [min_vertex, max_vertex] until it has that many, sorted.

The engine is the single std::mt19937_64 of ESCHER-GPU’s run (std::mt19937_64(seed) for its –seed); escher_batch_generator continues from it, as A’s batches continue A’s stream. Built with hypergraph::from_hyperedges() under {id_reuse::erase_first, capacity_policy:: escher_gpu()}, hyperedge i has A’s key i + 1 and vertex v is A’s vertex v + 1.

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Hyperedge weight type (a weighted list gets weight 1 everywhere).

Parameters:

  • rng – [inout] The engine (advanced by the draws).

  • opt – [in] The parameters.

Throws:
Returns:

The hyperedges, num_vertices = max_vertex + 1.

struct uniform_hypergraph_options#
#include <dyng/generators/hypergraphs.hpp>

Options of uniform_hypergraph().

Public Members

std::int64_t num_vertices = 0#

n (>= 1 when there are hyperedges)

std::int64_t num_hyperedges = 0#

hyperedges to draw (>= 0)

std::int64_t min_cardinality = 1#

The cardinality of every hyperedge is uniform in [min_cardinality, max_cardinality], clamped to n; its members are distinct vertices, uniform among the subsets of that size.

std::int64_t max_cardinality = 4#

see min_cardinality

std::int64_t min_weight = 1#

weighted types: weights uniform in [min_weight, max_weight]

std::int64_t max_weight = 100#

see min_weight

std::uint64_t seed = 1#

the seed of the stream

struct hyperedge_batch_options#
#include <dyng/generators/hypergraphs.hpp>

Options of random_hyperedge_batch().

Public Members

hyperedge_batch_mix mix = hyperedge_batch_mix::mixed#

the kind of batch

std::int64_t size = -1#

k of the mix (>= 0); -1: max(1, live hyperedges / 10)

std::int64_t min_cardinality = 1#

Fresh hyperedges have a cardinality uniform in [min_cardinality, max_cardinality] (clamped to n) and distinct members.

std::int64_t max_cardinality = 4#

see min_cardinality

std::int64_t skewed_cardinality = 1100#

hyperedge_batch_mix::skewed’s large hyperedge

std::int64_t min_weight = 1#

weighted types: weights of fresh hyperedges

std::int64_t max_weight = 100#

see min_weight

std::uint64_t seed = 1#

the seed of the stream

struct mosp_change_options#
#include <dyng/generators/legacy.hpp>

Options of mosp_changes() (MOSP’s ChangeGeneratorOptions; the mospPrep changes flags).

Public Members

std::int64_t num_changes = 0#

–changes: number of changes

double insertion_percentage = 50.0#

–ins: share of insertions (uniform, targeted)

mosp_change_mode mode = mosp_change_mode::uniform#

–mode

std::int32_t weight_min = 1#

–wmin: smallest drawn weight (>= 1)

std::int32_t weight_max = 100#

–wmax: largest drawn weight

std::uint32_t seed = 1#

–seed: std::mt19937 seed

std::int64_t local_hops = 0#

–local: if positive, every endpoint lies within this many hops (ignoring direction) of a random centre (a local batch)

bool safe_deletions = false#

–safe: drop deletions that would disconnect a vertex that is reachable from source

std::int64_t source = 0#

–source: the source of the trees and of the safe filter

struct mosp_change_report#
#include <dyng/generators/legacy.hpp>

What mosp_changes() did (the report line of mospPrep changes).

Public Functions

std::string summary() const#

The report in mospPrep changes format, e.g. “inserts=50 reweights=0 deletes=50 (safe: kept 50 of 50 after 1 rounds)”.

Returns:

The text (without the “changes: “ prefix).

Public Members

std::int64_t inserts = 0#

insertions of new edges

std::int64_t reweights = 0#

insertions that overwrite existing edges

std::int64_t deletes = 0#

deletions kept

std::int64_t requested_deletes = 0#

deletions before the safe filter

int safe_rounds = 0#

rounds of the safe filter (0 without it)

bool safe = false#

the safe filter ran

std::int64_t centre = -1#

centre of a local batch, -1 otherwise

std::int64_t local_hops = 0#

radius of a local batch

std::int64_t region = 0#

vertices of the local region

struct cycle_enum_batch_options#
#include <dyng/generators/legacy.hpp>

Options of cycle_enum_batch() (CycleEnumeration-GPU’s BatchParams; the cycle-enum flags –deletes, –inserts, –batch-seed and –batch-locality).

Public Members

std::int64_t num_deletions = 0#

existing edges to delete (sampled without replacement)

std::int64_t num_insertions = 0#

new edges to insert (non-edges, no self-loops)

std::uint64_t seed = 0#

seed of std::mt19937_64

std::int64_t locality_window = -1#

Locality window: when >= 0 and smaller than the vertex count, both endpoints of every change lie in a window of max(window, 2) consecutive vertex ids whose start is drawn from the seed. The default, a negative value, means no window (the original’s std::nullopt).

struct escher_hypergraph_options#
#include <dyng/generators/legacy.hpp>

ESCHER-GPU’s synthetic hypergraph (its positional arguments n m r1 r2), in dynG’s 0-based vertex ids.

Public Members

std::int64_t num_hyperedges = 0#

n: hyperedges to draw (>= 0)

std::int32_t max_cardinality = 1#

m: the size of every hyperedge is drawn from [1, m] (and clamped to the vertex range).

std::int32_t min_vertex = 0#

r1 - 1: the smallest vertex drawn (>= 0)

std::int32_t max_vertex = 0#

r2 - 1: the largest vertex drawn (the hypergraph has max_vertex + 1 vertices, ESCHER-GPU’s maxVertexId)

struct escher_batch_options#
#include <dyng/generators/legacy.hpp>

Options of escher_batch_generator (ESCHER-GPU’s –deletions, –insertions, –batch-size, –insert-mode and the distribution of its random insertions).

Public Members

std::int64_t num_deletions = -1#

Deletions per batch (at most the live count). -1 together with num_insertions == -1: ESCHER-GPU’s demo batch without batch options, min(2, live) deletions and one more insertion.

std::int64_t num_insertions = -1#

insertions per batch (see num_deletions)

escher_insert_mode insert_mode = escher_insert_mode::random#

–insert-mode

escher_hypergraph_options graph#

The distribution of random insertions (A’s graph parameters; for a hypergraph read from a file, its largest cardinality, min_vertex 0 and its largest vertex). max_vertex is raised to the hypergraph’s num_vertices() - 1 if that is larger, as A does.

Public Static Functions

static inline escher_batch_options batch_size(std::int64_t size, escher_insert_mode mode, const escher_hypergraph_options &graph)#

ESCHER-GPU’s –batch-size N: N / 2 deletions and N - N / 2 insertions.

Parameters:

  • size – [in] N (>= 0).

  • mode – [in] The insert mode.

  • graph – [in] The distribution of random insertions.

Returns:

The options.

class escher_batch_generator#
#include <dyng/generators/legacy.hpp>

ESCHER-GPU’s batch generator (BatchGenerator::next of ESCHER-GPU@abcf9b2), bit-exact for the engine’s state, reading the live state of a dynG hypergraph.

Each next() reads the live ids in increasing order (A’s live keys in key order) and their rows, chooses the deletions by a partial Fisher-Yates shuffle of the live ids (sorted afterwards) and the insertions as random hyperedges (escher_hypergraph()’s distribution) or as copies of live hyperedges indexed into the partly shuffled live ids (sample mode), all from the shared engine in A’s draw order. Driven against a hypergraph under {id_reuse::erase_first, capacity_policy::escher_gpu()} that applies every batch, it reproduces A’s batches: from the second batch on that needs dynG’s ids to equal A’s keys, so it is also an end-to-end check of the id parity.

Public Functions

escher_batch_generator(std::mt19937_64 &rng, const escher_batch_options &opt)#

A generator drawing from rng (which must outlive it).

Parameters:

  • rng – [inout] The shared engine.

  • opt – [in] The options.

Throws:

invalid_argument_error – if exactly one of the counts is -1 or a count is below -1, or the random-insertion parameters are invalid.

template<typename vertex_t, typename weight_t>
hyperedge_batch<vertex_t, weight_t> next(const resources &res, const hypergraph<vertex_t, weight_t> &h)#

The next batch for the hypergraph’s live state.

Synchronization:

Blocks until the work has completed (synchronous). Reads the hypergraph’s rows (a copy to the host for a CUDA hypergraph).

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Hyperedge weight type (insertions of a weighted batch get weight 1).

Parameters:

  • res – [in] Execution resources of the hypergraph’s backend (its rows are read on the host).

  • h – [in] The hypergraph.

Throws:
Returns:

The batch: the deletions (sorted ids), then the insertions in A’s order.