Graphs#

The dynamic graph container dyng::graph, its properties (row order, parallel edges, batch semantics), views, CSR and edge-list inputs, and the summary of an applied batch.

enum class dyng::row_layout : std::uint8_t#

Storage layout of the rows of a graph.

Values:

enumerator compact#: exact CSR; a batch rebuilds the touched rows (the only layout in 0.1)

enumerator slotted#: fixed per-vertex slot ranges (DynLP); planned for 0.4

enumerator slack#: per-row headroom with a tail region; planned for 0.4

enum class dyng::row_order : std::uint8_t#

Order of the neighbours inside a row.

Values:

enumerator sorted#: rows sorted by neighbour id (stable: parallel edges keep their relative order)

enumerator append#: surviving edges keep their order; new edges are appended to their row (MOSP)

enum class dyng::multi_edges : std::uint8_t#

Whether parallel edges (several (u,v) in one row) may exist.

Values:

enumerator forbid#: a simple graph: duplicate (u,v) in the input are merged (the last one wins)

enumerator allow#: parallel edges are kept; deletions and upserts act on the first (u,v) in the row

std::string_view dyng::to_string(row_layout layout) noexcept#

The lower-case name of a row layout (“compact”, “slotted”, “slack”).

Parameters:: layout – [in] The layout.
Returns:: A static string naming layout (the enumerator’s name).

std::string_view dyng::to_string(row_order order) noexcept#

The lower-case name of a row order (“sorted”, “append”).

Parameters:: order – [in] The order.
Returns:: A static string naming order (the enumerator’s name).

std::string_view dyng::to_string(multi_edges rule) noexcept#

The lower-case name of a parallel-edge rule (“forbid”, “allow”).

Parameters:: rule – [in] The rule.
Returns:: A static string naming rule (the enumerator’s name).

std::string_view dyng::to_string(batch_semantics::existing_insert rule) noexcept#

The lower-case name of an existing-edge insertion rule (“upsert”, “error”, “ignore”).

Parameters:: rule – [in] The rule.
Returns:: A static string naming rule (the enumerator’s name).

std::string_view dyng::to_string(batch_semantics::missing_delete rule) noexcept#

The lower-case name of a missing-edge deletion rule (“ignore”, “error”).

Parameters:: rule – [in] The rule.
Returns:: A static string naming rule (the enumerator’s name).

std::string_view dyng::to_string(batch_semantics::self_loop rule) noexcept#

The lower-case name of a self-loop rule (“keep”, “drop”, “error”).

Parameters:: rule – [in] The rule.
Returns:: A static string naming rule (the enumerator’s name).

struct apply_summary#

#include <dyng/graph/apply_summary.hpp>

Counters returned by graph::apply() and contained in every algorithm’s stats.

All counters are deterministic. For an undirected graph every batch edge counts once per stored direction.

Public Members

std::int64_t inserted_edges = 0#: insertions that added a new edge to a row

std::int64_t updated_edges = 0#: insertions that overwrote an existing edge (upsert)

std::int64_t deleted_edges = 0#: deletions that removed an edge

std::int64_t ignored_deletions = 0#: deletions of edges that did not exist

std::int64_t dropped_self_loops = 0#: self-loop operations skipped (self_loop::drop)

std::int64_t cancelled_pairs = 0#: insert/delete pairs cancelled (set semantics; from M2)

std::int64_t inserted_vertices = 0#: vertices added (explicitly or by vertex growth)

std::int64_t deleted_vertices = 0#: vertices removed

std::int64_t num_vertices_after = 0#: the vertex count after the batch

std::int64_t ignored_insertions = 0#: insertions of existing edges left unchanged (ignore)

template<typename vertex_t, typename edge_t, typename weight_t> struct csr_view#

#include <dyng/graph/csr.hpp>

A non-owning description of a CSR graph: row offsets, neighbours, weight columns.

Rows are indexed by source for out-edges and by destination for in-edges (the transposed graph). The arrays may live in any memory space; element access needs a host-accessible space.

Template Parameters:

