yo_graph/

lib.rs

//! The graph model: adjacency runs a traversal can read at memory speed
//! (`11`).
//!
//! The embedded graph space had two things happen to it and neither was about
//! traversal speed. Kuzu, which would otherwise be the comparison, was acquired
//! in October 2025 and archived the next day. FalkorDB spent 2025 and 2026
//! rewriting in Rust and pointing at GraphRAG. Both events are about who is
//! willing to keep an embedded graph engine alive, which is why the format
//! being documented byte for byte and read by something other than this code is
//! a first class decision here rather than a nicety.
//!
//! What does not come along is the query processor. There is no Cypher, no GQL
//! and no factorised execution, because a graph database without a query
//! language is an adjacency structure with good ergonomics, and that is what an
//! agent memory or a recommendation workload actually calls. A traversal is an
//! iterator the caller drives, and its cost is written down rather than hidden
//! behind a planner.
//!
//! # What is here so far
//!
//! [`Adjacency`], the hot form of the adjacency plane. A run is the neighbours
//! of one node under one label in one direction, it is contiguous, and it is
//! appended to and deleted from in place. A one hop is a probe and a sequential
//! read; a two hop is a probe per neighbour over runs that can be prefetched
//! before any of them is read.
//!
//! ```
//! use yo_graph::{Adjacency, Dir};
//!
//! const FOLLOWS: u32 = 1;
//!
//! let mut g = Adjacency::new();
//! g.link(1, 2, FOLLOWS, 0);
//! g.link(2, 3, FOLLOWS, 1);
//!
//! let hop = g.neighbours(1, FOLLOWS, Dir::Out).to_vec();
//! let two: Vec<u64> = hop.iter().flat_map(|n| g.neighbours(*n, FOLLOWS, Dir::Out)).copied().collect();
//! assert_eq!(two, vec![3]);
//! ```
//!
//! Twelve bytes an edge is the payload, and the run headers and the capacity
//! slack take a graph shaped like LiveJournal to around 15 once it has settled.
//! That is the price of a structure where every operation is O(1).
//!
//! [`Csr`], the cold form, which is the same adjacency once nothing is changing
//! it: node grouped, gap coded and bit packed, read only, and about an order of
//! magnitude smaller. On an R-MAT graph it is 11.98 bits an edge as the ids
//! come, and 9.38 after [`csr::order_by_degree`] gives the hubs the small ids.
//! On a uniformly random graph it is 15.96 against a floor of 13.44, and the
//! ordering pass moves that by nothing, which is what says the difference
//! between the two graphs is the graph rather than the encoder.
//!
//! [`bisect`], the numbering that matters on a real graph. It reads the graph as
//! a bipartite one, splits the nodes in half, swaps nodes across the middle for
//! as long as an estimate of the compressed size goes down, and recurses, which
//! is Facebook's recursive graph bisection from 2016. On soc-LiveJournal1 it
//! takes the cold form to 15.00 bits an edge where degree ordering leaves it at
//! 19.00, and on web-Google to 15.04 against 20.21. It costs twelve minutes on
//! eight cores for a graph of seventy million edges, which is the trade the cold
//! form is for.
//!
//! Neither number is the 8 bits an edge the spec asks for, and [`csr`] has the
//! full breakdown of where the rest of it is.
//!
//! ```
//! use yo_graph::{Csr, csr};
//!
//! let mut edges = vec![(0u32, 3u32), (0, 1), (2, 0), (0, 9)];
//! let to = csr::order_by_degree(10, &edges);
//! csr::renumber(&mut edges, &to);
//!
//! let cold = Csr::build(10, &mut edges);
//! assert_eq!(cold.degree(to[0]), 3);
//! ```
//!
//! [`Graph`] is the two of them together with a document behind every node and
//! every edge. The typed `Graph<N, E>` surface, the ten command `G.*` family and
//! the algorithms are the rest of M7.

#![deny(missing_docs)]

pub mod adjacency;
pub mod algo;
pub mod bisect;
pub mod csr;
pub mod graph;
pub mod props;
pub mod snapshot;

pub use adjacency::{Adjacency, Dir};
pub use csr::Csr;
pub use graph::{Graph, NO_PROPS};
pub use props::{Props, id_key};
pub use snapshot::Snapshot;