Module graph 

A property graph: the adjacency plane with a document behind every node and every edge (11 section 3).

crate::Adjacency is the structure and crate::Props is what hangs off it. This is the two of them together, plus the one thing neither of them can own on its own: which edge slot an edge got.

use yo_doc::Builder;
use yo_graph::{Dir, Graph};

const FOLLOWS: u32 = 1;

fn doc(f: impl FnOnce(&mut Builder) -> yo_common::Result<()>) -> Vec<u8> {
    let mut b = Builder::new();
    f(&mut b).unwrap();
    b.finish().unwrap().to_vec()
}

let mut g = Graph::new();
g.put_node(1, &doc(|b| { b.begin_object()?; b.key(b"name")?; b.text("ada")?; b.end_object() }))?;
g.put_node(2, &doc(|b| { b.begin_object()?; b.key(b"name")?; b.text("grace")?; b.end_object() }))?;
let e = g.link(1, 2, FOLLOWS, &doc(|b| { b.begin_object()?; b.key(b"since")?; b.int(2026)?; b.end_object() }))?;

assert_eq!(g.neighbours(1, FOLLOWS, Dir::Out), [2]);
assert_eq!(g.node(2).and_then(|n| n.get(b"name").and_then(|v| v.as_text())), Some("grace"));
assert_eq!(g.edge(e).and_then(|n| n.get(b"since").and_then(|v| v.as_int())), Some(2026));

A node is its properties

The adjacency plane has no node table. A node is a run of neighbours, so a node with no edges is not in it at all, and asking whether a node exists is not a question it can answer.

So the node property store is the node table. Graph::put_node with an empty object is how an isolated node exists, Graph::has_node is a lookup in it, and Graph::nodes is its count. That is one structure doing two jobs rather than two structures that can disagree about which nodes there are, and the empty object it costs is four bytes.

Edge slots

An edge’s properties are keyed by a slot, and the slot is what the adjacency plane carries beside each neighbour. Graph::link hands one out and Graph::unlink gives it back, through a free list, because an edge store that only ever counts up turns a graph that churns into a store that grows forever.

A slot is reused only after the properties under it are gone, which is what stops a new edge from inheriting an old edge’s fields. That ordering is the whole of why the free list is here rather than in crate::Adjacency: the plane does not know there is a property store, and a free list that hands out a slot whose document is still there would be worse than no free list.

Parallel edges

Linking the same pair twice under the same label leaves two edges, because that is what crate::Adjacency::link does and what a property graph means by a multigraph. Each gets its own slot and so its own properties, which is the point: two RATED edges between the same person and the same film with different scores and different dates is the case, not the corner case.

Structs

Graph

A property graph.

Constants

NO_PROPS

What to pass as the properties of a node or an edge that has none.