Hypergraphs#

The dynamic hypergraph container dyng::hypergraph (ADR 0041): hyperedges with 0-based int64 ids on the ESCHER store, changed by batches of hyperedge deletions and insertions whose new ids come from the store’s best-fit reuse (hyper_apply_summary::inserted_ids); its properties (hypergraph_storage, line_graph_policy, id_reuse, capacity_policy with the presets escher_gpu() and mosp_escher(extra)), the hyperedge list, the batch, the incidence and line-graph views and the storage counters. These headers are frozen (the M8b API review, ADR 0047: The hypergraph API review and freeze (0.3)): a change of a declaration fails the API checks unless the pull request is an api-change. By the plan’s default they are stable from 0.3.0, which awaits the author’s confirmation at that release. The concepts (ids, id_reuse with a worked example, best-fit reuse and the surplus drop rule, the capacity presets, the index limits, the line graph) are explained in Hypergraphs and hyperedge ids; the Python layer is dyng.Hypergraph (Use hypergraphs from Python).

The line graph (ADR 0042). hypergraph::h2h() is the line graph: one sorted row per id, the ids of the hyperedges that share a vertex with it, and out[r], the offset of the first neighbour above r (the oriented wedges of triad_count). Under line_graph_policy::sorted_merge it is built with the hypergraph and kept by every apply() with ESCHER-GPU’s sorted delta merge (on the CPU backends a host form of the same merge, with the same layout); under automatic (the default) the first h2h() builds it, and apply() keeps it from then on; under none h2h() throws. The views (h2v(), v2h(), h2h()) are built on first use per version, in the hypergraph’s memory space, and never by apply(); store_stats().device_bytes counts the stores and the row views the container keeps per commit (ESCHER-GPU’s DynamicHypergraph::deviceBytes() scope). dyng::testing::rebuild_line_graph (dyng/testing/line_graph_oracle.hpp) recomputes a line graph from the hyperedges for tests.

Updating results (ADR 0043). dyng::update(res, h, batch.view(), r1, r2...) applies a hyperedge batch to h once and brings every result of a hypergraph algorithm up to date: the batch is validated and normalized once, every result reads the hypergraph before the batch, the batch is committed once, then every result reads the hypergraph after it, with the ids the batch gave (stats.batch.inserted_ids). A result whose update fails after the commit is poisoned and the others are still updated; an error before the commit changes nothing.

Planned for 0.4 (declared now, so 0.4 adds behaviour, not declarations): hypergraph_storage::slack_csr, line_graph_policy::slack_csr and the incidence edits of a batch (hyperedge_batch::delete_incidence() / insert_incidence() and their accessors, the *_incidence_* arrays of the view) raise not_supported_error naming 0.4.

enum class dyng::hypergraph_storage : std::uint8_t#

How the incidences of a hypergraph are stored.

Values:

enumerator escher#

the ESCHER store (ESCHER, IPDPS’26; best-fit reuse, ESCHER+, TKDE’26)

enumerator slack_csr#

slack rows (H-SOSP’s DeviceIncidence); planned for 0.4, not_supported_error now

enum class dyng::line_graph_policy : std::uint8_t#

How the line graph (h2h: hyperedge to overlapping hyperedges) is kept.

Values:

enumerator none#

no line graph: hypergraph::h2h() throws

enumerator automatic#

built when it is first read (hypergraph::h2h(), or an algorithm that reads it), then maintained as sorted_merge

enumerator sorted_merge#

built with the hypergraph and maintained by every batch with ESCHER-GPU’s sorted delta merge (needs v2h)

enumerator slack_csr#

H-SOSP’s slack h2h CSR; planned for 0.4, not_supported_error now.

enum class dyng::id_reuse : std::uint8_t#

The order in which one batch’s deletions and insertions reach the store, which decides the ids that best-fit reuse gives the inserted hyperedges.

Values:

enumerator erase_first#

deletions first (ESCHER’s order): a slot freed by the batch can be reused

enumerator insert_first#

insertions first (H-SOSP’s order): only slots freed before the batch

std::string_view dyng::to_string(hypergraph_storage storage) noexcept#

The enumerator’s name (“escher”, “slack_csr”).

Parameters:

storage – [in] The value.

Returns:

