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.

Every property and edge carries a key — a NodeId that names the property or labels the edge (RDF-predicate style; keys are themselves nodes). The key is optional: NO_KEY means unkeyed. This is what makes the graph queryable — get_property(node, key) and edges_of_type(node, predicate) resolve by name rather than by position.

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:

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

(The inline limit is 10 rather than 14 because each record now spends 4 bytes on the key — see Persistent Layer.)

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.

Find (reverse lookup)

Keys make the graph queryable by value. Three reverse lookups scan the live nodes and return matches in ascending node order, each node once (edges and deleted nodes excluded):

• find_by_property(key, &value) — exact PropValue equality.
• find_by_str(key, s) — compares the resolved text, so inline and String-Store storage match alike (prefer this for strings).
• find_by_key(key) — nodes that have any property under key.

let alices = g.find_by_str(name, "Alice")?;       // -> [node, ...]
let adults = g.find_by_property(age, &PropValue::I64(30))?;
let named  = g.find_by_key(name)?;

These are full scans, O(total records) per query — the correct, allocation -light first cut. A secondary inverted index (key, value) → [node] (maintained on write, rebuilt on load, like the CSR adjacency) is the planned optimisation when query volume warrants it.

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)
from_edge_list(reader)	build a graph from a SNAP-style edge list (sparse ids remapped)
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, key, &PropValue)	attach a typed property under key
set_str(node, key, &str)	attach a string under key, auto-routing long values
add_edge(from, predicate, to)	directed labelled 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
edges_of_type(node, predicate)	end nodes of outgoing edges with that predicate
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, key, PropValue) tuples, edges excluded
get_property(node, key) / get_str(node, key)	first property/string with that key
find_by_property(key, &PropValue)	live nodes with key = value (exact equality)
find_by_str(key, &str)	live nodes whose string key resolves to the text
find_by_key(key)	live nodes that have any property under key
value(pid) / string_value(pid) / key_of(pid)	decode a record's value / string / key
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 name   = g.add_node();              // key / predicate nodes
let age    = g.add_node();
let knows  = g.add_node();
let alice  = g.add_typed_node(person);
let bob    = g.add_typed_node(person);

g.set_str(alice, name, "Alice")?;       // inline (≤ 10 bytes)
g.set_property(alice, age, &PropValue::I64(30))?;
g.set_str(bob, name, "Bob")?;
g.add_edge(alice, knows, bob)?;         // Alice KNOWS Bob

assert_eq!(g.get_str(alice, name)?.as_deref(), Some("Alice"));
assert_eq!(g.edges_of_type(alice, knows)?, 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.

Importing edge lists

Graph::from_edge_list(reader) builds a graph from a SNAP-style edge list — one from<whitespace>to integer pair per line, # comments and blank lines skipped. Source ids may be sparse; they are remapped to contiguous NodeIds in first-seen order, and each line becomes one directed, unlabelled (NO_KEY) edge. Undirected datasets list each edge in both directions, so they load as a symmetric directed graph.

let f = std::fs::File::open("ca-HepTh.txt")?;
let g = Graph::from_edge_list(std::io::BufReader::new(f))?;

First benchmarks

cargo bench --bench graph — indicative figures on a developer laptop (reduced sample size). The synthetic graphs are N nodes with ~4 uniform-random outgoing edges each; graph_realworld runs on the real SNAP ca-HepTh collaboration network (9,877 nodes / 51,971 edges, clustered power-law).

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_find/find_by_str	~50 000 records	~0.63 ms	full scan (resolves strings)
graph_find/find_by_property_i64	~50 000 records	~0.53 ms	full scan (PropValue equality)
graph_persist/save	~50 000 records	~0.92 ms	—
graph_persist/open	~50 000 records	~0.99 ms	—
graph_realworld/traverse_out_all (ca-HepTh)	51 971 edges	~0.92 ms	real power-law graph
graph_realworld/build_index (ca-HepTh)	51 971 edges	~0.29 ms	real power-law graph

Numbers are first-cut and meant for relative comparison as the design evolves, not as headline specifications. The real ca-HepTh graph shows per-edge costs comparable to the synthetic wiring, so the data structures hold up under a realistic clustered/power-law degree distribution. The dataset is not committed — see benches/data/README.md for the one-line download.

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.