vertex_t – Vertex id type.
edge_t – Edge offset type.
weight_t – Weight type.

Public Functions

inline vertex_t num_vertices() const noexcept#

Number of rows.

Returns:: row_ptr.size() - 1, or 0 for an empty view.

inline edge_t num_edges() const noexcept#

Number of edges.

Returns:: col_ind.size().

inline array_view<const weight_t> weight_column(int k) const#

The weights of one objective, one per edge in row order.

Parameters:: k – [in] Objective in [0, num_weights).
Throws:: invalid_argument_error – if k is out of range.
Returns:: A view of num_edges() weights.

Public Members

array_view<const edge_t> row_ptr#: num_vertices() + 1 offsets, row_ptr[0] == 0

array_view<const vertex_t> col_ind#: the neighbour of each edge, in row order

array_view<const weight_t> weights#: num_weights columns of num_edges() values each

int num_weights = 0#: number of weight columns (0: unweighted)

template<typename vertex_t, typename edge_t, typename weight_t> struct csr#

#include <dyng/graph/csr.hpp>

An owning host CSR graph with objective-major weight columns.

A plain aggregate: the fields may be filled directly. graph::from_csr() validates it.

Template Parameters:

vertex_t – Vertex id type.
edge_t – Edge offset type.
weight_t – Weight type.

Public Functions

inline vertex_t num_vertices() const noexcept#

Number of rows.

Returns:: row_ptr.size() - 1, or 0 if row_ptr is empty.

inline edge_t num_edges() const noexcept#

Number of edges.

Returns:: col_ind.size().

inline const weight_t &weight(edge_t e, int k) const noexcept#

The weight of one edge in one column (unchecked).

Parameters:

e – [in] Edge index in [0, num_edges()).
k – [in] Objective in [0, num_weights).

Returns:

weights[k * num_edges() + e].

inline csr_view<vertex_t, edge_t, weight_t> view() const noexcept#

A read-only view of the arrays.

Returns:: A csr_view in host memory; valid while this object is alive and unmodified.

Public Members

std::vector<edge_t> row_ptr#: num_vertices() + 1 offsets, row_ptr[0] == 0

std::vector<vertex_t> col_ind#: the neighbour of each edge, in row order

std::vector<weight_t> weights#: num_weights columns of num_edges() values each

int num_weights = 0#: number of weight columns (0: unweighted)

template<typename vertex_t, typename weight_t> struct edge_list_view#

#include <dyng/graph/edge_list.hpp>

A non-owning edge list: parallel arrays of sources, destinations and weights.

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type.

Public Functions

inline std::size_t num_edges() const noexcept#

Number of edges.

Returns:: src.size().

Public Members

vertex_t num_vertices = 0#: ids lie in [0, num_vertices)

array_view<const vertex_t> src#: source of each edge

array_view<const vertex_t> dst#: destination of each edge

array_view<const weight_t> weights#: num_weights per edge, edge-major

int num_weights = 0#: weights per edge (0: unweighted)

template<typename vertex_t, typename weight_t> struct edge_list#

#include <dyng/graph/edge_list.hpp>

An owning host edge list (COO).

Template Parameters:

vertex_t – Vertex id type.
weight_t – Weight type.

Public Functions

inline std::size_t num_edges() const noexcept#

Number of edges.

Returns:: src.size().

inline void add_edge(vertex_t u, vertex_t v, std::initializer_list<weight_t> w = {})#

Append one edge.

Exception safety:: Strong: after an exception the list is unchanged.

Parameters:

u – [in] Source.
v – [in] Destination.
w – [in] Its num_weights weights.

Throws:

invalid_argument_error – if w does not hold num_weights values.
out_of_memory_error – if the arrays cannot grow.

inline edge_list_view<vertex_t, weight_t> view() const noexcept#

A read-only view of the arrays.

Returns:: An edge_list_view in host memory; valid while this object is alive and unmodified.

Public Members

vertex_t num_vertices = 0#: ids lie in [0, num_vertices)

std::vector<vertex_t> src#: source of each edge