Its name, or “unknown”.

std::string_view dyng::to_string(line_graph_policy policy) noexcept#

The enumerator’s name (“none”, “automatic”, “sorted_merge”, “slack_csr”).

Parameters:

policy – [in] The value.

Returns:

Its name, or “unknown”.

std::string_view dyng::to_string(id_reuse reuse) noexcept#

The enumerator’s name (“erase_first”, “insert_first”).

Parameters:

reuse – [in] The value.

Returns:

Its name, or “unknown”.

struct hyper_apply_summary#
#include <dyng/hypergraph/hyper_apply_summary.hpp>

Returned by hypergraph::apply(): the counts of one batch and the id of every inserted hyperedge.

The ids come from the store’s best-fit reuse and are authoritative: read them here, never predict them (a slot freed earlier, or in the same batch under id_reuse::erase_first, may be reused, and the surplus rule may give out an id that was dead before the batch).

Public Members

std::int64_t inserted_hyperedges = 0#

hyperedges inserted

std::int64_t deleted_hyperedges = 0#

live hyperedges deleted

std::int64_t inserted_incidences = 0#

(hyperedge, vertex) incidences added by edits (0.4)

std::int64_t deleted_incidences = 0#

(hyperedge, vertex) incidences removed by edits (0.4)

std::int64_t skipped_ops = 0#

Every skipped operation: in 0.3 ignored_deletions + dropped_members; incidence edits (0.4) add the edits they skip (on a dead hyperedge, of a non-member, …).

std::int64_t ignored_deletions = 0#

deletions of dead, out-of-range or repeated ids

std::int64_t dropped_members = 0#

repeated members of inserted hyperedges dropped

std::int64_t num_hyperedges_after = 0#

live hyperedges after the batch

std::int64_t id_bound_after = 0#

hyperedge_id_bound() after the batch

std::vector<std::int64_t> inserted_ids#

the id of every inserted hyperedge, batch order

template<typename vertex_t, typename weight_t>
struct hyperedge_batch_view#
#include <dyng/hypergraph/hyperedge_batch.hpp>

A non-owning batch of hypergraph changes. An empty array means “none of this kind”.

Four kinds of operations: deletions of whole hyperedges (by id), insertions of whole hyperedges (a CSR of member lists, one weight each for a weighted hypergraph), and the incidence edits (a vertex removed from or added to a live hyperedge; planned for 0.4: hypergraph::apply() raises not_supported_error when they are not empty). A “replace” is a deletion plus an insertion. The order in which deletions and insertions reach the store is a property of the hypergraph (hypergraph_properties::reuse).

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Weight type (unweighted: no weights).

Public Functions

inline std::size_t num_insertions() const noexcept#

Number of hyperedge insertions.

Returns:

insert_offsets.size() - 1, or 0 for empty offsets.

inline std::size_t num_deletions() const noexcept#

Number of hyperedge deletions.

Returns:

delete_hyperedges.size().

inline bool empty() const noexcept#

Whether the batch has no operation at all.

Returns:

True if it has no deletion, insertion or incidence edit.

Public Members

array_view<const std::int64_t> delete_hyperedges#

ids of hyperedges to delete

array_view<const std::int64_t> insert_offsets#

num_insertions() + 1 offsets from 0

array_view<const vertex_t> insert_members#

members of inserted hyperedge i are [insert_offsets[i], insert_offsets[i+1])

array_view<const weight_t> insert_weights#

one weight per inserted hyperedge

array_view<const std::int64_t> delete_incidence_hyperedge#

(h, v) removals: h (0.4)

array_view<const vertex_t> delete_incidence_vertex#

(h, v) removals: v (0.4)

array_view<const std::int64_t> insert_incidence_hyperedge#

(h, v) additions: h (0.4)

array_view<const vertex_t> insert_incidence_vertex#

(h, v) additions: v (0.4)

template<typename vertex_t, typename weight_t>
class hyperedge_batch#
#include <dyng/hypergraph/hyperedge_batch.hpp>

An owning host batch of hypergraph changes with a builder interface.

Operations of one kind keep the order in which they were added (the inserted ids are reported in insertion order).

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Weight type (unweighted: no weights).

Public Functions

hyperedge_batch() noexcept = default#

