Module triangle 

Counting triangles, in the ordered form.

Schank and Wagner, “Finding, Counting and Listing All Triangles in Large Graphs”, WEA 2005, which is the forward algorithm, plus the degree ordering from Ortmann and Brandes, “Triangle Listing Algorithms: Back from the Diversion”, ALENEX 2014, whose point is that most of the published variants are the same algorithm under different orderings and the ordering is what decides how fast they are.

What is being counted

Three nodes with an edge between each pair, counted once however many ways there are to walk it. Direction is ignored, a self loop is not an edge for this purpose, and two parallel edges between the same pair are one edge. That is the only definition that makes the answer a property of the graph rather than of how it happened to be written down, and it is what every published number is counting, so a number from here can be checked against one from somewhere else.

The ordering is the whole algorithm

The naive count walks every pair of neighbours of every node and asks whether they are joined, which counts each triangle six times and spends its whole life on the highest degree node in the graph.

The ordered form gives every node a rank, and only ever looks from a node to the neighbours that outrank it. A triangle then has exactly one lowest ranked corner and is found exactly once, from there.

Which way round the rank goes is the whole thing. Rank by degree with the lowest first, so that every node looks up at the neighbours with more edges than it has. The hub is then at the top of the order with almost nothing above it, so its list is nearly empty and the work lands on the nodes that have three edges each. Rank it the other way and the hub carries a list of every node it touches and is intersected against all of them, which is measurably worse than not ordering at all.

On a graph where every node has about the same degree the ordering does not matter and the cost is the same either way.

Intersecting two sorted lists

A merge when the two are about the same length, and a binary search of the long one for each member of the short one when one is more than 32 times the other. A merge of a 3 element list against a 400 thousand element list reads all 400 thousand, and looking up three of them costs about sixty loads, so the switch is worth having and the exact ratio it happens at is not.

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

let mut g = Graph::new();
for (a, b) in [(1u64, 2u64), (2, 3), (3, 1)] {
    g.link(a, b, 1, NO_PROPS)?;
}

assert_eq!(algo::triangle_count(&Snapshot::of(&g)), 1);

Functions

triangle_count

How many triangles the graph has, reading it as undirected and simple.