Input and output#

Readers and writers of the formats in File formats: MOSP text CSR, MOSP batches, Matrix Market, edge lists, distances and trees; the batch files .dgt (graph and hypergraph batches) and .dgb (binary, streamed by batch_reader); hypergraphs (.hg, with the preprocessing of ESCHER-GPU and of MOSP_ESCHER’s H-SOSP as the option sets hypergraph_read_options::escher_gpu() and hsosp()).

enum class dyng::io::batch_dtype : std::uint8_t#

The element types a .dgb file can store (its header names one per array kind).

Values:

enumerator none#: no such array (an unweighted batch’s weights, a graph’s hyperedge ids)

enumerator int32#: 32-bit signed integers

enumerator int64#: 64-bit signed integers

enum class dyng::io::vertex_ids : std::uint8_t#

How the vertex ids of an edge-list file become graph ids.

Values:

enumerator compact#: The ids that occur in an edge (after self-loops are dropped) are numbered 0, 1, … in ascending order of their value in the file (CycleEnumeration-GPU); ids may be any 64-bit integers, and edge_list_info::external_ids returns the mapping.

enumerator as_is#: The id in the file minus edge_list_options::index_base; num_vertices is the largest id + 1, so vertices without edges are kept.

enum class dyng::io::duplicate_edges : std::uint8_t#

What happens to rows that repeat a (source, destination) pair.

Values:

enumerator merge#: One edge per pair (the weights of the last such row in file order).

enumerator keep#: Every row is an edge (CycleEnumeration-GPU’s grouped temporal edges, flattened); the timestamps are returned in edge_list_info::timestamps.

enum class dyng::io::vertex_relabel : std::uint8_t#

How the vertex ids of a .hg file become hypergraph vertex ids.

Values:

enumerator none#: The id in the file minus hypergraph_read_options::index_base (ESCHER-GPU’s loader: vertex v of the file is vertex v - 1); the vertex count is the largest id + 1 unless hypergraph_read_options::num_vertices is given, so unused ids stay isolated vertices.

enumerator dense_sorted#: The distinct ids of the kept hyperedges, any 64-bit integers, numbered 0, 1, … in ascending order (ESCHER-GPU’s bench/datasets/convert_coauth.py and MOSP_ESCHER’s scripts/benson_to_hg.py, which write ids 1..V this way).

enumerator first_appearance#: The distinct ids of the kept hyperedges, any 64-bit integers, numbered 0, 1, … in the order in which they first appear, hyperedge by hyperedge and within a hyperedge in ascending id order (MOSP_ESCHER’s loadHypergraphFile, the H-SOSP preprocessing).

enum class dyng::io::matrix_market_weights : std::uint8_t#

Where the edge weights of a Matrix Market graph come from.

Values:

enumerator automatic#: integer field: one column from the file; pattern: none; others: error

enumerator none#: no weight columns (num_weights = 0); values in the file are checked but ignored

enumerator from_file#: one column from the file’s values (integer field only in this release)

enumerator random#: random_weights: K seeded uniform integer columns (mospPrep mtx2csr)

template<typename vertex_t, typename weight_t> std::vector<edge_batch<vertex_t, weight_t>> dyng::io::read_batches(const std::string &path, const batch_file_options &options = {})#

Read a .dgt batch text file: a sequence of batches (PLAN Section 5.7).

One operation per line; blank lines and lines whose first token starts with # are skipped. An optional first line dgt 1 names the format version (only version 1 exists). A line batch <id> starts a batch (the ids are non-negative and strictly increasing); a file without batch lines holds one batch (or none if it holds no operation). The graph operations of 0.1 are +e u v [w1 .. wK] (an edge insertion with exactly K weights) and -e u v (an edge deletion), ids 0-based. Within a batch the insertions and the deletions each keep file order (which of the two applies first is the graph’s batch semantics, not the file’s). A file holds the batches of one container kind: the first line may name it (dgt 1 graph); a hypergraph file (dgt 1 hypergraph, or a hyperedge operation +h / -h) is an io_error here (read it with read_hyperedge_batches()). The vertex operations +v u [label] and -v u (label_propagation) and the incidence edits +i, -i are reserved for 0.4 and rejected with an io_error. Every token must be a whole decimal integer; weights must fit weight_t.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (integral, or dyng::unweighted).

Parameters:

path – [in] The file.
options – [in] K and the vertex count used for validation.

Throws:

io_error – if the file is missing or malformed (with path, line and column).
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The batches in file order.

template<typename vertex_t, typename weight_t> void dyng::io::write_batches(const std::string &path, const std::vector<edge_batch_view<vertex_t, weight_t>> &batches)#

Write batches as a .dgt batch text file (read back by read_batches()).

Writes dgt 1, then for batch i the line batch i, its deletions (-e u v) and its insertions (+e u v w1 .. wK), each in batch order.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (integral, or dyng::unweighted).

Parameters:

path – [in] The file (parent directories are created).
batches – [in] The batches (host memory; every batch with insertions has the same K).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if a batch has vertex operations, inconsistent sizes, a negative vertex id (it would not read back), or a K that differs from another batch’s.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> std::vector<hyperedge_batch<vertex_t, weight_t>> dyng::io::read_hyperedge_batches(const std::string &path, const hyperedge_batch_file_options &options = {})#