An empty batch.

inline void delete_hyperedge(std::int64_t id)#

Add the deletion of a hyperedge.

Exception safety:

Strong: after an exception the batch is unchanged.

Parameters:

id – [in] The hyperedge id (a dead or out-of-range id is skipped and counted by apply()).

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void insert_hyperedge(array_view<const vertex_t> members, weight_t w = {})#

Add the insertion of a hyperedge.

Exception safety:

Strong: after an exception the batch is unchanged.

Parameters:

  • members – [in] Its members (host memory; repeated members are dropped by apply()).

  • w – [in] Its weight (ignored for unweighted).

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void insert_hyperedge(std::initializer_list<vertex_t> members, weight_t w = {})#

Add the insertion of a hyperedge.

Exception safety:

Strong: after an exception the batch is unchanged.

Parameters:

  • members – [in] Its members (repeated members are dropped by apply()).

  • w – [in] Its weight (ignored for unweighted).

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void delete_incidence(std::int64_t h, vertex_t v)#

Add the removal of vertex v from the live hyperedge h (planned for 0.4: apply() raises not_supported_error for a batch that has one).

Exception safety:

Strong: after an exception the batch is unchanged.

Parameters:

  • h – [in] The hyperedge id.

  • v – [in] The vertex.

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void insert_incidence(std::int64_t h, vertex_t v)#

Add vertex v to the live hyperedge h (planned for 0.4: apply() raises not_supported_error for a batch that has one).

Exception safety:

Strong: after an exception the batch is unchanged.

Parameters:

  • h – [in] The hyperedge id.

  • v – [in] The vertex.

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void reserve(std::size_t insertions, std::size_t members, std::size_t deletions)#

Reserve capacity.

Exception safety:

Strong for the contents (the operations are unchanged; some arrays may keep a larger capacity).

Parameters:

  • insertions – [in] Expected number of inserted hyperedges.

  • members – [in] Expected number of their members in total.

  • deletions – [in] Expected number of deleted hyperedges.

Throws:

out_of_memory_error – if the capacity cannot be allocated.

inline void clear() noexcept#

Remove every operation (keeps the capacity).

Exception safety:

No-throw.

inline std::size_t num_insertions() const noexcept#

Number of hyperedge insertions.

Returns:

The insertion count.

inline std::size_t num_deletions() const noexcept#

Number of hyperedge deletions.

Returns:

The deletion count.

inline bool empty() const noexcept#

Whether the batch is empty.

Returns:

True if it has no operation.

inline const std::vector<std::int64_t> &delete_hyperedges() const noexcept#

The ids of the deletions.

Returns:

The array, in the order they were added.

inline const std::vector<std::int64_t> &insert_offsets() const noexcept#

The offsets of the inserted hyperedges’ members.

Returns:

num_insertions() + 1 offsets (empty without insertions).

inline const std::vector<vertex_t> &insert_members() const noexcept#

The members of the inserted hyperedges, back to back.

Returns:

The array.

inline const std::vector<weight_t> &insert_weights() const noexcept#

The weights of the inserted hyperedges.

Returns:

One per insertion (empty for unweighted).

inline const std::vector<std::int64_t> &delete_incidence_hyperedge() const noexcept#

The hyperedges of the incidence removals (planned for 0.4).

Returns:

One per removal, in the order they were added.

inline const std::vector<vertex_t> &delete_incidence_vertex() const noexcept#

The vertices of the incidence removals (planned for 0.4).

Returns:

One per removal, in the order they were added.

inline const std::vector<std::int64_t> &insert_incidence_hyperedge() const noexcept#

The hyperedges of the incidence additions (planned for 0.4).

Returns:

One per addition, in the order they were added.

inline const std::vector<vertex_t> &insert_incidence_vertex() const noexcept#

The vertices of the incidence additions (planned for 0.4).

Returns:

One per addition, in the order they were added.

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

A read-only view of the batch.

Returns:

A host hyperedge_batch_view; valid while this batch is alive and unmodified.

template<typename vertex_t, typename weight_t = unweighted>
struct hyperedge_list_view#
#include <dyng/hypergraph/hyperedge_list.hpp>

A non-owning list of hyperedges: the members of hyperedge i are members[offsets[i] .. offsets[i + 1]).

