yo-graph 0.3.26

//! 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;

/// Why a test in this crate names two sizes rather than dividing one.
///
/// Miri charges per operation, and the two planes here are three orders of
/// magnitude apart. An [`Adjacency::link`] is a push onto a run, so a thousand
/// of them is around half a minute and cutting a count tenfold does what you
/// would expect. A [`Graph::link`] puts a document for the source, one for the
/// destination and one for the edge, and a document put hashes and indexes. It
/// is far more expensive, and it does not stay at one price: eleven of them
/// inside a test that then runs a search is under three seconds, and ninety
/// nine of the same thing does not finish inside two minutes. The cost grows
/// with the graph rather than with the edge, which is why the cuts here are
/// large, and why they are written as a pair of sizes rather than as a divide
/// through one helper. A tenth of a count that was chosen for a native run is
/// usually still too big to interpret, and now and then it is small enough to
/// make the test vacuous, and only the test itself knows which.
///
/// Where the count is the claim rather than a way of reaching it, the test
/// keeps its number and is skipped under Miri instead, and says so where it is
/// skipped. Those are worth naming because they come up together: a test that
/// measures bits an edge, or how close an estimate lands, or that one ordering
/// beats another by a margin, is measuring a population, and a smaller
/// population is a different measurement rather than a cheaper one.
///
/// The two figures above came off a census taken single threaded. Nextest
/// charges a test that is queued behind another one for the wait, so a parallel
/// census reads as much as fourteen times too slow and is no use for deciding
/// any of this. They are a laptop's numbers and the runner's will differ, but
/// the distance between the two planes is the code rather than the machine.
#[cfg(test)]
mod miri {}