Module algo 

The algorithms, over a crate::Snapshot (11 section 8).

Every one of these is a whole graph computation rather than a traversal: it reads every node, several times, in an order it chooses. That is the opposite of what the adjacency plane is built for, which is why they all take a snapshot and none of them takes a crate::Graph.

What is implemented and where it comes from

These are not folk implementations. Each one is the published algorithm that is currently the fastest single machine answer for its problem, and the reference is named in the module that implements it, so a reader can check the code against the paper rather than against a guess.

bfs() is direction optimizing, from Beamer, Asanović and Patterson at SC12, which is the same algorithm the GAP benchmark suite measures and the reason a breadth first search over a social graph is not bound by the size of its frontier.

wcc() is Afforest, from Sutton, Ben-Nun and Barak at IPDPS 2018, which finds the giant component out of a two neighbour sample and then only looks at the edges of the nodes that are not in it.

pagerank() is the pull form, which is the one the GAP suite measures, with the mass that lands on a dead end handed back out rather than dropped, which is what the 1999 paper describes and what GAP leaves out.

triangle_count() is the ordered count from Schank and Wagner at WEA 2005 under the degree ordering Ortmann and Brandes recommend at ALENEX 2014, so a hub is intersected against almost nothing rather than against everybody.

sssp() is delta stepping, from Meyer and Sanders in the Journal of Algorithms 2003, which settles a band of nodes at a time instead of one at a time so the reads are independent of each other and a heap is not in the way.

scc() is Tarjan from 1972, which is still the fastest single core answer for strong components, written with its frames in a Vec so a long chain does not take the process down with it.

leiden() is Traag, Waltman and van Eck from 2019, which is Louvain with the step that stops it handing back a community in two disconnected halves. louvain() itself is here to be measured against it, and label_propagation() is the one to reach for when even Louvain is too much work for the size of the graph.

betweenness() is Brandes from 2001, sampled over random sources the way Brandes and Pich describe in 2007, which is the only centrality here that finds the node whose removal would cut the graph in half.

Why they are deterministic

Several of these sample or shuffle, and all of them draw from yo_common::Rng with a fixed seed. A caller who runs the same algorithm over the same snapshot twice gets the same answer, including the same representative for a component, the same nodes chosen for a sample and the same communities. That is worth more than the entropy is: an algorithm whose answer moves between runs cannot be tested against a reference implementation and cannot be diffed between two versions of this crate.

Re-exports

pub use betweenness::Between;

pub use betweenness::betweenness;

pub use betweenness::betweenness_exact;

pub use betweenness::betweenness_with;

pub use bfs::UNREACHED;

pub use bfs::bfs;

pub use community::leiden;

pub use community::leiden_with;

pub use community::louvain;

pub use community::louvain_with;

pub use community::modularity;

pub use community::modularity_with;

pub use label_propagation::label_propagation;

pub use label_propagation::label_propagation_with;

pub use pagerank::Rank;

pub use pagerank::pagerank;

pub use pagerank::pagerank_with;

pub use scc::scc;

pub use sssp::UNREACHABLE;

pub use sssp::sssp;

pub use sssp::sssp_with;

pub use triangle::triangle_count;

pub use wcc::wcc;

Modules

betweenness

How often each node sits in the middle of somebody else’s shortest path.

bfs

Breadth first search, direction optimizing.

community

Communities, by moving nodes until modularity stops going up.

label_propagation

Communities, by everyone taking the label most of their neighbours have.

pagerank

PageRank, pulled rather than pushed.

scc

Strongly connected components, in one pass, without the stack.

sssp

Single source shortest paths, by delta stepping.

triangle

Counting triangles, in the ordered form.

wcc

Weakly connected components, by Afforest.

Structs

Components

Which component each node is in.