The input of hypergraph::from_hyperedges(); the arrays may live in any memory space. Hyperedge i becomes the hyperedge with id i.

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Weight type (unweighted: no weights).

Public Functions

inline std::int64_t num_hyperedges() const noexcept#

Number of hyperedges.

Returns:

offsets.size() - 1, or 0 for empty offsets.

Public Members

vertex_t num_vertices = 0#

vertex ids lie in [0, num_vertices)

array_view<const std::int64_t> offsets#

num_hyperedges() + 1 offsets from 0 (or empty)

array_view<const vertex_t> members#

the members of every hyperedge, back to back

array_view<const weight_t> weights#

one weight per hyperedge; empty for unweighted

template<typename vertex_t, typename weight_t = unweighted>
struct hyperedge_list#
#include <dyng/hypergraph/hyperedge_list.hpp>

An owning host list of hyperedges (a CSR of member lists), for building hypergraphs and for hypergraph::to_hyperedge_list().

A plain aggregate: the fields may be filled directly. hypergraph::from_hyperedges() validates it.

Template Parameters:

  • vertex_t – Vertex id type.

  • weight_t – Weight type (unweighted: weights stays empty).

Public Functions

inline std::int64_t num_hyperedges() const noexcept#

Number of hyperedges.

Returns:

offsets.size() - 1, or 0 for empty offsets.

inline void add_hyperedge(array_view<const vertex_t> hyperedge_members, weight_t w = {})#

Append one hyperedge.

Exception safety:

Strong: after an exception the list is unchanged.

Parameters:

  • hyperedge_members – [in] Its members (host memory).

  • w – [in] Its weight (ignored for unweighted).

Throws:

out_of_memory_error – if the arrays cannot grow.

inline void add_hyperedge(std::initializer_list<vertex_t> hyperedge_members, weight_t w = {})#

Append one hyperedge.

Exception safety:

Strong: after an exception the list is unchanged.

Parameters:

  • hyperedge_members – [in] Its members.

  • w – [in] Its weight (ignored for unweighted).

Throws:

out_of_memory_error – if the arrays cannot grow.

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

A read-only view of the arrays.

Returns:

A hyperedge_list_view in host memory; valid while this object is alive and unmodified.

Public Members

vertex_t num_vertices = 0#

vertex ids lie in [0, num_vertices)

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

num_hyperedges() + 1 offsets, offsets[0] == 0

std::vector<vertex_t> members#

the members of every hyperedge, back to back

std::vector<weight_t> weights#

one weight per hyperedge; empty for unweighted

template<typename vertex_t = std::int32_t, typename weight_t = unweighted>
class hypergraph#
#include <dyng/hypergraph/hypergraph.hpp>

A dynamic hypergraph: hyperedges (sets of vertices) identified by 0-based int64 ids, changed by batches of hyperedge deletions and insertions.

The hypergraph owns its storage (hypergraph_storage::escher: the ESCHER store, ESCHER IPDPS’26 with the best-fit reuse of ESCHER+, TKDE’26) and a version counter that increases by one with every applied batch, plus a process-wide unique state identity (renewed by every construction and every batch, copied by clone()), so a result computed on it is detected as stale when it is used with another hypergraph or state.

Ids. Hyperedge i of from_hyperedges() gets id i. A batch’s inserted hyperedges get the ids that the store’s best-fit reuse chooses (hyper_apply_summary::inserted_ids): deleted slots whose capacity fits are reused, the others are dropped and new hyperedges are numbered after the last live id. Ids must be read from inserted_ids, never predicted: the order of a batch (hypergraph_properties::reuse) changes them, and a dead id can be given out again. Live ids lie in [0, hyperedge_id_bound()); a dead id below the bound has an empty row.

Placement (PLAN Section 4.6 rule 5). The storage belongs to the backend of the resources that built it: the host backends (sequential, openmp) keep a host store, the cuda backend the device store (authoritative; host copies are made only when something reads them on the host: to_hyperedge_list(), check_integrity(), a clone for a host backend). Calls with resources of the other kind throw instead of copying the hypergraph; clone(res) and to_backend(res) make the copy.