Read the hypergraph batches of a .dgt batch text file (PLAN Section 5.7).

The format of read_batches() with the hyperedge operations: +h v1 v2 .. [; w] inserts a hyperedge with the listed members (at least one; repeats are kept here and dropped by hypergraph::apply()) and, for a weighted type, its weight in [1, max(weight_t)] after a ; (a token of its own: +h 0 1 ; 5, or attached: +h 0 1;5); -h id deletes the hyperedge with the id id (>= 0; dead or out-of-range ids are kept and skipped by apply()). A file holds the batches of one container kind: graph operations (+e, -e) or a dgt 1 graph line are an io_error here. The incidence edits +i h v and -i h v are reserved for 0.4 and rejected with an io_error.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

path – [in] The file.
options – [in] The vertex count used for validation.

Throws:

io_error – if the file is missing or malformed (with path, line and column).
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The batches in file order.

template<typename vertex_t, typename weight_t> void dyng::io::write_hyperedge_batches(const std::string &path, const std::vector<hyperedge_batch_view<vertex_t, weight_t>> &batches)#

Write hypergraph batches as a .dgt batch text file (read back by read_hyperedge_batches()).

Writes dgt 1 hypergraph, then for batch i the line batch i, its deletions (-h id) and its insertions (+h v1 .. vk, with ; w for a weighted type), each in batch order.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

path – [in] The file (parent directories are created).
batches – [in] The batches (host memory).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if a batch is malformed or would not read back: offsets that do not start at 0 or end at the member count, an empty insertion, a negative member or deletion id, a weight below 1 or a missing one, an array outside host-accessible memory.
not_supported_error – if a batch has incidence edits (planned for 0.4).
out_of_memory_error – if host memory cannot be allocated.

std::string_view dyng::io::to_string(batch_dtype dtype) noexcept#

The lower-case name of a batch_dtype (“none”, “int32”, “int64”).

Parameters:: dtype – [in] The value.
Returns:: Its name.

template<typename vertex_t, typename weight_t> batch_file_header dyng::io::edge_batch_file_header(int num_weights)#

The header of a .dgb file of graph batches of the types (vertex_t, weight_t).

Template Parameters:

vertex_t – Vertex id type (int32 or int64).
weight_t – Weight type (dyng::unweighted, int32 or int64).

Parameters:

num_weights – [in] Weights per insertion (K; 0 for unweighted).

Throws:

invalid_argument_error – if num_weights is negative, or positive for unweighted.

Returns:

The header (num_batches 0).

template<typename vertex_t, typename weight_t> batch_file_header dyng::io::hyperedge_batch_file_header(std::uint64_t flags = 0)#

The header of a .dgb file of hypergraph batches of the types (vertex_t, weight_t).

Template Parameters:

vertex_t – Vertex id type (int32 or int64).
weight_t – Hyperedge weight type (dyng::unweighted, int32 or int64).

Parameters:

flags – [in] batch_file_flags.

Throws:

invalid_argument_error – if a flag is unknown.

Returns:

The header (one weight per insertion for a weighted type; num_batches 0).

template<typename vertex_t, typename weight_t> void dyng::io::write_binary_batches(const std::string &path, const std::vector<edge_batch_view<vertex_t, weight_t>> &batches)#

Write graph batches as a .dgb file (batch_writer over every batch).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (dyng::unweighted, or integral).

Parameters:

path – [in] The file (parent directories are created).
batches – [in] The batches (host memory, one K).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if a batch is malformed (the rules of write_batches()).
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> std::vector<edge_batch<vertex_t, weight_t>> dyng::io::read_binary_batches(const std::string &path, const batch_reader_options &options = {})#

Read every batch of a .dgb file of graph batches into host memory.

Template Parameters:

vertex_t – Vertex id type (the file’s).
weight_t – Weight type (the file’s).

Parameters:

path – [in] The file.
options – [in] The vertex count used for validation.

Throws:

io_error – if the file is missing or malformed, or holds hypergraph batches (read_binary_hyperedge_batches() reads them).
invalid_argument_error – if the file holds other vertex or weight types.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The batches in file order.

template<typename vertex_t, typename weight_t> void dyng::io::write_binary_hyperedge_batches(const std::string &path, const std::vector<hyperedge_batch_view<vertex_t, weight_t>> &batches)#

Write hypergraph batches as a .dgb file (batch_writer over every batch, no flags).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

path – [in] The file (parent directories are created).
batches – [in] The batches (host memory).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if a batch is malformed (the rules of write_hyperedge_batches()).
not_supported_error – if a batch has incidence edits (planned for 0.4).
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> std::vector<hyperedge_batch<vertex_t, weight_t>> dyng::io::read_binary_hyperedge_batches(const std::string &path, const batch_reader_options &options = {})#

Read every batch of a .dgb file of hypergraph batches into host memory (the annotations are not kept: use batch_reader for them).

Template Parameters:

vertex_t – Vertex id type (the file’s).
weight_t – Hyperedge weight type (the file’s).

Parameters:

path – [in] The file.
options – [in] The vertex count used for validation.

Throws:

io_error – if the file is missing or malformed, or holds graph batches (read_binary_batches() reads them).
invalid_argument_error – if the file holds other vertex or weight types.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The batches in file order.

