Struct CsrIndex 

pub struct CsrIndex { /* private fields */ }

Dense integer CSR adjacency index with interned node IDs and labels.

Implementations

impl CsrIndex

pub fn compact(&mut self) -> Result<(), GraphError>

Merge the mutable buffer into the dense CSR arrays.

Called during idle periods. Rebuilds the contiguous offset/target/label (and weight) arrays from scratch (buffer + surviving dense edges). The old arrays are dropped, freeing memory. O(E) where E = total edges.

Errors

Returns GraphError::MemoryBudget if a memory governor is installed and the dense-array allocation would exceed the Graph engine budget.

impl CsrIndex

pub fn collection_id(&self, collection: &str) -> Option<u32>

Look up the dense collection id for a collection name, if interned.

Returns None when no edge in this partition was inserted under collection — the collection-scoped read paths (MATCH IN '<c>', RAG) treat that as “no edges in this collection” (empty result).

pub fn collection_name(&self, collection_id: u32) -> Option<&str>

Collection name for a dense collection id.

pub fn set_node_surrogate(&mut self, node: &str, surrogate: Surrogate)

Set the surrogate for a node, identified by its user-visible name.

Call once per node after add_edge / add_edge_weighted has allocated a CSR-local id for it. If the node is not yet interned this is a no-op (the edge insertion that follows will intern it and a subsequent call with the correct surrogate will set it). Calling with Surrogate::ZERO is a no-op — the zero sentinel is the initial state and has no meaning.

pub fn node_surrogate(&self, node: &str) -> Option<Surrogate>

Forward lookup: the Surrogate bound to a node by name, or None if the node is unknown to this partition or has no surrogate set (ZERO sentinel).

A graph node and its same-pk document share one global surrogate, so this is the bridge from a MATCH binding’s node name to the document storage key (StorageKey::for_surrogate) used to fetch the node’s properties.

pub fn node_surrogate_raw(&self, local_id: u32) -> u32

Return the raw surrogate u32 for a CSR-local node id.

Returns 0 (the ZERO sentinel) when the node has no surrogate set.

pub fn local_id_for_node(&self, node: &str) -> Option<u32>

Resolve a node name to its CSR-local id.

The name table is rebuilt from durable storage on every open, so this resolution always works; the surrogate table is not, which is why a name-seeded read must not be routed through Self::local_id_for_surrogate.

pub fn local_id_for_surrogate(&self, surrogate: Surrogate) -> Option<u32>

Resolve a Surrogate to its CSR-local node id without touching the node-name table.

This is the entry point for reads that stay in the surrogate domain: seeding a traversal through Self::node_id_for_surrogate would materialize a name only to hash it straight back to this same id. Returns None for Surrogate::ZERO and for surrogates never bound in this partition.

pub fn node_id_for_surrogate(&self, surrogate: Surrogate) -> Option<&str>

Look up the user-visible node name bound to a Surrogate.

Returns None for Surrogate::ZERO and for surrogates that have never been bound to a node in this partition. Used by cross-engine fusion (graph RAG) to translate a vector-side surrogate into a graph BFS seed name.

pub fn add_node_label( &mut self, node: &str, label: &str, ) -> Result<bool, GraphError>

Add a label to a node.

Returns Ok(false) if the 64 distinct node-label limit is hit (the label is silently ignored). Returns Err(GraphError::NodeOverflow) if the node is new and the partition’s node-id space is exhausted.

pub fn remove_node_label(&mut self, node: &str, label: &str)

Remove a label from a node.

pub fn node_has_label(&self, node_id: u32, label: &str) -> bool

Check if a node has a specific label.

pub fn labeled_nodes(&self) -> Vec<(&str, Vec<&str>)>

Every node carrying at least one label, as (node_name, label_names).

Node NAMES, not local ids: the local id of a node is assigned by whatever order the CSR was built in (the EdgeStore scan on a rebuild, or ensure_node vivification order on a replay), so it is not stable across restarts. Any consumer that persists this state and installs it back through add_node_label therefore reattaches each label to the node it actually belonged to, instead of to whichever node happens to hold that id in the next process.

Unlabeled nodes are skipped — their bitset is zero and carries no information.

pub fn node_labels(&self, node_id: u32) -> Vec<&str>

Get all label names for a node.

impl CsrIndex