Thread safety. As graph: read-only calls (the views, the accessors, to_hyperedge_list()) may run concurrently with each other; apply() must not overlap any other call on the same hypergraph.

Results. dyng::update(res, h, batch, results…) applies a batch once and brings every result of a hypergraph algorithm up to date (detail::participant_of<hypergraph>, below): one validation and normalization of the batch, every result’s work on the hypergraph before the batch, one commit, every result’s work after it.

Instantiated for (vertex_t, weight_t) = (int32, unweighted) and (int32, int32) on every backend.

Template Parameters:

  • vertex_t – Vertex id type (signed).

  • weight_t – Hyperedge weight type (unweighted, or std::int32_t in [1, 2^31 - 1]).

Public Types

using vertex_type = vertex_t#

vertex id type

using weight_type = weight_t#

hyperedge weight type

using h2v_view_type = incidence_view<vertex_t>#

the h2v view type

using v2h_view_type = incidence_view<std::int64_t>#

the v2h view type

using line_graph_type = line_graph_view<weight_t>#

the h2h view type

using batch_view_type = hyperedge_batch_view<vertex_t, weight_t>#

the batch view type

using list_type = hyperedge_list<vertex_t, weight_t>#

the owning list type

Public Functions

hypergraph(hypergraph &&other) noexcept#

Move constructor.

Parameters:

other – [inout] The hypergraph to move from; it may only be assigned to or destroyed.

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

Move assignment.

Parameters:

other – [inout] The hypergraph to move from; it may only be assigned to or destroyed.

Returns:

*this.

hypergraph(const hypergraph&) = delete#

not copyable: use clone()

hypergraph &operator=(const hypergraph&) = delete#

not copyable: use clone()

~hypergraph()#

releases the storage

hypergraph clone(const resources &res) const#

A deep copy for the resources res (same properties, ids, rows, version and state identity; the store’s deleted slots and payload accounting too, so later batches give the copy the same ids).

The copy belongs to the backend of res: this is how a hypergraph moves between the host backends and cuda.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources of the copy.

Throws:
Returns:

The copy.

hypergraph to_backend(const resources &res) const#

The hypergraph for the backend of res: the explicit move between the host backends and cuda that the placement errors name. The same as clone(res).

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

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

Throws:
Returns:

The hypergraph for res.

vertex_t num_vertices() const noexcept#

Number of vertices.

Returns:

n; vertex ids lie in [0, n).

std::int64_t num_hyperedges() const noexcept#

Number of live hyperedges.

Returns:

The live count.

std::int64_t hyperedge_id_bound() const noexcept#

The bound of the hyperedge ids: live ids lie in [0, bound); dead ids may exist below it.

The bound can go down: an insert that appends new rows drops the deleted slots it did not reuse and numbers the new rows after the last live id.

Returns:

The bound.

const hypergraph_properties &properties() const noexcept#

The properties of the hypergraph.

Returns:

The properties given at construction.

memory_space space() const noexcept#

The memory space of the storage and of the views.

Returns:

memory_space::device for a hypergraph built with CUDA resources, memory_space::host otherwise.

std::uint64_t version() const noexcept#

The version counter.

Returns:

0 after construction; +1 per applied batch.

h2v_view_type h2v() const#

Hyperedge to members: one sorted row per id in [0, hyperedge_id_bound()), empty for a dead id.

Built from the store on first use per version (in the hypergraph’s memory space) and kept until the next apply().

Synchronization:

Blocks until the work has completed (synchronous).

Throws:
Returns:

The view, invalidated by the next apply().

v2h_view_type v2h() const#

Vertex to hyperedges: one row per vertex, the ids of its live hyperedges in increasing order.

Built from the store on first use per version (at most once per version, never by apply()) and kept until the next apply().

Synchronization:

Blocks until the work has completed (synchronous).

Throws:
Returns:

The view, invalidated by the next apply().

line_graph_type h2h() const#

The line graph: every live hyperedge to the hyperedges it overlaps (one sorted row per id in [0, hyperedge_id_bound()), empty for a dead id; out the first neighbour above the row’s id).

Under line_graph_policy::sorted_merge the line graph is built with the hypergraph and kept by every apply() (ESCHER-GPU’s sorted delta merge); under automatic the first call builds it, and apply() keeps it from then on. The view itself (decoded: 0-based ids, int64 offsets, in the hypergraph’s memory space; the weights by id in host memory) is built from the line graph on first use per version and kept until the next apply().