template<typename vertex_t, typename weight_t> edge_batch<vertex_t, weight_t> dyng::io::read_legacy_batch(const std::string &insert_path, const std::string &delete_path, const legacy_batch_options &options = {})#

Read a MOSP batch: insertions from insert_path, deletions from delete_path.

Each non-blank line of the insert file holds exactly 2 + K integers “u v w1 .. wK”, and each non-blank line of the delete file exactly 2 integers “u v”; ids are 0-based and must lie in [0, num_vertices), weights in [1, max(weight_t)] (MOSP readChangeBatch()). By default dynG is stricter than MOSP in three places: extra integers on an insertion or a deletion line, and a deletion line with a single integer, are errors (MOSP ignores them); options.mosp_lenient restores MOSP’s decisions. In both modes every token must be a whole decimal integer (“12abc” is an error, as in MOSP). Operations keep file order.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (integral).

Parameters:

insert_path – [in] The insertion file.
delete_path – [in] The deletion file.
options – [in] K and the vertex count used for validation.

Throws:

io_error – if a file is missing or malformed (with path, line and column).
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The batch.

template<typename vertex_t, typename weight_t> void dyng::io::write_legacy_batch(const std::string &insert_path, const std::string &delete_path, const edge_batch_view<vertex_t, weight_t> &batch)#

Write a batch as MOSP insert.txt / delete.txt (byte-identical to MOSP’s writeChangeBatch()).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (integral).

Parameters:

insert_path – [in] The insertion file (parent directories are created).
delete_path – [in] The deletion file (parent directories are created).
batch – [in] The batch (host memory; vertex operations are not representable).

Throws:

io_error – if a file cannot be written.
invalid_argument_error – if the batch has vertex operations or inconsistent sizes.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename edge_t, typename weight_t> csr<vertex_t, edge_t, weight_t> dyng::io::read_csr_triplet(const std::string &prefix, const csr_triplet_options &options = {})#

Read a MOSP text CSR.

Validation follows MOSP’s readCsrGraph(): offsets are integers in [0, max(edge_t)] starting at 0 and non-decreasing, with at least one vertex; neighbours lie in [0, n) and number exactly row_ptr[n]; every non-blank line of Values.txt holds the same number K of weights, each in [1, max(weight_t)], and there is one such line per edge. Every token must be a complete decimal integer.

Template Parameters:

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

Parameters:

prefix – [in] Path prefix of the three files.
options – [in] The expected number of weight columns.

Throws:

io_error – if a file is missing or malformed (with path, line and column).
invalid_argument_error – if options.num_weights is negative.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The CSR (objective-major weights).

template<typename vertex_t, typename edge_t, typename weight_t> void dyng::io::write_csr_triplet(const std::string &prefix, const csr_view<vertex_t, edge_t, weight_t> &graph)#

Write a CSR in the MOSP text format (byte-identical to MOSP’s writeCsrGraph()).

Template Parameters:

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

Parameters:

prefix – [in] Path prefix of the three files (parent directories are created).
graph – [in] The CSR (host memory), e.g. graph::view().out or csr::view().

Throws:

io_error – if a file cannot be written.
invalid_argument_error – if the view is not host-accessible or its sizes disagree.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> edge_list<vertex_t, weight_t> dyng::io::read_edge_list(const std::string &path, const edge_list_options &options = {}, edge_list_info *info = nullptr)#

Read a directed edge list.

Text format: one edge per line, src dst [w1..wK] [ts], integers separated by spaces, tabs or commas (a TUDataset *_A.txt file loads directly). Blank lines and lines whose first non-blank character is # or % are skipped. An integer is an optional sign followed by decimal digits and must fit 64 bits. A file whose first line starts with %MatrixMarket is read as a Matrix Market coordinate file: its dimensions line is skipped and its value columns are ignored; a general matrix gives one edge per entry, and a symmetric, skew-symmetric or hermitian matrix gives both directions of every entry; the array format and unknown symmetries are rejected.

The result is sorted by (source, destination) (and by timestamp, then file order, among the rows of one pair with duplicate_edges::keep). The file is split into line-aligned parts parsed on options.threads threads; the result does not depend on the thread count.

Template Parameters:

vertex_t – Vertex id type of the result.
weight_t – Weight type of the result: unweighted, or an integer type.

Parameters:

path – [in] The file.
options – [in] Weight columns, id mapping, symmetrization, self-loops, duplicates, threads.
info – [out] Optional: the id mapping, the timestamps and the kind of file.

Throws:

io_error – if the file cannot be read or is malformed (path and line), an id is out of range for as_is, or there are more vertices than vertex_t holds.
invalid_argument_error – if the options are invalid (negative num_weights, weights for an unweighted result).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The edges; num_vertices is the number of compact ids (compact) or the largest id + 1 (as_is).

template<typename vertex_t, typename weight_t> void dyng::io::write_edge_list(const std::string &path, const edge_list_view<vertex_t, weight_t> &edges)#

Write an edge list as text, one line src dst [w1..wK] per edge (0-based ids, single spaces), in edge order.

read_edge_list() with ids = vertex_ids::as_is, num_weights = edges.num_weights and drop_self_loops = false reads it back (sorted by (source, destination); duplicates merged unless duplicates = keep).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (unweighted or integral).

Parameters:

path – [in] The file (its parent directory is created).
edges – [in] The edges (host memory).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if the arrays disagree in size or are not host-accessible.
out_of_memory_error – if host memory cannot be allocated.