pub fn label_filter(&self, labels: &[&str]) -> LabelFilter

Resolve labels against this partition’s interned labels.

impl CsrIndex

pub fn partition_tag(&self) -> u32

Partition tag assigned at construction. Embedded in every LocalNodeId this index produces.

pub fn local(&self, id: u32) -> LocalNodeId

Mint a LocalNodeId for this partition from a raw dense index. Used by algorithm code that iterates 0..node_count and needs to call LocalNodeId-taking APIs.

pub fn neighbors( &self, node: &str, label_filter: &[&str], direction: Direction, ) -> Vec<(String, String)>

Get immediate neighbors by string name. An empty label_filter keeps every edge. Otherwise an edge whose label is any listed label passes.

pub fn add_node(&mut self, name: &str) -> Result<LocalNodeId, GraphError>

Add a node without any edges. Idempotent — returns the existing tagged id if the name is already present.

Returns Err(GraphError::NodeOverflow) when the partition’s node-id space is exhausted (more than MAX_NODES_PER_CSR distinct nodes).

pub fn node_count(&self) -> usize

pub fn contains_node(&self, node: &str) -> bool

pub fn node_name(&self, id: LocalNodeId) -> &str

Get the string name for a tagged node id.

pub fn node_id(&self, name: &str) -> Option<LocalNodeId>

Look up the tagged node id for a string name.

pub fn label_name(&self, label_id: u32) -> &str

Get the string label for a dense label index.

pub fn label_id(&self, name: &str) -> Option<u32>

Look up the dense label id for a string label.

pub fn out_degree(&self, id: LocalNodeId) -> usize

Out-degree of a node (including buffer, excluding deleted).

pub fn in_degree(&self, id: LocalNodeId) -> usize

In-degree of a node.

pub fn edge_count(&self) -> usize

Total edge count (dense + buffer - deleted). O(V).

pub fn iter_out_edges( &self, node: LocalNodeId, ) -> impl Iterator<Item = (u32, LocalNodeId)>

Iterate all outbound edges for a tagged node. Yields (label_id, dst) with dst tagged to this partition.

pub fn iter_in_edges( &self, node: LocalNodeId, ) -> impl Iterator<Item = (u32, LocalNodeId)>

Iterate all inbound edges for a tagged node.

pub fn iter_out_edges_raw(&self, node: u32) -> impl Iterator<Item = (u32, u32)>

Raw dense out-edges iteration. In-partition algorithm use only.

pub fn iter_in_edges_raw(&self, node: u32) -> impl Iterator<Item = (u32, u32)>

Raw dense in-edges iteration. In-partition algorithm use only.

pub fn out_degree_raw(&self, node: u32) -> usize

Raw out-degree by dense index.

pub fn in_degree_raw(&self, node: u32) -> usize

Raw in-degree by dense index.

pub fn node_name_raw(&self, id: u32) -> &str

String name for a raw dense index. In-partition algorithm use only.

pub fn is_local_node(&self, id: u32) -> bool

Whether a raw dense index names a node of this partition.

Read paths that accept caller-supplied local ids gate on this: an id past the end is not a node, and admitting it would put an entry in a result set that resolves to no name at all.

pub fn node_name_checked(&self, id: u32) -> Option<&str>

String name for a raw dense index, or None when the index is out of range. Same domain as Self::node_name_raw, without the panic: read paths that resolve a whole traversal frontier use this so one torn id narrows the answer instead of killing the core.

pub fn node_id_raw(&self, name: &str) -> Option<u32>

Raw dense index lookup by name. In-partition algorithm use only.

impl CsrIndex

pub fn add_edge( &mut self, src: &str, label: &str, dst: &str, ) -> Result<(), GraphError>

Incrementally add an unweighted edge (goes into mutable buffer). Uses weight 1.0 if the graph already has weighted edges.

Returns Err(GraphError::LabelOverflow) if the label id space is exhausted. Production callers should always surface this to the client; silently ignoring it reproduces the silent-wrap bug the u32 widening was meant to fix.

pub fn add_edge_in_collection( &mut self, src: &str, label: &str, dst: &str, collection: &str, ) -> Result<(), GraphError>

Add an unweighted edge scoped to collection.