Synchronization:

Blocks until the work has completed (synchronous).

Throws:
Returns:

The view, invalidated by the next apply().

array_view<const weight_t> weights() const#

The hyperedge weights by id (host memory on every backend): one per id in [0, hyperedge_id_bound()), 0 for a dead id; empty for an unweighted hypergraph.

Throws:

invalid_argument_error – for a moved-from or poisoned hypergraph.

Returns:

The view, invalidated by the next apply().

hyper_apply_summary apply(const resources &res, const batch_view_type &batch)#

Apply a batch: delete hyperedges by id and insert new ones, in the order of properties().reuse.

Deletions of dead, out-of-range or repeated ids are skipped and counted (hyper_apply_summary::ignored_deletions), as are repeated members of an inserted hyperedge (dropped_members). The inserted hyperedges get the ids the store’s best-fit reuse chooses, reported in hyper_apply_summary::inserted_ids.

On CUDA the storage works on the stream of the resources the hypergraph was built with; apply() orders that work after the work queued so far on the stream of res, and the work later queued on the stream of res after it, so either stream may hold readers of the views.

Synchronization:

Blocks until the work has completed (synchronous).

Exception safety:

Strong for every error found before the store changes (the invalid_argument_error and not_supported_error cases above, the batch-size capacity_error, an allocation failure while the batch is staged and checked): version, state identity and contents are unchanged. Basic otherwise: an error inside a store operation poisons the hypergraph; every later call that reads or changes its storage (the views, weights(), apply(), to_hyperedge_list(), clone(), to_backend(), check_integrity()) throws, and the noexcept accessors return unspecified values, until it is destroyed or assigned.

Parameters:

  • res – [in] Execution resources of the hypergraph’s backend (and device).

  • batch – [in] The batch (any memory space: it is validated and grouped on the host, so arrays in device memory are copied once under res.get_copy_policy()).

Throws:

  • invalid_argument_error – if a member is out of range, an inserted hyperedge is empty, the offsets are malformed, a weight is outside [1, 2^31 - 1] (or the weights do not match the insertions), the resources belong to another backend or device, the hypergraph was moved from or is poisoned, or an array must be copied and the copy policy is copy_policy::error.

  • not_supported_error – if the batch has incidence edits (planned for 0.4).

  • capacity_error – if the batch inserts more than INT_MAX / 3 (715,827,882) members in all (found before the store changes: nothing changed), or the storage exceeds its policy (the hypergraph is then poisoned).

  • out_of_memory_error – if host or device memory cannot be allocated: while the batch is staged and checked nothing changed, in a store operation the hypergraph is poisoned.

  • cuda_error – if the CUDA runtime reports an error (poisoned).

  • internal_error – if the store’s device error word reports a broken invariant (poisoned).

Returns:

What the batch did.

list_type to_hyperedge_list(const resources &res) const#

A host copy of the live hyperedges in increasing id order (ids are not kept: the list’s hyperedge i is the i-th live id).

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources (the hypergraph’s backend).

Throws:
Returns:

The list, with the weights of a weighted hypergraph.

storage_stats store_stats() const noexcept#

The storage counters (device bytes in ESCHER-GPU’s accounting scope, payload, growths, compactions, kernel paths).

Returns:

The counters of the last completed operation.

void check_integrity(const resources &res) const#

Check the storage invariants: the rows of every tree by search from the root, their reachability, segments and tail metadata (ESCHER’s row check), the deleted-slot counters (subtree_avail, MOSP_ESCHER’s store check) against the live ids, and that v2h is the transpose of h2v.

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

res – [in] Execution resources (the hypergraph’s backend).

Throws:

Public Static Functions

static hypergraph from_hyperedges(const resources &res, hyperedge_list_view<vertex_t, weight_t> hyperedges, const hypergraph_properties &props = {})#

Build a hypergraph from a list of hyperedges (hyperedge i gets id i).

Each hyperedge’s members are sorted and repeated members dropped. The list may be empty (no hyperedge; vertices may still exist).

Synchronization:

Blocks until the work has completed (synchronous).

