Struct Adjacency 

pub struct Adjacency { /* private fields */ }

The neighbours of every node, under every label, in both directions.

use yo_graph::{Adjacency, Dir};

const FOLLOWS: u32 = 1;

let mut g = Adjacency::new();
g.link(1, 2, FOLLOWS, 100);
g.link(1, 3, FOLLOWS, 101);

assert_eq!(g.neighbours(1, FOLLOWS, Dir::Out), &[2, 3]);
assert_eq!(g.neighbours(2, FOLLOWS, Dir::In), &[1]);
assert_eq!(g.degree(1, FOLLOWS, Dir::Out), 2);

Implementations

impl Adjacency

pub fn new() -> Adjacency

An empty plane that indexes both directions, so In answers as well as Out does.

pub fn out_only() -> Adjacency

An empty plane that indexes outgoing edges only.

This halves the memory and halves the work an insert does, and it is the right choice whenever nothing asks the graph who points at a node. neighbours under Dir::In then answers nothing at all, which is why it is a decision at construction rather than a flag on a call: a walk that silently found no incoming edges because of how the plane was built would look exactly like a node that has none.

pub fn indexes_incoming(&self) -> bool

Whether incoming edges are indexed.

pub fn edges(&self) -> usize

How many edges have been linked and not unlinked.

pub fn is_empty(&self) -> bool

Whether any edge is linked.

pub fn runs(&self) -> usize

How many runs hold at least one edge.

pub fn link(&mut self, src: u64, dst: u64, label: u32, edge: u32)

Add an edge from src to dst under label, carrying edge as the slot of the edge record.

This appends. It does not look for an edge that is already there, for the reason in the module docs, so linking the same pair twice leaves two entries and unlinking it once leaves one.

pub fn unlink(&mut self, src: u64, dst: u64, label: u32) -> Option<u32>

Remove one edge from src to dst under label, and answer with the edge slot it was carrying.

Costs a scan of the run at each end, because finding which position an edge sits at is the one thing a plane keyed by node rather than by edge cannot do in a step. A caller that already knows the position wants Adjacency::unlink_at.

pub fn unlink_at( &mut self, node: u64, label: u32, dir: Dir, i: usize, ) -> Option<(u64, u32)>

Remove the edge at position i of one run, and answer with the neighbour and the edge slot that were there.

This is the O(1) primitive and it touches one end only, so the other end still holds its half of the edge. It is for a caller that tracks positions itself and will do both. Whatever used to be last has moved into i.

pub fn neighbours(&self, node: u64, label: u32, dir: Dir) -> &[u64]

The neighbours of node under label in dir, in one contiguous run.

One probe and then a sequential read. The order is whatever inserting and deleting left behind, because a delete moves the last entry into the hole it made.

pub fn edge_slots(&self, node: u64, label: u32, dir: Dir) -> &[u32]

The edge slots of node under label in dir, lined up one for one with Adjacency::neighbours.

pub fn degree(&self, node: u64, label: u32, dir: Dir) -> usize

How many edges node has under label in dir.

pub fn for_each_run( &self, label: u32, dir: Dir, f: impl FnMut(u64, &[u64], &[u32]), )

Every non empty run under label in dir, as the node and its two slices, in whatever order the table happens to hold them.

This is the read side of promotion. The cold form is built by walking the hot plane once and handing every run to an encoder, and there is no other way to get at a run whose node you have not already been told about, because the table is keyed by the node rather than ordered by it. The order is deliberately not promised: a caller that needs the runs in node order is building something sorted anyway and can sort what it collects.

pub fn prefetch(&self, node: u64, label: u32, dir: Dir)

Ask the cache for the slot a run’s header will be found in.

A multi hop walk knows its whole next frontier before it reads any of it, so it can issue these across the frontier and then come back and read. That is the same two walk shape 04 section 3 drains a command batch with, and it is what the two hop budget in G14 is actually spending: the probes are dependent loads, and the only way to make them cheap is to stop them being serial.

pub fn bytes(&self) -> usize

Resident bytes, counting the table, both arenas, and everything the free lists are still holding.

pub fn compact(&mut self)

Rebuild the table and the arenas with nothing spare in them.

A run that emptied leaves its header behind, a run that shrank leaves slack, and a free list holds blocks nothing has asked for again. None of that is worth chasing on the write path, so this is the sweep that reclaims it, and it is the natural thing to run before a settled part of the graph is promoted into the cold form. Every run comes out sized to exactly what it holds and laid out one after another, which is also the order the promotion wants to read them in.

Trait Implementations

impl Debug for Adjacency

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for Adjacency

fn default() -> Adjacency

Returns the “default value” for a type.