std::vector<vertex_t> dst#: destination of each edge

std::vector<weight_t> weights#: num_weights per edge, edge-major

int num_weights = 0#: weights per edge (0: unweighted); last, as in edge_list_view

template<typename vertex_t = std::int32_t, typename edge_t = std::int32_t, typename weight_t = std::int32_t> class graph#

#include <dyng/graph/graph.hpp>

A dynamic directed (or symmetric) graph with K weight columns.

The graph owns its storage and a version counter that increases by one with every applied batch; results computed on the graph remember the version they match and the identity of the graph state (a process-wide unique value that every construction and every batch renews and clone() copies), so a result is detected as stale when it is used with another graph, or with a graph variable that was reassigned since, even if the version counters are equal. The storage belongs to the backend of the resources that created it: algorithms refuse resources of the other kind (host backends versus cuda) instead of copying the graph silently, and to_backend(res) (or clone(res)) makes a copy for other resources.

A graph built with CUDA resources has two copies of its out-edges, at least one of which is current: a host CSR and a resident device copy (one weight column per objective), uploaded on first use. The in-edges of the device copy are built on the device only when an engine needs them (sssp does; cycle_count reads the out-edges only). A batch takes one of two paths (ADR 0020, docs/adr/0020-resident-device-graph-and-one-step-0.md):

the device merge: when the device copy is resident, the batch semantics is batch_semantics::set() (as_sets), the graph has no weight columns and 32-bit vertex ids, and the resources are CUDA resources of the graph’s device, the normalized batch is merged into the sorted rows on the device (CycleEnumeration-GPU’s build_next_rows_kernel). The device copy becomes the new state and the host CSR is stale until something reads it: view(), to_csr(), check_integrity() and clone() download it once. Step 0 of the next batch reads the device copy, so a chain of batches never downloads the graph.
the host apply, in every other case: the batch is applied to the host CSR (as MOSP-CUDA applies it) and the device copy is dropped, then uploaded again on first use. num_vertices() and num_edges() never download.

Thread safety. A graph is not thread-safe. Calls that only read it (view(), the accessors, to_csr(), an algorithm’s compute() on it) may run concurrently with each other. A call that changes it (apply(), reserve(), an algorithm’s update(), dyng::update()) must not overlap any other call on the same graph or on a result being updated with it: two concurrent updates of one graph, or reading a result on one thread (or stream) while another updates it, are undefined unless the caller orders them (a mutex, or stream events on CUDA). Distinct graphs and results may be used concurrently through copies of one resources handle.

Instantiated for (vertex_t, edge_t, weight_t) = (int32, int32, int32), (int32, int64, int32) and (int64, int64, int32), and without weights for (int32, int32, unweighted) and (int32, int64, unweighted). A graph with weight_t = unweighted has no weight columns. The default edge offset type is int32, the originals’ type, fixed by the edge_t benchmark (ADR 0009: 64-bit offsets cost more than 3 % on the parity suites). Construction is checked: a graph whose edge count does not fit edge_t (from_edges(), or a batch that grows it past 2^31 - 1 edges with int32) throws capacity_error naming the int64 instantiation.

Template Parameters:

vertex_t – Vertex id type (signed).
edge_t – Edge offset type (signed; int32 by default, int64 for more than 2^31 - 1 edges).
weight_t – Weight type.

Public Types

using vertex_type = vertex_t #: vertex id type

using edge_type = edge_t #: edge offset type

using weight_type = weight_t #: weight type

using view_type = graph_view<vertex_t, edge_t, weight_t>#: the view type

using csr_type = csr<vertex_t, edge_t, weight_t>#: the owning CSR type

Public Functions

explicit graph(const graph_properties &props = {})#

An empty graph (no vertices) with the given properties.

Parameters:

props – [in] The properties (see graph_properties).

Throws:

not_supported_error – if props.layout is not row_layout::compact, or the batch semantics cannot be applied (batch_semantics::as_sets without deletions_first, with an upsert, or on rows that are not row_order::sorted with multi_edges::forbid).
out_of_memory_error – if host memory cannot be allocated.