Parameters:

  • res – [in] Execution resources (the hypergraph belongs to their backend).

  • hyperedges – [in] The hyperedges (any memory space: the list is read on the host, so arrays in device memory are copied once under res.get_copy_policy()).

  • props – [in] The properties of the new hypergraph.

Throws:

  • invalid_argument_error – if a member is out of [0, num_vertices), a hyperedge is empty, the offsets are malformed, a weight is outside [1, 2^31 - 1] (or weights are given for an unweighted list, or missing for a weighted one), line_graph_policy:: sorted_merge is asked for without v2h (store_v2h is false), or an array must be copied and the copy policy is copy_policy::error.

  • not_supported_error – for hypergraph_storage::slack_csr or line_graph_policy:: slack_csr (planned for 0.4), a grow_factor other than 1.5 or 0, or the cuda backend in a build without CUDA.

  • capacity_error – if the storage (the line graph of sorted_merge included) exceeds the policy’s max_payload (by default the int32 offsets of the store).

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

  • cuda_error – if the CUDA runtime reports an error.

Returns:

The hypergraph at version 0.

struct capacity_policy#
#include <dyng/hypergraph/hypergraph_properties.hpp>

How a hypergraph’s storage is sized and grows (the payload of each of its trees).

A tree updated in place starts with min(max(min_initial_payload

, size + floor(size *

initial_headroom) +

initial_slack), max_payload) payload entries, where size is the payload its rows need; capacity_error if that is below size. A payload that does not fit is first compacted (compact_before_grow, at MOSP_ESCHER’s trigger points), then grows to max(needed + needed / 4, floor(capacity * grow_factor)) entries, at most max_payload, or raises capacity_error when grow_factor is 0. The two presets reproduce the originals exactly; the default is dynG’s policy (compact first, then grow, with headroom after a compaction).

Public Members

double initial_headroom = 0.125#

slack of a new tree as a fraction of its size

std::int64_t initial_slack = 1024#

slack entries added to every new tree

std::int64_t min_initial_payload = 0#

lower bound of the initial payload (0: none)

double grow_factor = 1.5#

growth of a full payload (1.5), or 0: never grow

bool compact_before_grow = true#

compact a full payload before growing it

std::int64_t max_payload = 0#

largest payload per tree (0: 2^31 - 1, int32 offsets)

std::int32_t row_alignment = 4#

a surplus row inserted by a batch reserves its members rounded up to a multiple of this, plus one slot (construction pads to multiples of 4 always)

std::int32_t compaction_headroom = 8#

after a compaction, grow while fewer than capacity / compaction_headroom entries are free (0: never)

bool exact_scratch = false#

operation buffers sized exactly (ESCHER-GPU) or grown geometrically (MOSP_ESCHER)

Public Static Functions

static inline constexpr capacity_policy escher_gpu(std::int64_t min_initial_payload = 0) noexcept#

ESCHER-GPU@abcf9b2’s policy: trees start at size + size / 8 + 1024 entries (at least min_initial_payload), never compact, and grow by its rule up to 2^31 - 1.

Parameters:

min_initial_payload – [in] ESCHER-GPU’s --payload-capacity (a lower bound; 0: none).

Returns:

The preset.

static inline constexpr capacity_policy mosp_escher(std::int64_t extra = std::int64_t{1} << 20) noexcept#

MOSP_ESCHER@4b86159’s policy: trees start at floor(size * 1.3) + extra entries (at most 2.0e9), compact at its trigger points and never grow (capacity_error).

Parameters:

extra – [in] The extra entries of every tree (MOSP_ESCHER’s Caps::extraPayloadInts; its default 2^20).

Returns:

The preset.

struct hypergraph_properties#
#include <dyng/hypergraph/hypergraph_properties.hpp>

The properties of a hypergraph, fixed at construction.

Public Members

hypergraph_storage storage = hypergraph_storage::escher#

the incidence storage

line_graph_policy line_graph = line_graph_policy::automatic#

the line graph (h2h)

id_reuse reuse = id_reuse::erase_first#

the order of a batch (decides the reused ids)

capacity_policy capacity = {}#

sizing and growth of the storage

bool store_v2h = true#

keep vertex -> hyperedges (v2h(); triad_count)

