oxgraph-hyper-bcsr 0.1.0

Borrowed bipartite CSR hypergraph views implementing oxgraph-hyper traits.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

//! Borrowed bipartite compressed-sparse-row hypergraph views.
//!
//! `oxgraph-hyper-bcsr` provides the first concrete hypergraph layout for the
//! substrate. A [`BcsrHypergraph`] borrows eight validated CSR slices — one
//! offset/value pair per direction per role — and implements the
//! storage-agnostic hypergraph traits from `oxgraph-hyper`.
//!
//! Bipartite CSR keeps both directions dense: head and tail participants are
//! stored under a hyperedge-major index, while outgoing and incoming
//! incidences are stored under a vertex-major index. This trades roughly four
//! times the participant storage for `O(degree)` traversal in either
//! direction, which is the only access pattern that scales for read-heavy
//! workloads.
//!
//! # Layout summary
//!
//! Eight sections compose the snapshot bytes consumed by [`BcsrHypergraph`]:
//!
//! | Section kind                            | Logical content                                                            |
//! | --------------------------------------- | -------------------------------------------------------------------------- |
//! Snapshot section kinds are width-specific. Vertex participant sections use
//! the selected vertex width, relation sections use the selected relation
//! width, and all offset sections use the selected incidence width.
//!
//! # Validation
//!
//! Section payloads are validated at open time. [`BcsrValidation::Layout`]
//! covers length, offset monotonicity, in-range IDs, and per-range
//! sorted-and-unique vertex / hyperedge sequences. [`BcsrValidation::Strict`]
//! additionally checks cross-CSR consistency — that hyperedge-major and
//! vertex-major arrays describe the same incidence set. `Layout` is the
//! default for trusted producers; `Strict` is required for end-to-end
//! semantic guarantees on untrusted inputs.
//!
//! # Optional builder
//!
//! The `build` feature enables the append-only [`build::HypergraphBuilder`]
//! and [`build::WeightedHypergraphBuilder`] types plus snapshot export
//! helpers in the [`build`] submodule. The additional `build-property-arrow`
//! feature enables property-snapshot export via `oxgraph-property`.
#![no_std]

#[cfg(feature = "build")]
extern crate alloc;

#[cfg(kani)]
extern crate kani;

#[cfg(feature = "build")]
pub mod build;
mod error;
mod id;
mod internal;
mod snapshot;
mod word;

#[cfg(kani)]
mod proofs;

pub use crate::{
    error::{BcsrError, BcsrRoleSide, BcsrSection, BcsrSnapshotError},
    id::{BcsrHyperedgeId, BcsrParticipantId, BcsrRole, BcsrVertexId},
    internal::{
        BcsrChainedHyperedges, BcsrChainedParticipants, BcsrChainedRelationIncidences,
        BcsrElementIncidences, BcsrHyperedgeSlice, BcsrHypergraph, BcsrParticipantSlice,
        BcsrPredecessorVertices, BcsrSections, BcsrSuccessorVertices, BcsrValidation,
        BcsrVertexSlice,
    },
    snapshot::{
        SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U16, SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U32,
        SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U64, SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U16,
        SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U32, SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U64,
        SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U16, SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U32,
        SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U64, SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U16,
        SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U32, SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U64,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U16,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U32,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U64,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U16,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U32,
        SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U64,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U16,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U32,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U64,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U16,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U32,
        SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U64,
    },
    word::{BcsrIndex, BcsrSnapshotIndex, BcsrSnapshotWord, BcsrWord},
};

/// Native borrowed BCSR hypergraph alias.
///
/// # Performance
///
/// `perf: unspecified`; this alias carries no runtime cost.
pub type BcsrNativeHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> = BcsrHypergraph<
    'view,
    VertexIndex,
    RelationIndex,
    IncidenceIndex,
    IncidenceIndex,
    VertexIndex,
    RelationIndex,
>;

/// Snapshot-backed BCSR hypergraph alias.
///
/// # Performance
///
/// `perf: unspecified`; this alias carries no runtime cost.
pub type BcsrSnapshotHypergraph<'view, VertexIndex, RelationIndex, IncidenceIndex> = BcsrHypergraph<
    'view,
    VertexIndex,
    RelationIndex,
    IncidenceIndex,
    <IncidenceIndex as BcsrSnapshotIndex>::LittleEndianWord,
    <VertexIndex as BcsrSnapshotIndex>::LittleEndianWord,
    <RelationIndex as BcsrSnapshotIndex>::LittleEndianWord,
>;