std::string_view dyng::io::to_string(vertex_relabel relabel) noexcept#

The lower-case name of a vertex_relabel (“none”, “dense_sorted”, “first_appearance”).

Parameters:: relabel – [in] The value.
Returns:: Its name.

template<typename vertex_t, typename weight_t> hyperedge_list<vertex_t, weight_t> dyng::io::read_hypergraph(const std::string &path, const hypergraph_read_options &options = {}, hypergraph_file_info *info = nullptr)#

Read a .hg hypergraph file: one hyperedge per line (docs/api/file_formats.md).

A line lists the hyperedge’s vertex ids, decimal integers separated by spaces, tabs, carriage returns or commas; a weighted file ends every line with ; w. Blank lines (and lines of separators only) are skipped; a line whose first character is # or % is a comment. Each line’s ids are sorted and deduplicated; hyperedge i of the result is the i-th kept line. Under hypergraph_read_options::escher_gpu() the result is ESCHER-GPU’s loaded hypergraph (hyperedge id = its key - 1, vertex id = its id - 1), under hsosp() MOSP_ESCHER’s (without its virtual source and target hyperedges; vertex ids and weights bit for bit).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Hyperedge weight type (dyng::unweighted, or integral with weights >= 1).

Parameters:

path – [in] The file.
options – [in] The preprocessing.
info – [out] Optional: the relabelling and what was dropped.

Throws:

io_error – if the file is missing or malformed (path, line and column): a token that is not a decimal integer, an id out of range, a weight missing, misplaced or out of range, more vertices than vertex_t holds.
invalid_argument_error – if the options are invalid (index_base < 0, max_cardinality < -1, a weight range outside [1, max(weight_t)], random_weights for an unweighted type).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The hyperedges and the vertex count.

template<typename vertex_t, typename weight_t> void dyng::io::write_hypergraph(const std::string &path, const hyperedge_list_view<vertex_t, weight_t> &hyperedges, std::int64_t index_base = 1)#

Write hyperedges as a .hg file, read back by read_hypergraph() with the same index_base.

One line per hyperedge: its members plus index_base, separated by single spaces, in list order, then ; w for a weighted list. The vertex count is not written (read_hypergraph() takes the largest id + 1 unless told otherwise).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Hyperedge weight type (dyng::unweighted, or integral).

Parameters:

path – [in] The file (parent directories are created).
hyperedges – [in] The hyperedges (host memory).
index_base – [in] Added to every vertex id (1: the originals’ convention).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if a hyperedge is empty (a .hg file cannot hold it), a member is outside [0, num_vertices), the offsets or weights do not match, index_base is negative, or an array is not in host-accessible memory.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> edge_list<vertex_t, weight_t> dyng::io::read_matrix_market(const std::string &path, const matrix_market_options &options = {})#

Read a Matrix Market coordinate file as a directed edge list (0-based ids).

The header must be %MatrixMarket matrix coordinate <field> <symmetry> with field real, double, integer, complex or pattern and symmetry general, symmetric, skew-symmetric or hermitian; array files are rejected. Comment lines (%) may follow the header; blank lines are ignored. The matrix must be square (it is an adjacency matrix), and the file must hold exactly the announced number of entries, each with 1-based indices in range and the number of value tokens of its field. Symmetric, skew-symmetric and hermitian entries (i, j) with i != j give both edges i -> j and j -> i (skew-symmetric: the mirrored value is negated).

With sort_and_dedupe, duplicate edges keep the value of their LAST entry. With random weights, the weights are drawn after sorting and deduplication, K per edge in edge order. (mospPrep treats hermitian files as general; dynG follows the Matrix Market specification.)

Template Parameters:

vertex_t – Vertex id type of the result.
weight_t – Weight type of the result (integral).

Parameters:

path – [in] The file.
options – [in] Weight source, self-loop and duplicate handling.

Throws:

io_error – if the file cannot be read or is malformed (with path, line and column).
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The edges; num_vertices is the matrix dimension.

template<typename vertex_t, typename weight_t> void dyng::io::write_matrix_market(const std::string &path, const edge_list_view<vertex_t, weight_t> &edges, int weight_column = 0)#

Write an edge list as a general coordinate Matrix Market file (1-based ids).

The field is pattern if edges.num_weights == 0 and integer otherwise; with several weight columns only column weight_column is written.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type (integral).

Parameters:

path – [in] The file (its parent directory is created).
edges – [in] The edges (host memory).
weight_column – [in] The weight column to write (ignored for num_weights == 0).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if weight_column is out of range or the arrays disagree.
out_of_memory_error – if host memory cannot be allocated.

template<typename distance_t> void dyng::io::write_distances(const std::string &path, array_view<const distance_t> distances)#

Write distances, one line “v d” per vertex; d >= infinite_distance() / 2 is “INF”.

Byte-identical to MOSP’s writeDistances().

Template Parameters:

distance_t – Signed integer distance type.

Parameters:

path – [in] The file (parent directories are created).
distances – [in] One distance per vertex (host memory).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if the array is not host-accessible.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t> void dyng::io::write_parents(const std::string &path, array_view<const vertex_t> parents)#

Write a parent array (an SSSP tree), one line “v p” per vertex.

Byte-identical to MOSP’s writeParents().

