Struct Csr

Source

pub struct Csr { /* private fields */ }

Expand description

A read only adjacency, node grouped and bit packed.

Built from an edge list over dense u32 ids, or from the hot form through an id mapping. See the module documentation for the layout and for what it costs.

use yo_graph::Csr;

let mut edges = vec![(0u32, 3u32), (0, 1), (2, 0), (0, 9)];
let cold = Csr::build(10, &mut edges);

assert_eq!(cold.degree(0), 3);
assert_eq!(cold.neighbours(0), vec![1, 3, 9]);
assert_eq!(cold.neighbours(1), Vec::<u32>::new());

Implementations§

Source §

impl Csr

Source

pub fn build(nodes: u32, edges: &mut [(u32, u32)]) -> Csr

Encode an edge list.

The list is sorted in place, which is the only reason it is taken by mutable reference. Every id has to be under nodes. Parallel edges are kept rather than merged, because whether two links between the same pair are one edge or two is the caller’s question and the answer costs a zero gap either way.

Source

pub fn from_hot( hot: &Adjacency, label: u32, dir: Dir, nodes: u32, id: impl Fn(u64) -> u32, ) -> Csr

Encode one label and direction of a hot plane.

id maps the caller’s node ids onto the dense u32 ids the cold form is over. That mapping is the node table’s job and the node table does not exist yet, so for now it is the caller’s, which also means a caller whose ids are already dense can pass a cast and pay nothing.

Source

pub fn nodes(&self) -> u32

How many node ids this was built over, whether or not they have edges.

Source

pub fn edges(&self) -> u64

How many edges are packed in here.

Source

pub fn is_empty(&self) -> bool

Whether there is nothing here.

Source

pub fn degree(&self, node: u32) -> u32

The degree of node, without decoding its run.

Two dependent loads, the offset and then the degree that starts the run, and neither of them touches a gap.

Source

pub fn neighbours_into(&self, node: u32, out: &mut Vec<u32>)

Decode the neighbours of node into out, ascending, replacing whatever was in it.

The buffer is the point: a walk decodes run after run and there is no reason for any of them but the first to allocate.

Source

pub fn neighbours(&self, node: u32) -> Vec<u32>

The neighbours of node, ascending, in a fresh vector.

The convenient one. A traversal should use neighbours_into and keep its buffer.

Source

pub fn prefetch(&self, node: u32)

Ask the cache for the word a node’s offset will be found in.

Same reason as the hot form’s: a frontier is known before any of it is read, and the loads that decode it are dependent, so the only way to make them cheap is to stop them being serial.

Source