graph(graph &&other) noexcept#

Move constructor.

Parameters:: other – [inout] The graph to move from; it may only be assigned to or destroyed after.

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

Move assignment.

Parameters:: other – [inout] The graph to move from; it may only be assigned to or destroyed after.
Returns:: *this.

graph(const graph&) = delete#: not copyable: use clone()

graph &operator=(const graph&) = delete#: not copyable: use clone()

~graph()#: releases the storage

graph clone(const resources &res) const#

A deep copy (same properties, storage, version and state) for the resources res.

The copy belongs to the backend of res: this is how a graph moves between the host backends and cuda (a CUDA copy uploads its device copy on first use).

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

Parameters:

res – [in] Execution resources of the copy.

Throws:

invalid_argument_error – for a moved-from graph.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The copy.

graph to_backend(const resources &res) const#

The graph for the backend of res: the explicit move between the host backends and cuda that the placement errors name (a graph is never copied between them silently).

In this release the same as clone(res) (a deep copy that belongs to the backend of res; the original is unchanged), since a CUDA graph keeps its authoritative CSR on the host; ADR 0017 item 3.

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

Parameters:

res – [in] Execution resources of the new graph.

Throws:

invalid_argument_error – for a moved-from graph.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The graph for res.

void reserve(const resources &res, edge_t edge_capacity)#

Pre-size the current storage (out-edges and, if stored, in-edges) for edge_capacity edges.

In this release reserve() only sizes the storage the graph holds now: the host apply() is the straight port of MOSP’s applyChangeBatch(), which builds a new CSR per batch, so the first apply() after reserve() allocates new arrays and the reserved capacity is released. It gives no guarantee against reallocation until the resident apply replaces the port (invariant I9 exempts the port until then; docs/developer/framework.md, “Budgets”).

Synchronization:: Blocks until the work has completed (synchronous).
Exception safety:: Strong for the contents: the edges, the version and every result’s validity are unchanged (some arrays may keep a larger capacity).

Parameters:

res – [in] Execution resources.
edge_capacity – [in] Expected maximum number of stored edges.

Throws:

invalid_argument_error – if edge_capacity is negative or the graph was moved from.
out_of_memory_error – if the storage cannot be allocated.

vertex_t num_vertices() const noexcept#

Number of vertices.

Returns:: The vertex count.

edge_t num_edges() const noexcept#

Number of stored (directed) edges.

Returns:: The edge count (an undirected edge counts twice, a self-loop once).

int num_weights() const noexcept#

Number of weight columns (objectives).

Returns:: K >= 0.

const graph_properties &properties() const noexcept#

The properties of the graph.

Returns:: The properties given at construction (num_weights as stored).

bool is_directed() const noexcept#

Whether the graph is directed.

Returns:: properties().directed.

bool has_transposed() const noexcept#

Whether the in-edges are stored.

Returns:: properties().store_transposed.

memory_space space() const noexcept#

The memory space of the storage.

Returns:: memory_space::device for a graph built with CUDA resources (its resident device copy; the host CSR that view() and to_csr() read is kept as well, and after a device merge downloaded lazily on the first host read, see the class description), memory_space::host otherwise.

std::uint64_t version() const noexcept#

The version counter.

Returns:: 0 after construction; +1 per applied batch.

view_type view() const#

A read-only description of the storage at the current version (host memory, also for a graph built with CUDA resources).

For a CUDA graph whose current state a device merge produced, the host CSR is downloaded first (once per state; a synchronous copy on the stream of the resources that built the state). If the in-edges are stored but not built yet for this version (they are built on first use), this call builds them (with the thread count of the resources that built the graph); it is safe to call concurrently with other read-only calls.

Throws:: out_of_memory_error – if the in-edges must be built and memory cannot be allocated.
Returns:: The view; invalidated by the next apply().

apply_summary apply(const resources &res, const edge_batch_view<vertex_t, weight_t> &batch)#

Apply a batch to the structure (and weights) of the graph.