Template Parameters:

vertex_t – Signed vertex id type.

Parameters:

path – [in] The file (parent directories are created).
parents – [in] One parent per vertex, -1 for none (host memory).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if the array is not host-accessible.
out_of_memory_error – if host memory cannot be allocated.

template<typename distance_t> void dyng::io::write_path_costs(const std::string &path, array_view<const distance_t> costs, int num_objectives)#

Write MOSP path costs, one line “v c1 .. cK” per vertex; a cost >= infinite_distance() / 2 is “INF” (mosp::result::path_costs(), MOSP’s combinedGraph/mospCosts.txt).

Byte-identical to the writeCosts() of MOSP’s mosp driver.

Template Parameters:

distance_t – Signed integer distance type.

Parameters:

path – [in] The file (parent directories are created).
costs – [in] n * num_objectives costs, vertex-major (host memory).
num_objectives – [in] K (>= 1; the length of costs must be a multiple of it).

Throws:

io_error – if the file cannot be written.
invalid_argument_error – if the array is not host-accessible or K does not divide its length.
out_of_memory_error – if host memory cannot be allocated.

template<typename distance_t> std::vector<distance_t> dyng::io::read_distances(const std::string &path, std::int64_t num_vertices)#

Read a distance file: one line “v d” or “v INF” per vertex, each vertex exactly once.

Validation follows MOSP’s readDistances(): ids in [0, num_vertices), d >= 0, every vertex listed exactly once; “INF” reads as infinite_distance<distance_t>().

Template Parameters:

distance_t – Signed integer distance type.

Parameters:

path – [in] The file.
num_vertices – [in] Number of vertices.

Throws:

io_error – if the file is missing or malformed (with path, line and column).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The distances, indexed by vertex.

template<typename vertex_t> std::vector<vertex_t> dyng::io::read_parents(const std::string &path, std::int64_t num_vertices)#

Read an SSSP-tree file: one line “v p” per vertex, p in [-1, num_vertices).

Validation follows MOSP’s readParents(): every vertex listed exactly once.

Template Parameters:

vertex_t – Signed vertex id type.

Parameters:

path – [in] The file.
num_vertices – [in] Number of vertices.

Throws:

io_error – if the file is missing or malformed (with path, line and column).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The parents, indexed by vertex (-1 for none).

void dyng::io::write_histogram_csv(std::ostream &out, array_view<const std::uint64_t> counts, bool include_total = true)#

Write a cycle histogram as CycleEnumeration-GPU’s CSV (CycleHistogram::to_csv()).

The header line “# cycle_size, num_of_cycles”, one line “len, count” per length with a non-zero count in increasing order, then (with include_total) “Total, N”. This is the standard output of the original’s cycle-enum. The text is built first, so on an error nothing is written.

Parameters:

out – [inout] The stream (e.g. std::cout, or a std::ofstream).
counts – [in] counts[len] = cycles of length len (host memory; e.g. cycle_count::result::counts()).
include_total – [in] Append the “Total, N” line.

Throws:

invalid_argument_error – if the array is not host-accessible.
capacity_error – if the total exceeds 2^64 - 1.
io_error – if the stream fails.
out_of_memory_error – if host memory cannot be allocated.

struct batch_file_options#

#include <dyng/io/batch_io.hpp>

Options of read_batches().

Public Members

int num_weights = -1#: Weights per edge insertion (K), or -1: taken from the first insertion of the file (then every insertion must carry as many). Must be 0 or -1 for unweighted batches.

std::int64_t num_vertices = -1#: ids must be < num_vertices; -1: only ids >= 0 are checked

struct hyperedge_batch_file_options#

#include <dyng/io/batch_io.hpp>

Options of read_hyperedge_batches().

Public Members

std::int64_t num_vertices = -1#: members must be < num_vertices; -1: only ids >= 0 are checked

struct batch_file_flags#

#include <dyng/io/batch_io.hpp>

The flags of a .dgb file (batch_file_header::flags; docs/api/file_formats.md). A reader rejects a file with a flag it does not know.

Public Static Attributes

static constexpr std::uint64_t deleted_members = 1U#: Hypergraph files: every deletion also carries the member set of the hyperedge it deleted when the batch was generated (replay by content, PLAN 6.4.6).

static constexpr std::uint64_t expected_ids = 2U#: Hypergraph files: every insertion also carries the id the generating run gave it (replay by key, checked against hyper_apply_summary::inserted_ids).

static constexpr std::uint64_t insert_first = 4U#: Hypergraph files: the batches were generated against a hypergraph with id_reuse::insert_first (the expected ids hold under that order; without the flag, id_reuse::erase_first).

static constexpr std::uint64_t known = deleted_members | expected_ids | insert_first #: Every flag this library knows.

struct batch_file_header#

#include <dyng/io/batch_io.hpp>

The header of a .dgb file: what its batch records hold.

Public Members

std::uint32_t format_version = 1#: the .dgb format version (1)

container_kind kind = container_kind::graph #: graph or hypergraph batches

batch_dtype vertex_type = batch_dtype::int32 #: vertex ids

batch_dtype weight_type = batch_dtype::none #: weights (none: unweighted)

int num_weights = 0#: weights per insertion: K for graphs, 0 or 1 for hypergraphs

std::uint64_t flags = 0#: batch_file_flags (0 for graph files)