template<typename id_t>
struct incidence_view#
#include <dyng/hypergraph/hypergraph_view.hpp>

A read-only CSR of one incidence relation of a hypergraph at one version: hyperedge to member vertices (h2v) or vertex to hyperedge ids (v2h).

Row r lists col_ind[row_ptr[r] .. row_ptr[r + 1]) in increasing order. Rows of h2v are indexed by hyperedge id in [0, hyperedge_id_bound()); a dead id has an empty row. Rows of v2h are indexed by vertex. The arrays live in the container’s memory space (device memory for a CUDA hypergraph) and are invalidated by the next hypergraph::apply() (compare version with hypergraph::version()).

Template Parameters:

id_t – The type of the listed ids (vertex_t for h2v, std::int64_t for v2h).

Public Functions

inline std::int64_t num_rows() const noexcept#

Number of rows.

Returns:

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

inline std::int64_t num_entries() const noexcept#

Number of entries (incidences).

Returns:

col_ind.size().

Public Members

array_view<const std::int64_t> row_ptr#

num_rows() + 1 offsets, row_ptr[0] == 0

array_view<const id_t> col_ind#

the ids of every row, rows back to back

std::uint64_t version = 0#

the hypergraph version this view describes

template<typename weight_t>
struct line_graph_view#
#include <dyng/hypergraph/hypergraph_view.hpp>

A read-only view of the line graph (h2h) of a hypergraph at one version: every live hyperedge to the other hyperedges it shares at least one vertex with.

Rows are indexed by hyperedge id, sorted and contiguous; a dead id has an empty row. out[r] is the offset of the first neighbour of row r with an id greater than r. row_ptr, col_ind, out and overlaps live in the container’s memory space; weights is host memory on every backend (each array_view carries its space). All are invalidated by the next hypergraph::apply().

Template Parameters:

weight_t – The hyperedge weight type (unweighted: no weights).

Public Functions

inline std::int64_t num_rows() const noexcept#

Number of rows.

Returns:

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

inline std::int64_t num_entries() const noexcept#

Number of entries (each adjacent pair counts in both rows).

Returns:

col_ind.size().

Public Members

array_view<const std::int64_t> row_ptr#

num_rows() + 1 offsets, row_ptr[0] == 0

array_view<const std::int64_t> col_ind#

the neighbour ids of every row, sorted

array_view<const std::int64_t> out#

per row: the first neighbour above the row’s id

array_view<const std::int32_t> overlaps#

shared vertices per entry; empty under escher

array_view<const weight_t> weights#

weights by id (host memory); empty if unweighted

std::uint64_t version = 0#

the hypergraph version this view describes

struct storage_path_counters#
#include <dyng/hypergraph/hypergraph_view.hpp>

Which kernel paths an operation family took: the degree-binned thread, warp and block paths (an operation counts once per path it used).

Public Members

std::int64_t thread = 0#

operations that used the thread-per-item path

std::int64_t warp = 0#

operations that used the warp-per-item path

std::int64_t block = 0#

operations that used the block-per-item path

struct storage_stats#
#include <dyng/hypergraph/hypergraph_view.hpp>

The storage counters of a hypergraph (hypergraph::store_stats()).

device_bytes is the scope of ESCHER-GPU’s DynamicHypergraph::deviceBytes(): the stores of the incidence relations and of the line graph with their operation buffers, and the row views the container keeps; the views built on request (h2v(), v2h()) are counted in view_bytes. The counters are those of the last completed operation (reading them does not synchronize).

Public Members

std::int64_t device_bytes = 0#

device memory of the stores and kept row views

std::int64_t view_bytes = 0#

memory of the views built on request

std::int64_t host_bytes = 0#

host memory of the storage (CPU backends)

std::int64_t payload_capacity = 0#

h2v payload entries allocated

std::int64_t payload_used = 0#

h2v payload entries in use (the bump pointer)

std::int64_t growths = 0#

payload growths (all trees)

std::int64_t compactions = 0#

payload compactions (all trees)

storage_path_counters fill#

appends of values to rows (v2h)

storage_path_counters reuse#

inserted rows that reused a deleted slot (h2v)

storage_path_counters unfill#

removals of values from rows (v2h)

On this page
Edit on GitHub