The collection tag is what lets a collection-scoped MATCH / RAG read (... IN '<collection>') see only its own edges even though every collection’s edges share one per-(database, tenant) CSR partition (nodes, node-labels and surrogates are shared across collections; only edges carry the collection axis).

pub fn add_edge_weighted_in_collection( &mut self, src: &str, label: &str, dst: &str, collection: &str, weight: f64, ) -> Result<(), GraphError>

Add a weighted edge scoped to collection. See Self::add_edge_in_collection and Self::add_edge_weighted.

pub fn add_edge_weighted( &mut self, src: &str, label: &str, dst: &str, weight: f64, ) -> Result<(), GraphError>

Incrementally add a weighted edge (goes into mutable buffer).

If this is the first weighted edge (weight != 1.0), initializes the weight tracking infrastructure (backfills existing buffer entries with 1.0).

pub fn remove_edge(&mut self, src: &str, label: &str, dst: &str)

Incrementally remove an edge under the unscoped ("") collection.

Kept for callers that operate on a single-collection CSR (NodeDB-Lite keys one CsrIndex per collection) or add edges via the collection-less Self::add_edge. Origin’s collection-scoped delete path uses Self::remove_edge_in_collection.

pub fn remove_edge_in_collection( &mut self, src: &str, label: &str, dst: &str, collection: &str, )

Incrementally remove the (src, label, dst, collection) edge.

Only the copy tagged with collection is removed — an identical triple under a different collection is left intact.

pub fn remove_node_edges(&mut self, node: &str) -> usize

Remove ALL edges touching a node. Returns the number of edges removed.

pub fn remove_nodes_with_prefix(&mut self, prefix: &str)

Remove all edges touching any node whose ID starts with prefix.

Used for tenant purge: prefix = "{tenant_id}:" removes all edges belonging to that tenant.

impl CsrIndex

pub fn edge_weight_in_collection( &self, src: &str, label: &str, dst: &str, collection: &str, ) -> Option<f64>

Weight of the live (src, label, dst) edge in collection, None when that edge is not live.

pub fn put_edge_in_collection( &mut self, src: &str, label: &str, dst: &str, collection: &str, weight: f64, ) -> Result<Option<f64>, GraphError>

Make the (src, label, dst) edge in collection live with weight.

A live edge with another weight takes the new one. Returns the weight the edge had while live before, None when it was not live, so a rollback can put it back.

pub fn restore_edge_in_collection( &mut self, src: &str, label: &str, dst: &str, collection: &str, prior: Option<f64>, ) -> Result<(), GraphError>

Put the edge back to prior: live with that weight, or absent when prior is None.

pub fn restore_node_surrogate(&mut self, node: &str, prior: u32)

Put node’s surrogate back to prior, 0 for none.

pub fn has_node_label_name(&self, label: &str) -> bool

Whether the node label label is interned.

pub fn withdraw_newest_node(&mut self, node: &str) -> Result<(), GraphError>

Withdraw node, which a rolled-back write interned.

An absent node is a no-op. The node must be the newest one, with no edge and no label: withdrawing any other would renumber or orphan live state, so that is refused.

pub fn withdraw_newest_node_label( &mut self, label: &str, ) -> Result<(), GraphError>

Withdraw the node label label, which a rolled-back write interned.

An absent label is a no-op. The label must be the newest one and no node may carry it, or the withdraw is refused.

impl CsrIndex

pub fn neighbors_in_collection( &self, node: &str, label_filter: &[&str], direction: Direction, collection: &str, ) -> Vec<(String, String)>

Collection-scoped neighbor lookup by string name.

Like Self::neighbors, with the same label_filter set semantics, but only traverses edges tagged with collection. A collection with no edges in this partition yields an empty result (never falls back to the merged, cross-collection view). Used by collection-scoped GraphRAG BFS so expansion never crosses a collection boundary.

pub fn iter_out_edges_raw_in( &self, node: u32, collection_id: u32, ) -> impl Iterator<Item = (u32, u32)>

Collection-scoped raw outbound iteration: yields (label_id, dst) for edges inserted under collection_id only (dense + buffer, minus deleted). Used by the MATCH / RAG collection-scoped read paths so a ... IN '<collection>' query never traverses another collection’s edges even though all collections share one CSR partition.

pub fn iter_in_edges_raw_in( &self, node: u32, collection_id: u32, ) -> impl Iterator<Item = (u32, u32)>

