Struct Snapshot 

pub struct Snapshot { /* private fields */ }

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

Implementations

impl Snapshot

pub fn of(g: &Graph) -> Snapshot

Every node and every edge of g, under every label.

pub fn labelled(g: &Graph, labels: &[u32]) -> Snapshot

Every node of g, and the edges under the labels named.

Every node, including the ones that have no edge under any of these labels, because an algorithm’s answer is a vector indexed by node and a node that was left out of the numbering would shift every answer after it. An isolated node is an empty run and costs two offsets.

pub fn weighted( g: &Graph, labels: &[u32], field: &[u8], missing: u32, ) -> (Snapshot, Vec<u32>)

The same projection, and a weight for every outgoing edge in it.

The weight is read off the edge’s own document, out of the field named, which is where a weight lives in this engine: an edge is a document and a weight is one of its fields. The weights come back in the order the outgoing runs are in, so the weight of the edge out(node)[i] is weights[out_at(node) + i], and a shortest path only has to index the two arrays together.

An edge whose document has no such field, or has one that is not a number, or has a negative one, gets missing. A negative weight is refused rather than clamped because every shortest path algorithm worth having needs weights that do not go backwards, and quietly turning a minus five into a zero is a worse answer than using the default the caller chose.

A float is rounded to the nearest whole number, and anything above four billion is held at four billion, because a weight is u32 so that an edge costs four bytes rather than eight.

pub fn nodes(&self) -> u32

How many nodes there are, which is the length of every answer.

pub fn edges(&self) -> u64

How many edges were projected, counting a parallel edge as its own.

pub fn is_empty(&self) -> bool

Whether there is nothing here.

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

The graph’s own id for a dense one.

Panics

If node is not a node of this snapshot, which is a bug in the caller: every dense id an algorithm can be holding came out of 0..nodes().

pub fn dense(&self, id: u64) -> Option<u32>

The dense id for one of the graph’s, or None if it has no such node.

pub fn out(&self, node: u32) -> &[u32]

Node node’s outgoing neighbours.

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

Where node node’s outgoing run starts in the flat array.

Only useful next to something that was built alongside that array, which in practice means the weights out of Snapshot::weighted: the weight of out(node)[i] is weights[out_at(node) + i].

pub fn into_(&self, node: u32) -> &[u32]

Node node’s incoming neighbours.

The trailing underscore is because in is a keyword, and the name is still in because that is the word for what it is.

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

Neighbours in whichever direction, for an algorithm that takes one.

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

How many edges leave node.

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

How many edges arrive at node.

pub fn prefetch(&self, node: u32)

Ask the cache for a node’s outgoing run, before the loop that reads it.

The same call crate::Adjacency::prefetch is for and much cheaper to serve, because a dense run is one load of the offset and then a contiguous read rather than a hash and a probe.

pub fn memory_bytes(&self) -> usize

Resident bytes.

Trait Implementations

impl Clone for Snapshot

fn clone(&self) -> Snapshot

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Snapshot

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

Formats the value using the given formatter.

impl Default for Snapshot

fn default() -> Snapshot

Returns the “default value” for a type.