Graph API

Graph API

The Graph API (mgraphdb::graph::Graph) is the public surface that ties the four storage layers into one ergonomic interface. "Everything is a node": an edge is simply a property whose value is PropValue::Edge, owned by its start node and pointing at its end node.

What it owns

Layer	Role
Node Store	one 12-byte record per node
Property/Edge Store	one 16-byte record per property or edge
String Store	deduplicated backing for strings too long to inline
live adjacency (Vec<Vec<PropId>>)	O(1) edge/property insert + iterate; exported to a CSR Index

While the graph is mutated, adjacency is kept in a live Vec<Vec<PropId>> for O(1) inserts and contiguous iteration. build_index() exports it to an immutable CSR IndexStore for persistence; open() rebuilds the live adjacency from that index.

Long-string routing (REQ-22 / REQ-37)

set_str routes by length automatically:

• ≤ 14 bytes → stored inline in the 16-byte property record (InlineStr).
• > 14 bytes → interned into the String Store; the record holds a StringRef(StrId).

string_value resolves either form back to a String transparently, so callers never see the distinction.

Traversal: outgoing and incoming

Edge records are owned by their start node, so outgoing traversal (out_edges) is a scan of the node's owned records. Incoming traversal would otherwise require scanning the whole graph, so the Graph keeps a reverse adjacency: incoming[target] = (source, edge PropId), updated on add_edge and rebuilt from the edges on open (sorted by PropId to preserve insertion order). in_edges / in_neighbors / in_degree are therefore served from a precomputed slice with no record decoding.

Note the asymmetry in the degree accessors:

• degree(node) — all owned records (properties and edges), O(1).
• out_degree(node) — outgoing edges only; decodes each owned record.
• in_degree(node) — incoming edges, O(1) from the reverse adjacency.

Deletion

delete_node is a soft delete: the node is tombstoned in the Node Store (its slot and id are never reused) and detached from the graph symmetrically, so no dangling edges remain:

• its outgoing edges are removed from each target's incoming list;
• its incoming edges are removed from each source's owned records — those sources no longer report an edge to the deleted node;
• the node's owned records, and the edge records pointing at it, are overwritten with None. Slots are not reclaimed, so record_count is unchanged (compaction is a future concern).

After deletion the node still counts toward node_count but not live_node_count; is_deleted returns true. Write operations (set_property, set_str, add_edge) on a deleted node are rejected with an error. delete_node returns Ok(false) for an out-of-range or already-deleted node, and handles self-loops. Deletion state survives save / open.

API

Method	Purpose
new() / with_compression(c)	empty graph (optionally compressed strings)
add_node() / add_typed_node(type_id)	create a node (optionally typed by a class node)
delete_node(node)	soft-delete a node and detach its edges both ways
live_node_count() / is_deleted(node)	count of live nodes / deletion check
set_property(node, &PropValue)	attach a typed property
set_str(node, &str)	attach a string, auto-routing long values
add_edge(from, to)	directed edge; sets HAS_OUT on from, HAS_IN on to
neighbors(node) / degree(node)	records owned by a node (props + edges)
out_edges(node) / out_degree(node)	end nodes / count of a node's outgoing edges
in_edges(node)	(source, edge PropId) for every edge pointing at the node
in_neighbors(node) / in_degree(node)	source nodes / count of incoming edges
properties(node)	(PropId, PropValue) pairs, edges excluded
value(pid) / string_value(pid)	decode a record; resolve a string transparently
build_index()	export live adjacency to a CSR IndexStore
save(dir) / open(dir)	persist / load all four segments

Example

use mgraphdb::graph::Graph;
use mgraphdb::prop_store::PropValue;

let mut g = Graph::new();

let person = g.add_node();              // a class node, used as a type
let alice  = g.add_typed_node(person);
let bob    = g.add_typed_node(person);

g.set_str(alice, "Alice")?;             // inline (≤ 14 bytes)
g.set_property(alice, &PropValue::I64(30))?;
g.set_str(bob, "Bob")?;
g.add_edge(alice, bob)?;                // Alice → Bob

assert_eq!(g.out_edges(alice)?, vec![bob]);
assert_eq!(g.in_neighbors(bob), vec![alice]);   // who points at Bob?
assert_eq!(g.properties(alice)?.len(), 2);      // name + age (edge excluded)

g.save("my_graph_dir")?;                // writes nodes/props/strings/index
let reloaded = Graph::open("my_graph_dir")?;

The demo binary (cargo run) builds and traverses a small social graph end to end.

First benchmarks

cargo bench --bench graph — indicative figures on a developer laptop (reduced sample size), graphs of N nodes with ~4 outgoing edges each:

Benchmark	Size	Time	Throughput
graph_build	1 000 nodes	~0.21 ms	~23 M elem/s
graph_build	10 000 nodes	~2.4 ms	~21 M elem/s
graph_traverse/out_edges_all	10 000 nodes	~0.72 ms	~13 M edge/s (decodes each edge)
graph_traverse/degree_all	10 000 nodes	~4.5 µs	~2.2 G elem/s (slice length only)
graph_traverse/in_edges_all	10 000 nodes	~4.5 µs	~2.2 G elem/s (precomputed reverse adjacency)
graph_index/build_index	~50 000 records	~0.21 ms	~249 M elem/s
graph_persist/save	~50 000 records	~0.92 ms	—
graph_persist/open	~50 000 records	~0.99 ms	—

Numbers are first-cut and meant for relative comparison as the design evolves, not as headline specifications.

Design notes

• The live adjacency makes the Graph API write-friendly; the persisted CSR index makes reload read-friendly. This pairs the two layouts discussed on the Persistent Layer page.
• Tombstoned nodes still occupy a slot; delete_node clears their adjacency and orphans their records (set to None) but does not reclaim slots — compaction is a future concern.
• A node out of range is rejected with an error rather than panicking.

See the Requirements page (REQ-01–03, REQ-22, REQ-60–63) for the numbered, traceable form of this design.