Module snapshot 

The graph flattened into dense arrays, which is the shape every algorithm wants (11 section 8).

crate::Adjacency is built for a graph that is being changed: a run is found by hashing the node and the label, it is grown and shrunk in place, and a node is whatever u64 the caller decided to call it. That is the right structure for a traversal, which touches a handful of runs and wants each one to be a probe and a sequential read, and it is the wrong structure for PageRank, which touches every run twenty times and wants node zero’s neighbours to be the first thing in the array.

So an algorithm runs over one of these instead. It is the same edges, renumbered from zero, in one flat CSR per direction, taken at a point in time. Nothing in here can change the graph and nothing here notices when the graph changes, which is the trade: a snapshot goes stale, and in exchange every algorithm below it is arrays and index arithmetic with no hashing on any inner loop.

use yo_graph::{Graph, NO_PROPS, Snapshot};

const FOLLOWS: u32 = 1;

let mut g = Graph::new();
g.link(10, 20, FOLLOWS, NO_PROPS)?;
g.link(20, 30, FOLLOWS, NO_PROPS)?;

let s = Snapshot::of(&g);
// Ids are renumbered from zero, in the order the graph's own ids sort.
assert_eq!(s.nodes(), 3);
assert_eq!(s.dense(20), Some(1));
assert_eq!(s.out(1), [2]);
assert_eq!(s.into_(1), [0]);
assert_eq!(s.id(2), 30);

Why the numbering is sorted and not arrival order

Because it has to be reproducible. Two snapshots of the same graph have to give the same dense id to the same node, or a caller cannot hold a PageRank vector from one run and a component table from another and compare them by index. The property store hands its ids back in whatever order its table happens to hold them, so the ids are sorted, and sorting is also the cheapest way to build the reverse map for the case that matters.

Two ways to turn a graph’s id into a dense one

A graph whose ids came out of a counter, which is every graph the wire path builds, has ids that are already 0..n. That gets a direct table: one Vec<u32> indexed by the id, one load per lookup, no comparisons. A graph whose ids are hashes or timestamps gets a binary search over the sorted ids, which is about twenty dependent loads instead of one.

The rule is the table when the highest id is less than twice the node count, so the table is never more than twice the size of the ids it replaces, and the choice is made once when the snapshot is built rather than per lookup. It only matters while the snapshot is being built, because after that every algorithm works in dense ids and never asks.

The reverse index is transposed and not read

The plane can index incoming edges and this does not use that. The incoming CSR here is the transpose of the outgoing one, which is a counting sort over the edges that were projected, because that is the only way the two can be guaranteed to be the same set of edges. It also means an algorithm that needs predecessors, which is most of the interesting ones, works on a graph built with crate::Graph::out_only.

Structs

Snapshot

A graph as dense arrays: ids renumbered from zero, one CSR per direction.