std::int64_t num_batches = 0#: batch records in the file (written by batch_writer::close())

template<typename vertex_t> struct hyperedge_batch_annotations#

#include <dyng/io/batch_io.hpp>

What a hyperedge batch record of a .dgb file carries besides the batch, for the flags batch_file_flags::deleted_members and batch_file_flags::expected_ids.

Template Parameters:: vertex_t – Vertex id type.

Public Members

array_view<const std::int64_t> deleted_offsets#: deleted_members: num_deletions() + 1 offsets from 0 into deleted_members.

array_view<const vertex_t> deleted_members#: deleted_members: the member set of every deleted hyperedge, back to back.

array_view<const std::int64_t> expected_ids#: expected_ids: the id of every insertion in the generating run.

class batch_writer#

#include <dyng/io/batch_io.hpp>

Writes a .dgb binary batch file record by record (PLAN Section 5.7; the format is in docs/api/file_formats.md).

The constructor writes the header with a batch count of 0; every write() appends one length-prefixed record with its CRC32; close() writes the count. A file whose writer was not closed is rejected by batch_reader (its count does not match).

Public Functions

batch_writer(const std::string &path, const batch_file_header &header)#

Create (truncate) path and write the header.

Parameters:

path – [in] The file (parent directories are created).
header – [in] The kind, types, K and flags (num_batches is ignored).

Throws:

io_error – if the file cannot be opened or written.
invalid_argument_error – if the header is inconsistent (a graph file with flags or no vertex type, a hypergraph file with K > 1, an unknown flag or format version).

~batch_writer()#: Close the file if close() was not called (errors are ignored).

batch_writer(const batch_writer&) = delete#: not copyable

batch_writer &operator=(const batch_writer&) = delete#: not copyable

batch_writer(batch_writer &&other) noexcept#

Move constructor.

Parameters:: other – [inout] The writer to move from.

batch_writer &operator=(batch_writer &&other) noexcept#

Move assignment.

Parameters:: other – [inout] The writer to move from.
Returns:: *this.

template<typename vertex_t, typename weight_t> void write(const edge_batch_view<vertex_t, weight_t> &batch)#

Append a graph batch.

Template Parameters:

vertex_t – Vertex id type (the header’s).
weight_t – Weight type (the header’s).

Parameters:

batch – [in] The batch (host memory; K = the header’s num_weights).

Throws:

invalid_argument_error – if the file is not a graph file of these types, or the batch is malformed (edge_batch rules of write_batches()).
io_error – if the file cannot be written.
out_of_memory_error – if host memory cannot be allocated.

template<typename vertex_t, typename weight_t> void write(const hyperedge_batch_view<vertex_t, weight_t> &batch, const hyperedge_batch_annotations<vertex_t> &annotations = {})#

Append a hypergraph batch.

Template Parameters:

vertex_t – Vertex id type (the header’s).
weight_t – Hyperedge weight type (the header’s).

Parameters:

batch – [in] The batch (host memory; the rules of write_hyperedge_batches()).
annotations – [in] What the header’s flags require (deleted member sets, expected ids).

Throws:

invalid_argument_error – if the file is not a hypergraph file of these types, the batch is malformed, or the annotations do not match the flags or the batch.
not_supported_error – if the batch has incidence edits (planned for 0.4).
io_error – if the file cannot be written.
out_of_memory_error – if host memory cannot be allocated.

void close()#

Write the batch count and close the file.

Throws:: io_error – if a write or the close failed.

std::int64_t num_batches() const noexcept#

The batches written so far.

Returns:: The count.

struct batch_reader_options#

#include <dyng/io/batch_io.hpp>

Options of batch_reader.

Public Members

std::int64_t num_vertices = -1#: Vertex ids must be < num_vertices; -1: only ids >= 0 (and the type’s range) are checked.

class batch_reader#

#include <dyng/io/batch_io.hpp>

Reads a .dgb binary batch file one batch at a time, in bounded memory (PLAN Section 5.7; the format is in docs/api/file_formats.md).

The constructor reads and checks the header; next() reads the next record, checks its length against the rest of the file before allocating anything, its CRC32 and its contents, and makes it the current batch, whose views stay valid until the next call of next(). The memory held is that of the largest record (twice, plus its device copy, with CUDA resources).

With the resources of the cuda backend the views are in device memory: each record is read into one of two pinned host buffers from the resources’ staging memory resource and copied to the device asynchronously on the resources’ stream (the views are ready in stream order; the reader waits for a pinned buffer’s earlier copy only before it reuses that buffer). With other resources, or none, the views are in host memory.

Every malformed input raises io_error with the path and the byte offset of the record (in the column of the error; the line is 0): a wrong magic, a newer format version, an unknown flag, a size field larger than the rest of the file, a record that is shorter or longer than its counts, a CRC32 that does not match, offsets that are not monotonic, ids out of range, a file that ends before (or after) the header’s batch count.

Public Functions

explicit batch_reader(const std::string &path, const batch_reader_options &options = {})#

Open path and read its header (views in host memory).

Parameters:

path – [in] The file.
options – [in] The vertex count used for validation.

Throws:

io_error – if the file is missing or its header is malformed.
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

batch_reader(const resources &res, const std::string &path, const batch_reader_options &options = {})#