Collection-scoped raw inbound iteration (see iter_out_edges_raw_in).

impl CsrIndex

pub fn new(memory: ScopedMemory) -> CsrIndex

Create a new CsrIndex wired to memory.

Subsequent calls to compact(), checkpoint_to_bytes(), and compute_statistics() reserve bytes against the bound database, tenant, and EngineId::Graph before allocating and return Err(GraphError::MemoryBudget(_)) if the budget is exhausted.

pub fn has_weighted_edges(&self) -> bool

Whether any edge in this index has a non-default (1.0) weight.

impl CsrIndex

pub fn record_access(&self, node_id: u32)

Record a node access (called during traversals for hot/cold tracking).

pub fn cold_nodes(&self, threshold: u32) -> Vec<u32>

Get nodes with access count below threshold (cold nodes).

pub fn hot_node_count(&self) -> usize

Number of hot nodes (access count > 0).

pub fn query_epoch(&self) -> u64

Current query epoch (incremented per traversal call).

pub fn reset_access_counts(&mut self)

Reset access counters (called during compaction or periodically).

pub fn prefetch_node(&self, node_id: u32)

Predictive prefetch: hint the OS to load a node’s adjacency data into the page cache before the traversal touches it.

For in-memory dense CSR, this prefetches the cache line containing the node’s offset/target entries. For future mmap’d cold segments, this would call madvise(MADV_WILLNEED) on the relevant pages.

Called during BFS planning: when adding nodes to the next frontier, prefetch their neighbors’ data so it’s resident when the BFS loop reaches them on the next iteration.

pub fn prefetch_batch(&self, node_ids: &[u32])

Prefetch a batch of nodes (called during BFS frontier expansion).

pub fn evaluate_memory_pressure( &self, utilization: u8, spill_threshold: u8, restore_threshold: u8, ) -> (usize, usize)

Evaluate graph memory pressure and return promotion/demotion hints.

Uses SpillController-compatible thresholds (90%/75% hysteresis):

• Above spill threshold: demote cold nodes (spill to potential mmap)
• Below restore threshold: promote warm nodes back to hot RAM

utilization = estimated memory usage as percentage (0-100). Returns (nodes_to_demote, nodes_to_promote) counts.

pub fn estimated_memory_bytes(&self) -> usize

Estimated memory usage of the dense CSR in bytes.

Used for SpillController utilization calculation.

impl CsrIndex

pub fn checkpoint_to_bytes(&self) -> Result<Vec<u8>, GraphError>

Serialize the index to rkyv bytes (with magic header) for storage.

Errors

Returns GraphError::MemoryBudget if a memory governor is installed and the serialization buffer would exceed the Graph engine budget.

pub fn from_checkpoint( bytes: &[u8], memory: ScopedMemory, ) -> Result<Option<CsrIndex>, CsrCheckpointError>

Restore an index from a checkpoint snapshot.

Returns:

• Ok(Some(index)) — successfully decoded.
• Ok(None) — buffer does not start with the magic header (no legacy format exists for CSR; callers should treat this as an invalid buffer).
• Err(CsrCheckpointError::UnsupportedVersion) — magic matches but the version byte is not CSR_FORMAT_VERSION.

impl CsrIndex

pub fn finish_rebuild( &mut self, rebuilt: CsrRebuilt, memory: ScopedMemory, ) -> Result<CsrIndex, GraphError>

Close the journal of rebuilt and return the copy that replaces this index.

The copy holds the snapshot, compacted, plus every mutation this index took since begin_rebuild, in order. It keeps this index’s partition tag, so node ids handed out before the swap stay valid. The caller installs it in one step. On error the journal is closed, this index stays as it is, and the copy is dropped:

• GraphError::RebuildSuperseded: no journal of this rebuild is open.
• GraphError::RebuildJournalOverflow: the journal hit its bound.
• GraphError::RebuildReplayDiverged: a replayed mutation returned another outcome than it did here.
• GraphError::RebuildSnapshotInvalid: the copy does not decode.

impl CsrIndex

pub fn begin_rebuild( &mut self, max_journal_bytes: usize, ) -> Result<CsrRebuildSeed, GraphError>

Snapshot this index and open its write journal.

