Crate oxgraph_hyper_bcsr

Expand description

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.

Structs§

BcsrElementIncidences: Iterator yielding incidence IDs for one vertex’s incidences.
BcsrHypergraph: Borrowed bipartite compressed-sparse-row hypergraph view.
BcsrParticipantSlice: Iterator yielding incidence IDs for a contiguous incidence range.
BcsrSections: Borrowed input slices for a bipartite-CSR hypergraph view.

Enums§

BcsrError: Bipartite-CSR validation error.
BcsrRole: Side of a directed hyperedge an incidence belongs to.
BcsrRoleSide: Side of the bipartite index that produced a cross-direction mismatch.
BcsrSection: Names a single bipartite-CSR section for error reporting.
BcsrSnapshotError: Error returned when a snapshot cannot be opened as a bipartite-CSR hypergraph view.
BcsrValidation: Validation depth applied at view open time.

Constants§

SNAPSHOT_BCSR_SECTION_VERSION: Section version written and expected for all BCSR layout payloads.
SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U16: Hyperedge-major head offsets, u16 little-endian.
SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U32: Hyperedge-major head offsets, u32 little-endian.
SNAPSHOT_KIND_BCSR_HEAD_OFFSETS_U64: Hyperedge-major head offsets, u64 little-endian.
SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U16: Hyperedge-major head participants, u16 little-endian.
SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U32: Hyperedge-major head participants, u32 little-endian.
SNAPSHOT_KIND_BCSR_HEAD_PARTICIPANTS_U64: Hyperedge-major head participants, u64 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U16: Hyperedge-major tail offsets, u16 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U32: Hyperedge-major tail offsets, u32 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_OFFSETS_U64: Hyperedge-major tail offsets, u64 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U16: Hyperedge-major tail participants, u16 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U32: Hyperedge-major tail participants, u32 little-endian.
SNAPSHOT_KIND_BCSR_TAIL_PARTICIPANTS_U64: Hyperedge-major tail participants, u64 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U16: Vertex-major incoming hyperedge IDs, u16 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U32: Vertex-major incoming hyperedge IDs, u32 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_HYPEREDGES_U64: Vertex-major incoming hyperedge IDs, u64 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U16: Vertex-major incoming offsets, u16 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U32: Vertex-major incoming offsets, u32 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_INCOMING_OFFSETS_U64: Vertex-major incoming offsets, u64 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U16: Vertex-major outgoing hyperedge IDs, u16 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U32: Vertex-major outgoing hyperedge IDs, u32 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_HYPEREDGES_U64: Vertex-major outgoing hyperedge IDs, u64 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U16: Vertex-major outgoing offsets, u16 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U32: Vertex-major outgoing offsets, u32 little-endian.
SNAPSHOT_KIND_BCSR_VERTEX_OUTGOING_OFFSETS_U64: Vertex-major outgoing offsets, u64 little-endian.

Traits§

BcsrSnapshotIndex: Width-specific section-kind tags for persisted BCSR layout payloads.
LayoutIndex: Unsigned dense ID width usable by graph and hypergraph layouts and builders.
LayoutSnapshotWord: A little-endian storage word usable in persisted snapshot payloads.
LayoutWord: A native-host or little-endian word carrying a typed dense LayoutIndex.

Type Aliases§

BcsrChainedHyperedges: Chained hyperedge iterator yielding outgoing then incoming hyperedges.
BcsrChainedParticipants: Chained vertex iterator yielding head participants then tail participants.
BcsrChainedRelationIncidences: Chained participant-ID iterator yielding head incidences then tail incidences for a single hyperedge.
BcsrHyperedgeId: Local hyperedge ID for BcsrHypergraph.
BcsrHyperedgeSlice: Iterator over a borrowed slice of hyperedge words.
BcsrNativeHypergraph: Native borrowed BCSR hypergraph alias.
BcsrParticipantId: Local participant (incidence) ID for BcsrHypergraph.
BcsrPredecessorVertices: Iterator over predecessor vertices of a directed-hypergraph vertex.
BcsrSnapshotHypergraph: Snapshot-backed BCSR hypergraph alias.
BcsrSuccessorVertices: Iterator over successor vertices of a directed-hypergraph vertex.
BcsrVertexId: Local vertex ID for BcsrHypergraph.
BcsrVertexSlice: Iterator over a borrowed slice of vertex words.