oxgraph_hyper_bcsr/
lib.rs

1//! Borrowed bipartite compressed-sparse-row hypergraph views.
2//!
3//! `oxgraph-hyper-bcsr` provides the first concrete hypergraph layout for the
4//! substrate. A [`BcsrHypergraph`] borrows eight validated CSR slices — one
5//! offset/value pair per direction per role — and implements the
6//! storage-agnostic hypergraph traits from `oxgraph-hyper`.
7//!
8//! Bipartite CSR keeps both directions dense: head and tail participants are
9//! stored under a hyperedge-major index, while outgoing and incoming
10//! incidences are stored under a vertex-major index. This trades roughly four
11//! times the participant storage for `O(degree)` traversal in either
12//! direction, which is the only access pattern that scales for read-heavy
13//! workloads.
14//!
15//! # Layout summary
16//!
17//! Eight sections compose the snapshot bytes consumed by [`BcsrHypergraph`]:
18//!
19//! | Section kind                            | Logical content                                                            |
20//! | --------------------------------------- | -------------------------------------------------------------------------- |
21//! Snapshot section kinds are width-specific. Vertex participant sections use
22//! the selected vertex width, relation sections use the selected relation
23//! width, and all offset sections use the selected incidence width.
24//!
25//! # Validation
26//!
27//! Section payloads are validated at open time. [`BcsrValidation::Layout`]
28//! covers length, offset monotonicity, in-range IDs, and per-range
29//! sorted-and-unique vertex / hyperedge sequences. [`BcsrValidation::Strict`]
30//! additionally checks cross-CSR consistency — that hyperedge-major and
31//! vertex-major arrays describe the same incidence set. `Layout` is the
32//! default for trusted producers; `Strict` is required for end-to-end
33//! semantic guarantees on untrusted inputs.
34//!
35//! # Optional builder
36//!
37//! The `build` feature enables the append-only [`build::HypergraphBuilder`]
38//! and [`build::WeightedHypergraphBuilder`] types plus snapshot export
39//! helpers in the [`build`] submodule. The additional `build-property-arrow`
40//! feature enables property-snapshot export via `oxgraph-property`.
41#![no_std]
42
43#[cfg(feature = "build")]
44extern crate alloc;
45
46#[cfg(kani)]
47extern crate kani;
48
49#[cfg(feature = "build")]
50pub mod build;
51mod error;
52mod id;
53mod internal;
54mod snapshot;
55mod word;
56
57#[cfg(kani)]
58mod proofs;
59
60pub use crate::{
61    error::{BcsrError, BcsrRoleSide, BcsrSection, BcsrSnapshotError},
62    id::{BcsrHyperedgeId, BcsrParticipantId, BcsrRole, BcsrVertexId},
63    internal::{
64        BcsrChainedHyperedges, BcsrChainedParticipants, BcsrChainedRelationIncidences,
65        BcsrElementIncidences, BcsrHyperedgeSlice, BcsrHypergraph, BcsrParticipantSlice,
66        BcsrPredecessorVertices, BcsrSections, BcsrSuccessorVertices, BcsrValidation,
67        BcsrVertexSlice,
68    },
69    snapshot::{
70        SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_BASE, SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_BASE,
71        SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_BASE, SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_BASE,
72        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_BASE,
73        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_BASE,
74        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_BASE,
75        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_BASE,
76    },
77    word::{
78        BcsrSnapshotIndex, BcsrWords, LayoutIndex, LayoutSnapshotWord, LayoutWord, LeWords,
79        NativeWords, SNAPSHOT_BCSR_SECTION_VERSION,
80    },
81};
82
83/// Native borrowed BCSR hypergraph alias.
84///
85/// # Performance
86///
87/// `perf: unspecified`; this alias carries no runtime cost.
88pub type BcsrNativeHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> =
89    BcsrHypergraph<'view, NativeWords<VertexIndex, RelationIndex, IncidenceIndex>>;
90
91/// Snapshot-backed BCSR hypergraph alias.
92///
93/// # Performance
94///
95/// `perf: unspecified`; this alias carries no runtime cost.
96pub type BcsrSnapshotHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> =
97    BcsrHypergraph<'view, LeWords<VertexIndex, RelationIndex, IncidenceIndex>>;
oxgraph_hyper_bcsr/lib.rs

oxgraph_hyper_bcsr/
lib.rs