Every later mutation records itself until finish_rebuild or abort_rebuild closes the journal. max_journal_bytes bounds the journal. Returns GraphError::RebuildInProgress when a journal is already open.

pub fn rebuild_in_progress(&self) -> bool

Whether a rebuild journal is open on this index.

pub fn abort_rebuild(&mut self, token: u64)

Close the journal of rebuild token. The index itself is unchanged. A journal of another rebuild stays open.

impl CsrIndex

pub fn node_to_id_map(&self) -> &HashMap<String, u32>

Node-to-ID mapping (for snapshot cloning).

pub fn id_to_node_list(&self) -> &[String]

ID-to-node list (for snapshot cloning).

pub fn label_to_id_map(&self) -> &HashMap<String, u32>

Label-to-ID mapping (for snapshot cloning).

pub fn id_to_label_list(&self) -> &[String]

ID-to-label list (for snapshot cloning).

pub fn out_offsets_slice(&self) -> &[u32]

Outbound offset array slice.

pub fn out_targets_slice(&self) -> &[u32]

Outbound target array slice.

pub fn out_labels_slice(&self) -> &[u32]

Outbound label array slice.

pub fn out_weights_slice(&self) -> Option<&[f64]>

Outbound weight array slice (None if unweighted).

pub fn in_offsets_slice(&self) -> &[u32]

Inbound offset array slice.

pub fn in_targets_slice(&self) -> &[u32]

Inbound target array slice.

pub fn in_labels_slice(&self) -> &[u32]

Inbound label array slice.

pub fn in_weights_slice(&self) -> Option<&[f64]>

Inbound weight array slice (None if unweighted).

impl CsrIndex

pub fn compute_statistics(&self) -> Result<GraphStatistics, GraphError>

Compute full graph statistics from the current CSR state.

O(V + E) — iterates all nodes and edges once. Intended for query planning, not hot-path execution.

Errors

Returns GraphError::MemoryBudget if a memory governor is installed and the degree-array working set would exceed the Graph engine budget.

pub fn label_edge_count(&self, label: &str) -> usize

Get the edge count for a specific label. O(E) unless cached.

Returns 0 if the label doesn’t exist.

pub fn label_selectivity(&self, label: &str) -> f64

Estimate the selectivity of a label: edge_count / total_edges.

Returns 1.0 for unknown labels (conservative — assume all edges). Returns 0.0 for graphs with no edges.

impl CsrIndex

pub fn has_weights(&self) -> bool

Whether this CSR has any weighted edges.

pub fn out_edge_weight(&self, edge_idx: usize) -> f64

Get the weight of the i-th outbound edge from a node (dense CSR only).

edge_idx is the absolute index into out_targets/out_weights. Returns 1.0 for unweighted graphs.

pub fn in_edge_weight(&self, edge_idx: usize) -> f64

Get the weight of the i-th inbound edge to a node (dense CSR only).

pub fn edge_weight(&self, src: &str, label: &str, dst: &str) -> Option<f64>

Get the weight of a specific outbound edge from src to dst via label.

Checks both dense and buffer. Returns 1.0 if the edge exists but has no weight, or None if the edge doesn’t exist.

pub fn iter_out_edges_weighted( &self, node: LocalNodeId, ) -> impl Iterator<Item = (u32, LocalNodeId, f64)>

Iterate outbound edges of a node with weights: (label_id, dst_id, weight).

Yields from both dense CSR and buffer, excluding deleted edges. Weights are 1.0 for unweighted graphs.

pub fn iter_out_edges_weighted_raw( &self, node: u32, ) -> impl Iterator<Item = (u32, u32, f64)>

Raw u32 variant of iter_out_edges_weighted. In-partition algorithm use only — see Self::iter_out_edges_raw for the safety rationale.

impl CsrIndex

