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_U16, SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U32,
71        SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U64, SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U16,
72        SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U32, SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U64,
73        SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U16, SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U32,
74        SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U64, SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U16,
75        SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U32, SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U64,
76        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U16,
77        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U32,
78        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U64,
79        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U16,
80        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U32,
81        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U64,
82        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U16,
83        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U32,
84        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U64,
85        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U16,
86        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U32,
87        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U64,
88    },
89    word::{
90        BcsrSnapshotIndex, LayoutIndex, LayoutSnapshotWord, LayoutWord,
91        SNAPSHOT_BCSR_SECTION_VERSION,
92    },
93};
94
95/// Native borrowed BCSR hypergraph alias.
96///
97/// # Performance
98///
99/// `perf: unspecified`; this alias carries no runtime cost.
100pub type BcsrNativeHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> = BcsrHypergraph<
101    'view,
102    VertexIndex,
103    RelationIndex,
104    IncidenceIndex,
105    IncidenceIndex,
106    VertexIndex,
107    RelationIndex,
108>;
109
110/// Snapshot-backed BCSR hypergraph alias.
111///
112/// # Performance
113///
114/// `perf: unspecified`; this alias carries no runtime cost.
115pub type BcsrSnapshotHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> = BcsrHypergraph<
116    'view,
117    VertexIndex,
118    RelationIndex,
119    IncidenceIndex,
120    <IncidenceIndex as oxgraph_layout_util::SnapshotWidth>::LittleEndianWord,
121    <VertexIndex as oxgraph_layout_util::SnapshotWidth>::LittleEndianWord,
122    <RelationIndex as oxgraph_layout_util::SnapshotWidth>::LittleEndianWord,
123>;
oxgraph_hyper_bcsr/lib.rs

oxgraph_hyper_bcsr/
lib.rs