Open path and read its header; the views are in the default memory space of res (device memory for the cuda backend, staged through pinned buffers).

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

Parameters:

res – [in] Execution resources.
path – [in] The file.
options – [in] The vertex count used for validation.

Throws:

io_error – if the file is missing or its header is malformed.
invalid_argument_error – if the options are invalid.
out_of_memory_error – if host memory cannot be allocated.

~batch_reader()#: Release the buffers (device and pinned memory in stream order).

batch_reader(const batch_reader&) = delete#: not copyable

batch_reader &operator=(const batch_reader&) = delete#: not copyable

batch_reader(batch_reader &&other) noexcept#

Move constructor.

Parameters:: other – [inout] The reader to move from.

batch_reader &operator=(batch_reader &&other) noexcept#

Move assignment.

Parameters:: other – [inout] The reader to move from.
Returns:: *this.

const batch_file_header &header() const noexcept#

The file’s header.

Returns:: The header (num_batches as the file states it).

bool next()#

Read the next batch.

The reader is fail-stop: after next() threw, every later next() and batch view throws an io_error naming the record where it failed (a damaged record is never skipped); reopen the file to read it again.

Synchronization:: Stream-ordered; returns before the work completes (asynchronous). With CUDA resources the copy to the device is enqueued on the resources’ stream; the call may wait for the copy of the batch before the previous one.

Throws:

io_error – if the record is malformed or the file ends early, or an earlier call failed.
out_of_memory_error – if host, pinned or device memory cannot be allocated.
cuda_error – if the CUDA runtime reports an error.

Returns:

False at the end of the file (after the header’s batch count).

std::int64_t batch_id() const noexcept#

The record’s batch id (strictly increasing within a file; the writers number 0, 1, …).

Returns:: The id of the current batch, -1 before the first next().

template<typename vertex_t, typename weight_t> edge_batch_view<vertex_t, weight_t> edge_batch() const#

The current batch of a graph file.

Template Parameters:

vertex_t – Vertex id type (the header’s vertex type).
weight_t – Weight type (the header’s weight type).

Throws:

invalid_argument_error – if the file holds hypergraph batches, the types differ from the header’s, or there is no current batch.

Returns:

The view, valid until the next call of next().

template<typename vertex_t, typename weight_t> hyperedge_batch_view<vertex_t, weight_t> hyperedge_batch() const#

The current batch of a hypergraph file.

Template Parameters:

vertex_t – Vertex id type (the header’s vertex type).
weight_t – Hyperedge weight type (the header’s weight type).

Throws:

invalid_argument_error – if the file holds graph batches, the types differ from the header’s, or there is no current batch.

Returns:

The view, valid until the next call of next().

template<typename vertex_t> hyperedge_batch_annotations<vertex_t> annotations() const#

The annotations of the current hypergraph batch (empty arrays for the flags the file does not have).

Template Parameters:: vertex_t – Vertex id type (the header’s vertex type).
Throws:: invalid_argument_error – if the file holds graph batches, the vertex type differs, or there is no current batch.
Returns:: The views, valid until the next call of next().

struct legacy_batch_options#

#include <dyng/io/batch_io.hpp>

Options of read_legacy_batch().

Public Members

int num_weights = 1#: weights per insertion line (K of the graph), >= 0

std::int64_t num_vertices = -1#: ids must be < num_vertices; -1: only ids >= 0 are checked

bool mosp_lenient = false#

MOSP’s accept/reject rules instead of dynG’s stricter ones.

As readChangeBatch() of MOSP-OpenMP@c352151 / MOSP-CUDA@e220ee2: integers after the first 2 + K of an insertion line and after the first 2 of a deletion line are read and ignored, and a deletion line with a single integer is skipped. The compatibility driver dyng-compat-mosp sets it (the parity harness needs the original’s input-rejection semantics); ADR 0010 records why the default is strict.

struct csr_triplet_options#

#include <dyng/io/csr_triplet.hpp>

Options of read_csr_triplet().

Public Members

int num_weights = 0#: Weight columns expected in Values.txt. 0: infer K from the file (the first non-blank line); a graph without edges then needs an explicit value (MOSP’s -k).

struct edge_list_options#

#include <dyng/io/edge_list_io.hpp>

Options of read_edge_list().

Public Members

int num_weights = 0#: Weight columns after src dst (integers). 0 (the default): a third column, if present, is a timestamp, and a fourth column is an error (CycleEnumeration-GPU). With K > 0 a row holds src dst w1..wK [ts]. Must be 0 for weight_t = unweighted and for Matrix Market files.

vertex_ids ids = vertex_ids::compact #: how file ids become graph ids

std::int64_t index_base = 0#: vertex_ids::as_is only: subtracted from every id (1: 1-based)

bool symmetrize = false#: also add (dst, src) for every row (an undirected input)

bool drop_self_loops = true#: skip rows with src == dst (CycleEnumeration-GPU)

duplicate_edges duplicates = duplicate_edges::merge #: rows with a repeated pair

int threads = 0#: parser threads (std::thread); 0 = the hardware concurrency

struct edge_list_info#

#include <dyng/io/edge_list_io.hpp>

What read_edge_list() found besides the edges.

Public Members

std::vector<std::int64_t> external_ids#: vertex_ids::compact: the id in the file of graph vertex i (ascending). Empty for as_is.