pub fn traverse_bfs( &self, params: BfsParams<'_>, overlay: Option<&GraphOverlayDelta>, ) -> Vec<String>

BFS traversal. Returns all reachable node IDs within max_depth hops.

max_visited caps the number of nodes visited to prevent supernode fan-out explosion. Pass crate::traversal::DEFAULT_MAX_VISITED for the standard limit.

frontier_bitmap: when Some, only nodes whose surrogate is present in the bitmap are eligible as traversal targets. Start nodes are not gated — only newly discovered frontier nodes are checked.

overlay: when Some and non-empty, the traversal observes the transaction’s staged edge writes/deletes (read-your-own-writes), including through nodes reachable only via a staged edge. When None or empty, the durable-only dense fast path runs unchanged.

pub fn traverse_bfs_on( partition: Option<&CsrIndex>, params: BfsParams<'_>, overlay: Option<&GraphOverlayDelta>, ) -> Vec<String>

Self::traverse_bfs over an optional partition. None is a tenant with no CSR partition: the walk then follows only the staged edges of overlay, and returns no node without them.

pub fn traverse_bfs_with_depth( &self, start_nodes: &[&str], label_filter: &[&str], direction: Direction, max_depth: usize, max_visited: usize, ) -> Vec<(String, u8)>

BFS traversal returning nodes with their hop depth.

An empty label_filter keeps every edge. Otherwise an edge whose label is any listed label passes. The walk runs level by level and admits each level’s new nodes in node-name order until max_visited nodes are visited, like Self::traverse_bfs. The depth tag saturates at u8::MAX.

max_visited caps the number of nodes visited to prevent supernode fan-out explosion. Pass crate::traversal::DEFAULT_MAX_VISITED for the standard limit.

impl CsrIndex

pub fn shortest_path( &self, params: ShortestPathParams<'_>, overlay: Option<&GraphOverlayDelta>, ) -> Option<Vec<String>>

Shortest path via bidirectional BFS.

max_visited caps the combined forward+backward visited set to prevent supernode fan-out explosion. Pass crate::traversal::DEFAULT_MAX_VISITED for the standard limit.

frontier_bitmap: when Some, only nodes whose surrogate is present in the bitmap are eligible for expansion. The start and end nodes are not gated.

overlay: when Some and non-empty, the search observes the transaction’s staged edge writes/deletes (read-your-own-writes), including a path that must pass through a node reachable only via a staged edge. When None or empty, the durable-only dense bidirectional fast path runs unchanged.

pub fn shortest_path_on( partition: Option<&CsrIndex>, params: ShortestPathParams<'_>, overlay: Option<&GraphOverlayDelta>, ) -> Option<Vec<String>>

Self::shortest_path over an optional partition. None is a tenant with no CSR partition: the search then follows only the staged edges of overlay, and finds no path without them.

impl CsrIndex

pub fn subgraph( &self, start_nodes: &[&str], label_filter: &[&str], direction: Direction, max_depth: usize, max_visited: usize, overlay: Option<&GraphOverlayDelta>, ) -> Vec<(String, String, String)>

Materialize a subgraph as (src, label, dst) edge tuples within max_depth, expanding in direction.

Every expanded node records each of its edges in direction. The last admitted level is not expanded: it records only its edges in direction whose other endpoint is an admitted node, and admits no node.

An empty label_filter keeps every edge. Otherwise an edge whose label is any listed label passes.

max_visited caps the number of nodes visited to prevent supernode fan-out explosion. Pass crate::traversal::DEFAULT_MAX_VISITED for the standard limit.

overlay: when Some and non-empty, staged edges are included and staged tombstones subtract durable edges (read-your-own-writes), including through staged-only intermediate nodes. When None or empty, the durable-only dense path runs unchanged.

pub fn subgraph_on( partition: Option<&CsrIndex>, start_nodes: &[&str], label_filter: &[&str], direction: Direction, max_depth: usize, max_visited: usize, overlay: Option<&GraphOverlayDelta>, ) -> Vec<(String, String, String)>

Self::subgraph over an optional partition. None is a tenant with no CSR partition: the walk then follows only the staged edges of overlay, and returns no edge without them.

impl CsrIndex

pub fn traverse_surrogates_in_collection( &self, params: SurrogateBfsParams<'_>, ) -> SurrogateHops

BFS from surrogate seeds over one collection’s edges, returning surrogates and hop distances.

The frontier is the dense u32 CSR id, exactly as in the durable string-keyed path; the difference is that nothing is ever converted to a name. Nodes without a surrogate stay traversable — they just cannot be reported (see SurrogateHops::unaddressable).

The walk admits nodes in (depth, node name) order: each level’s new nodes in name order. When max_visited cuts the walk, the admitted set is the same however the edges are stored, which lets a cluster coordinator walking the same edges across partitions admit the same nodes.