The batch is interpreted under properties().semantics (see batch_semantics). The in-edges of the new version are built on first use. Results computed on the previous version become stale (their update() throws stale_result_error); use the algorithms’ update() to apply a batch and keep a result current.

On a CUDA graph the batch is merged on the device when the class description’s conditions hold (resident device copy, batch_semantics::set(), no weight columns, 32-bit vertex ids): the host CSR is then left stale and downloaded on the next host read. Otherwise it is applied to the host CSR and the device copy is dropped (uploaded again on first use). ADR 0020.

Synchronization:: Blocks until the work has completed (synchronous).
Exception safety:: Strong: the batch is validated and the next state is built completely before it replaces the current one, so a throwing apply() leaves the graph (storage, version, state identity) unchanged.

Parameters:

res – [in] Execution resources (host threads; for the device merge, CUDA resources of the graph’s device).
batch – [in] The batch (any memory space: it is read on the host, where its normalization, Step 0, runs on both paths, so arrays in device memory are copied once under res.get_copy_policy()).

Throws:

invalid_argument_error – if an id is negative or out of range (without vertex growth), the weights do not match num_weights(), a semantics rule says error, or an array must be copied and the copy policy is copy_policy::error.
capacity_error – if the edge count after the batch does not fit edge_t.
not_supported_error – for vertex insertions or deletions (planned for 0.4).
out_of_memory_error – if host or device memory cannot be allocated.
cuda_error – if the CUDA runtime reports an error (device merge).

Returns:

What the batch did.

csr_type to_csr(const resources &res) const#

A host copy of the out-edges (downloaded first, once per state, if a device merge left the host CSR of a CUDA graph stale).

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

Parameters:

res – [in] Execution resources.

Throws:

invalid_argument_error – for a moved-from graph.
out_of_memory_error – if host memory cannot be allocated.

Returns:

The out-edge CSR with objective-major weights.

void check_integrity(const resources &res) const#

Check the storage invariants (offsets, ids, row order, simple graph, in-edges).

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

Parameters:: res – [in] Execution resources.
Throws:: internal_error – if an invariant is broken.

Public Static Functions

static graph from_edges(const resources &res, edge_list_view<vertex_t, weight_t> edges, const graph_properties &props = {})#

Build a graph from an edge list.

Edges are grouped by source; inside a row they keep their input order under row_order::append and are stably sorted by destination under row_order::sorted. Under multi_edges::forbid, duplicate (u,v) are merged: the first position is kept, the last weights win. Self-loops follow props.semantics.on_self_loop. For an undirected graph every edge (u,v) is stored in both directions. The number of weight columns is taken from edges.

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

Parameters:

res – [in] Execution resources (the graph belongs to its backend).
edges – [in] The edges (any memory space: built on the host, so arrays in device memory are copied once under res.get_copy_policy()); ids must lie in [0, edges.num_vertices).
props – [in] The properties of the new graph.

Throws:

invalid_argument_error – if an id is out of range, the arrays disagree in size, a self-loop is present under self_loop::error, or an array must be copied and the copy policy is copy_policy::error.
capacity_error – if the number of stored edges does not fit edge_t (use the int64 edge_t instantiation).
not_supported_error – for a layout other than compact, or batch semantics that cannot be applied (as graph(const graph_properties&)).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The graph at version 0.

static graph from_csr(const resources &res, csr_view<vertex_t, edge_t, weight_t> csr, const graph_properties &props = {})#

Build a graph from a CSR (the out-edges).

The CSR is validated (monotone offsets from 0, neighbours in range, weight array size). Under row_order::sorted rows are stably sorted; under multi_edges::forbid duplicates are merged as in from_edges(). Self-loops follow props.semantics.on_self_loop. For an undirected graph the CSR must already be symmetric (each direction stored). The number of weight columns is taken from csr. The in-edges (props.store_transposed) are built on first use, not here (the same holds for from_edges() and after apply()).

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

Parameters:

res – [in] Execution resources (the graph belongs to its backend).
csr – [in] The out-edge CSR (objective-major weights; any memory space: arrays in device memory are copied to the host once under res.get_copy_policy()).
props – [in] The properties of the new graph.

Throws:

invalid_argument_error – if the CSR is malformed, or an array must be copied and the copy policy is copy_policy::error.
not_supported_error – for a layout other than compact, or batch semantics that cannot be applied (as graph(const graph_properties&)).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The graph at version 0.

static graph from_csr(const resources &res, csr_type &&csr, const graph_properties &props = {})#

Build a graph from a CSR it may take over (the out-edges).

The same graph as from_csr(res, csr.view(), props). When the CSR already is what props ask for (directed, self-loops kept or absent, rows in the requested order and without forbidden parallel edges; for example any CSR under graph_properties::mosp_compatible()), its arrays are moved into the graph instead of copied; csr is then left empty. Otherwise it is left unchanged.

Synchronization:: Blocks until the work has completed (synchronous).
Exception safety:: Strong for every error in the input (invalid_argument_error, not_supported_error): csr is unchanged, because its arrays are taken over only once they are known to be final. Basic for out_of_memory_error: csr may have been left empty.

Parameters:

res – [in] Execution resources (the graph belongs to its backend).
csr – [inout] The out-edge CSR (objective-major weights).
props – [in] The properties of the new graph.

Throws:

invalid_argument_error – if the CSR is malformed.
not_supported_error – for a layout other than compact, or batch semantics that cannot be applied (as graph(const graph_properties&)).
out_of_memory_error – if host memory cannot be allocated.

Returns:

The graph at version 0.

struct batch_semantics#

#include <dyng/graph/graph_properties.hpp>

How a batch of edge changes is interpreted.

The default-constructed value equals upsert_last_wins(), the semantics of MOSP’s applyChangeBatch():

deletions first, in batch order; each removes the FIRST remaining (u,v) of row u;
then insertions in batch order; an insertion of an existing (u,v) overwrites the weights of the first remaining (u,v) (so the last insertion of a pair wins), otherwise the edge is appended to row u (or merged into it under row_order::sorted).

Public Types

enum class existing_insert : std::uint8_t#

What an insertion of an edge that already exists does.

Values:

enumerator upsert#: overwrite the weights of the first existing (u,v)

enumerator error#: throw invalid_argument_error

enumerator ignore#: leave the existing edge unchanged

enum class missing_delete : std::uint8_t#

What a deletion of an edge that does not exist does.

Values:

enumerator ignore#: nothing (counted in apply_summary::ignored_deletions)

enumerator error#: throw invalid_argument_error

enum class self_loop : std::uint8_t#

What an insertion or deletion of a self-loop (u,u) does.

Values:

enumerator keep#: treat it like any other edge (MOSP)

enumerator drop#: skip it (counted in apply_summary::dropped_self_loops)

enumerator error#: throw invalid_argument_error

Public Members

existing_insert on_existing_insert = existing_insert::upsert #: insertion of an existing edge

missing_delete on_missing_delete = missing_delete::ignore #: deletion of a missing edge

self_loop on_self_loop = self_loop::keep #: self-loops in the batch

bool deletions_first = true#: true: deletions, then insertions; false: the reverse

bool allow_vertex_growth = true#: an insertion naming v >= num_vertices grows the vertex set

bool as_sets = false#

true: the deletions and the insertions are read as two SETS (Step 0 of set()).

Before anything is applied, each list is sorted by (source, destination) and deduplicated (the first insertion of a pair in batch order supplies its weights); deletions of edges that do not exist and insertions of edges that exist are no-ops and leave the lists, except that an edge the batch both deletes and inserts stays in both lists (it is removed, then added back; apply_summary::cancelled_pairs counts these pairs). The two lists, in this order, are the net structural change the algorithms see (for example the change edges of cycle_count, whose position in the sorted list is their ownership id). The switches above keep their meaning: on_missing_delete and on_existing_insert decide what the no-ops do (ignore or error), on_self_loop what self-loops do, and allow_vertex_growth whether insertions may name new vertices.