std::vector<std::int64_t> timestamps#: duplicate_edges::keep: the timestamp of every returned edge (0 where the row has none). Empty for duplicate_edges::merge.

bool matrix_market = false#: the file had a %MatrixMarket banner

bool symmetric = false#: its symmetry was symmetric, skew-symmetric or hermitian

struct weight_spec#

#include <dyng/io/hypergraph_io.hpp>

Seeded random hyperedge weights (hypergraph_read_options::random_weights): one weight per kept hyperedge, in file order, uniform in [lo, hi].

The weights are drawn from one std::mt19937_64(seed) with the algorithm of libstdc++’s std::uniform_int_distribution, which dynG reproduces itself (so they are the same with any standard library): MOSP_ESCHER’s loader draws them this way (U[1, 100]).

Public Members

std::int64_t lo = 1#: smallest weight (>= 1)

std::int64_t hi = 100#: largest weight (>= lo, <= max of the weight type)

std::uint64_t seed = 1#: seed of the std::mt19937_64

bool hsosp_target_draw = false#: Before the weights, draw (and discard) one vertex in [0, num_vertices - 1] from the same engine, as MOSP_ESCHER’s loadHypergraphFile does for the target vertex of its virtual target hyperedge. The virtual source and target hyperedges themselves are not part of the file’s hypergraph: hyper_sssp adds them (0.4, M11).

struct hypergraph_read_options#

#include <dyng/io/hypergraph_io.hpp>

Options of read_hypergraph().

Every line’s ids are sorted and repeated ids dropped first (both originals do this); then, in file order, hyperedges above max_cardinality are dropped, repeated hyperedges are dropped if dedupe_hyperedges is set, and the ids of the kept ones are relabelled. escher_gpu() and hsosp() are the two originals’ option sets.

Public Members

std::int64_t index_base = 1#: vertex_relabel::none only: subtracted from every id of the file (1: ids 1..n, the convention of both originals’ files; 0: ids 0..n-1).

bool dedupe_hyperedges = false#: Keep only the first hyperedge of every distinct member set (in file order).

std::int64_t max_cardinality = -1#: Drop hyperedges with more than this many distinct members; -1: no limit.

vertex_relabel relabel = vertex_relabel::none #: how file ids become vertex ids

std::optional<weight_spec> random_weights#: For a weighted read: draw the weights instead of reading them from the file (then the file must not have weights). std::nullopt: a weighted read takes ; w from every line.

std::int64_t num_vertices = -1#: vertex_relabel::none only: the vertex count (every id must lie below it after the index_base shift); -1: the largest id + 1.

Public Static Functions

static inline hypergraph_read_options escher_gpu() noexcept#

ESCHER-GPU’s loader (loadHypergraph of ESCHER-GPU@abcf9b2): ids 1..n kept as they are (vertex v becomes v - 1, the vertex count is the largest id), every line a hyperedge (repeated hyperedges kept), no cardinality limit, no weights.

Two differences, both on input ESCHER-GPU rejects: the largest id is 2^31 - 1 (the largest that keeps the vertex count in int32; ESCHER-GPU stops at 2^31 - 2), and a file without hyperedges gives an empty list (ESCHER-GPU fails).

Returns:: The option set.

static inline hypergraph_read_options hsosp(std::uint64_t seed = 20260725U, std::int64_t max_cardinality = 25) noexcept#

MOSP_ESCHER’s H-SOSP loader (loadHypergraphFile of MOSP_ESCHER@4b86159, hsospBench –hg): hyperedges of at most max_cardinality vertices, vertices numbered by first appearance, weights U[1, 100] from std::mt19937_64(seed) after its target draw.

Parameters:

seed – [in] The seed (hsospBench’s –seed, default 20260725).
max_cardinality – [in] The limit (hsospBench’s –maxcard, default 25).

Returns:

The option set.

struct hypergraph_file_info#

#include <dyng/io/hypergraph_io.hpp>

What read_hypergraph() found besides the hyperedges.

Public Members

std::vector<std::int64_t> external_ids#: vertex_relabel::dense_sorted and first_appearance: the id in the file of vertex i. Empty for vertex_relabel::none.

std::int64_t lines = 0#: non-empty, non-comment lines (hyperedges in the file)

std::int64_t repeated_members = 0#: ids dropped because they repeat within a line

std::int64_t over_cardinality = 0#: hyperedges dropped by max_cardinality

std::int64_t repeated_hyperedges = 0#: hyperedges dropped by dedupe_hyperedges

struct random_weights#

#include <dyng/io/matrix_market.hpp>

Seeded random weights (the mospPrep mtx2csr defaults: K = 1, [1, 100], seed 12345).

Public Members

int num_weights = 1#: K, the number of weight columns (>= 1).

std::int64_t min = 1#: smallest weight (inclusive)

std::int64_t max = 100#: largest weight (inclusive); max - min < 2^32

std::uint32_t seed = 12345#: seed of std::mt19937

struct matrix_market_options#

#include <dyng/io/matrix_market.hpp>

Options of read_matrix_market().

Public Members

matrix_market_weights weights = matrix_market_weights::automatic #: weight source

random_weights random = {}#: used with matrix_market_weights::random

bool drop_self_loops = true#: skip diagonal entries (mospPrep)

bool sort_and_dedupe = true#: sort edges by (source, destination), drop duplicates (mospPrep)