Not supported with as_sets: on_existing_insert = upsert (an upsert of the weights of an existing edge is not a structural change; delete and re-insert the edge to change its weights), deletions_first = false, and rows that are not row_order::sorted with multi_edges::forbid (the lists are merged into the sorted rows of a simple graph). A graph constructed with such properties throws not_supported_error at construction.

Public Static Functions

static inline constexpr batch_semantics upsert_last_wins() noexcept#

MOSP applyChangeBatch() / updateGraphCSR() semantics (the default).

Returns:: Upsert, ignore missing deletions, keep self-loops, deletions first, vertex growth.

static inline constexpr batch_semantics set() noexcept#

CycleEnumeration-GPU prepare_batch() / apply_batch() semantics: a batch is two sets.

as_sets with: insertions of existing edges and deletions of missing edges ignored (dropped from the normalized batch), self-loops dropped, deletions first, vertex growth. The graph after the batch has the edges (E minus Del) plus Ins, without self-loops; the normalized batch equals the original’s prepare_batch() exactly.

Returns:: The set semantics.

struct graph_properties#

#include <dyng/graph/graph_properties.hpp>

The properties of a graph: direction, stored in-edges, weights, layout, row order, multigraph switch and batch semantics.

Public Members

bool directed = true#: false: stored symmetric; a batch edge (u,v) changes both

bool store_transposed = true#: keep the in-edges (CSC, built on first use); sssp, mosp and cycle_count need them

int num_weights = 1#: Number of weight columns (objectives); 0 for an unweighted graph. graph::from_edges() and graph::from_csr() take the number of columns from their input and overwrite this field.

row_layout layout = row_layout::compact #: storage layout of the rows

double headroom = 0.125#: spare capacity for row_layout::slack

row_order order = row_order::sorted #: the general default: sorted rows

multi_edges parallel_edges = multi_edges::forbid #: the general default: a simple graph

batch_semantics semantics = batch_semantics::upsert_last_wins()#: how batches are applied

Public Static Functions

static inline constexpr graph_properties mosp_compatible() noexcept#

Byte parity with MOSP’s CSR: append order, parallel edges allowed, upsert_last_wins.

Returns:: Directed, transposed stored, compact rows, row_order::append, multi_edges::allow.

static inline constexpr graph_properties cycle_enum_compatible() noexcept#

Parity with CycleEnumeration-GPU’s DirectedGraph: sorted rows of a simple graph and set() batch semantics.

A graph built with these properties from the same edges has the CSR of the original’s build_directed_graph(), and every applied batch gives the CSR of its apply_batch() (byte for byte, row offsets and neighbours).

Returns:: Directed, transposed stored, compact rows, row_order::sorted, multi_edges::forbid, batch_semantics::set(), no weight columns.

template<typename vertex_t, typename edge_t, typename weight_t> struct graph_view#

#include <dyng/graph/graph_view.hpp>

A read-only description of the storage of a graph at one version.

A view is invalidated by the next graph::apply() (compare version with graph::version()). For row_layout::compact, out is the exact out-edge CSR and in the in-edge CSR (the transposed graph, rows indexed by destination, each row listing sources in increasing order of their out-edge position).

Template Parameters:

vertex_t – Vertex id type.
edge_t – Edge offset type.
weight_t – Weight type.

Public Functions

inline vertex_t num_vertices() const noexcept#

Number of vertices.

Returns:: out.num_vertices().

inline edge_t num_edges() const noexcept#

Number of stored (directed) edges.

Returns:: out.num_edges().

inline int num_weights() const noexcept#

Number of weight columns.

Returns:: out.num_weights.

Public Members

csr_view<vertex_t, edge_t, weight_t> out#: out-edges (rows indexed by source)

csr_view<vertex_t, edge_t, weight_t> in#: in-edges; empty unless has_transposed

bool has_transposed = false#: whether in describes the in-edges

bool directed = true#: false: every edge is stored in both directions

row_layout layout = row_layout::compact #: the storage layout of the rows

std::uint64_t version = 0#: the graph version this view describes