Appearance

@graphty/algorithms / index / ALGORITHMS

Variable: ALGORITHMS ​

const ALGORITHMS: object

Defined in: catalog.ts:215

Every algorithm of @graphty/algorithms, keyed by its export name.

Type Declaration ​

adamicAdarForPairs ​

readonly adamicAdarForPairs: object

adamicAdarForPairs.accelerator ​

readonly accelerator: null = null

adamicAdarForPairs.category ​

readonly category: "link-prediction" = "link-prediction"

adamicAdarForPairs.direction ​

readonly direction: "any" = "any"

adamicAdarForPairs.dispatch ​

readonly dispatch: null = null

adamicAdarForPairs.fn ​

readonly fn: (s, pairs, o) => F64 = adamicAdarForPairs

Adamic-Adar scores of the given pairs, in order.

Parameters ​
s ​

GraphSnapshot

The snapshot

pairs ​

NodePairs

The pairs

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

F64

One score per pair

adamicAdarForPairs.inputs ​

readonly inputs: readonly [AlgorithmInput]

adamicAdarForPairs.name ​

readonly name: "adamicAdarForPairs" = "adamicAdarForPairs"

adamicAdarForPairs.requiredOptions ​

readonly requiredOptions: readonly [] = []

adamicAdarForPairs.result ​

readonly result: "pair-scores" = "pair-scores"

adamicAdarForPairs.values ​

readonly values: readonly [] = []

adamicAdarForPairs.weights ​

readonly weights: "never" = "never"

adamicAdarPrediction ​

readonly adamicAdarPrediction: object

adamicAdarPrediction.accelerator ​

readonly accelerator: null = null

adamicAdarPrediction.category ​

readonly category: "link-prediction" = "link-prediction"

adamicAdarPrediction.direction ​

readonly direction: "any" = "any"

adamicAdarPrediction.dispatch ​

readonly dispatch: "adamicAdarPrediction" = "adamicAdarPrediction"

adamicAdarPrediction.fn ​

readonly fn: (s, o) => LinkPredictionResult = adamicAdarPrediction

Adamic-Adar scores of every pair not already joined, ranked.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

LinkPredictionOptions = {}

Options

Returns ​

LinkPredictionResult

The pairs with a positive score, highest first

adamicAdarPrediction.inputs ​

readonly inputs: readonly [] = []

adamicAdarPrediction.name ​

readonly name: "adamicAdarPrediction" = "adamicAdarPrediction"

adamicAdarPrediction.requiredOptions ​

readonly requiredOptions: readonly [] = []

adamicAdarPrediction.result ​

readonly result: "link-predictions" = "link-predictions"

adamicAdarPrediction.values ​

readonly values: readonly [] = []

adamicAdarPrediction.weights ​

readonly weights: "never" = "never"

adamicAdarScore ​

readonly adamicAdarScore: object

adamicAdarScore.accelerator ​

readonly accelerator: null = null

adamicAdarScore.category ​

readonly category: "link-prediction" = "link-prediction"

adamicAdarScore.direction ​

readonly direction: "any" = "any"

adamicAdarScore.dispatch ​

readonly dispatch: null = null

adamicAdarScore.fn ​

readonly fn: (s, uNode, vNode, o) => number = adamicAdarScore

The Adamic-Adar index of two nodes: the sum over distinct common neighbours z of 1 / ln(degree(z)).

Parameters ​
s ​

GraphSnapshot

The snapshot

uNode ​

NodeRef

A node: its index, or { id }

vNode ​

NodeRef

A node: its index, or { id }

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

number

The score

adamicAdarScore.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

adamicAdarScore.name ​

readonly name: "adamicAdarScore" = "adamicAdarScore"

adamicAdarScore.requiredOptions ​

readonly requiredOptions: readonly [] = []

adamicAdarScore.result ​

readonly result: "number" = "number"

adamicAdarScore.values ​

readonly values: readonly [] = []

adamicAdarScore.weights ​

readonly weights: "never" = "never"

allPairsShortestPath ​

readonly allPairsShortestPath: object

allPairsShortestPath.accelerator ​

readonly accelerator: "allPairsShortestPath" = "allPairsShortestPath"

allPairsShortestPath.category ​

readonly category: "shortest-path" = "shortest-path"

allPairsShortestPath.direction ​

readonly direction: "any" = "any"

allPairsShortestPath.dispatch ​

readonly dispatch: "allPairsShortestPath" = "allPairsShortestPath"

allPairsShortestPath.fn ​

readonly fn: (s, options) => ApspResult = allPairsShortestPath

All-pairs shortest paths over a snapshot.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

ApspOptions = {}

Weights, strategy, paths and the size bound

Returns ​

ApspResult

The distance matrix and the path accessors

allPairsShortestPath.inputs ​

readonly inputs: readonly [] = []

allPairsShortestPath.name ​

readonly name: "allPairsShortestPath" = "allPairsShortestPath"

allPairsShortestPath.requiredOptions ​

readonly requiredOptions: readonly [] = []

allPairsShortestPath.result ​

readonly result: "all-pairs" = "all-pairs"

allPairsShortestPath.values ​

readonly values: readonly [] = []

allPairsShortestPath.weights ​

readonly weights: "by-default" = "by-default"

astar ​

readonly astar: object

astar.accelerator ​

readonly accelerator: null = null

astar.category ​

readonly category: "shortest-path" = "shortest-path"

astar.direction ​

readonly direction: "any" = "any"

astar.dispatch ​

readonly dispatch: null = null

astar.fn ​

readonly fn: (g, sourceNode, targetNode, heuristic, options) => AstarResult = astar

A* between two nodes: Dijkstra keyed by cost so far plus heuristic(node, target), stopping when the target is taken from the queue. An expanded node is never reopened, as in legacy astar, so the path is shortest when the heuristic is consistent. The predecessor is the relaxing ARC, so a parallel edge on the path is the exact edge.

Parameters ​
g ​

AdjacencyView

The adjacency to search

sourceNode ​

NodeRef

The node to start from: its index, or { id }

targetNode ​

NodeRef

The node to reach: its index, or { id }

heuristic ​

(node, target) => number

Estimated remaining cost from a node index to the target index

options? ​

PathOptions = {}

Per-arc weight override

Returns ​

AstarResult

The path, plus the per-node scores and the expansion order

astar.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput, { kind: "heuristic"; name: "heuristic"; }]

astar.name ​

readonly name: "astar" = "astar"

astar.requiredOptions ​

readonly requiredOptions: readonly [] = []

astar.result ​

readonly result: "path" = "path"

astar.values ​

readonly values: readonly [] = []

astar.weights ​

readonly weights: "always" = "always"

bellmanFord ​

readonly bellmanFord: object

bellmanFord.accelerator ​

readonly accelerator: "bellmanFord" = "bellmanFord"

bellmanFord.category ​

readonly category: "shortest-path" = "shortest-path"

bellmanFord.direction ​

readonly direction: "any" = "any"

bellmanFord.dispatch ​

readonly dispatch: "bellmanFord" = "bellmanFord"

bellmanFord.fn ​

readonly fn: (g, sourceNode, options) => BellmanFordResult = bellmanFord

Bellman-Ford single-source shortest paths, index-based, for weights that may be negative. It relaxes every arc, so an undirected edge is relaxed both ways (it has an arc in each direction), and one negative undirected edge is therefore a negative cycle. Rounds stop early once one changes nothing; after nodeCount - 1 rounds one more round decides hasNegativeCycle. The predecessor is the relaxing ARC, as in dijkstra, so a parallel edge on a path is identified exactly.

Parameters ​
g ​

AdjacencyView

The adjacency to search

sourceNode ​

NodeRef

The node to start from: its index, or { id }

options? ​

SsspOptions = {}

Cutoff (a relaxation beyond it is skipped) and per-arc weight override

Returns ​

BellmanFordResult

The distances, the predecessor arcs, the path accessors and the negative-cycle flag

bellmanFord.inputs ​

readonly inputs: readonly [AlgorithmInput]

bellmanFord.name ​

readonly name: "bellmanFord" = "bellmanFord"

bellmanFord.requiredOptions ​

readonly requiredOptions: readonly [] = []

bellmanFord.result ​

readonly result: "shortest-paths" = "shortest-paths"

bellmanFord.values ​

readonly values: readonly ["dist", "predArc"]

bellmanFord.weights ​

readonly weights: "always" = "always"

betweennessCentrality ​

readonly betweennessCentrality: object

betweennessCentrality.accelerator ​

readonly accelerator: "betweennessCentrality" = "betweennessCentrality"

betweennessCentrality.category ​

readonly category: "centrality" = "centrality"

betweennessCentrality.direction ​

readonly direction: "any" = "any"

betweennessCentrality.dispatch ​

readonly dispatch: "betweennessCentrality" = "betweennessCentrality"

betweennessCentrality.fn ​

readonly fn: (s, options) => BetweennessResult = betweennessCentrality

Node betweenness centrality by Brandes' algorithm: breadth-first, so weights are ignored, as in the legacy betweennessCentrality, whose scores this equals on every graph it can hold. A sampled run (sources or k) is the UNSCALED sum over the sources run, as the WebGPU accelerator reports it.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

BetweennessOptions = {}

Normalisation, endpoints and sampling

Returns ​

BetweennessResult

One score per node index; iterations is the number of sources run

Throws ​

RangeError for a bad sources or k

betweennessCentrality.inputs ​

readonly inputs: readonly [] = []

betweennessCentrality.name ​

readonly name: "betweennessCentrality" = "betweennessCentrality"

betweennessCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

betweennessCentrality.result ​

readonly result: "node-scores" = "node-scores"

betweennessCentrality.values ​

readonly values: readonly ["scores"]

betweennessCentrality.weights ​

readonly weights: "never" = "never"

bidirectionalDijkstra ​

readonly bidirectionalDijkstra: object

bidirectionalDijkstra.accelerator ​

readonly accelerator: null = null

bidirectionalDijkstra.category ​

readonly category: "shortest-path" = "shortest-path"

bidirectionalDijkstra.direction ​

readonly direction: "any" = "any"

bidirectionalDijkstra.dispatch ​

readonly dispatch: null = null

bidirectionalDijkstra.fn ​

readonly fn: (s, sourceNode, targetNode, options) => PathResult = bidirectionalDijkstra

Bidirectional Dijkstra between two nodes: one search forward from the source, one backward from the target over reverse(), each step taken by the side whose next key is smaller, stopping once the two next keys sum to at least the best path found. That is the point-to-point query legacy dijkstraPath answers. The path is recorded as ARCS, so a parallel edge on it is the exact edge.

Parameters ​
s ​

GraphSnapshot

The snapshot to search

sourceNode ​

NodeRef

The node to start from: its index, or { id }

targetNode ​

NodeRef

The node to reach: its index, or { id }

options? ​

PathOptions = {}

Per-arc weight override

Returns ​

PathResult

The distance, the node path and the logical edges on it

Throws ​

Error when any weight is negative

bidirectionalDijkstra.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

bidirectionalDijkstra.name ​

readonly name: "bidirectionalDijkstra" = "bidirectionalDijkstra"

bidirectionalDijkstra.requiredOptions ​

readonly requiredOptions: readonly [] = []

bidirectionalDijkstra.result ​

readonly result: "path" = "path"

bidirectionalDijkstra.values ​

readonly values: readonly [] = []

bidirectionalDijkstra.weights ​

readonly weights: "always" = "always"

breadthFirstSearch ​

readonly breadthFirstSearch: object

breadthFirstSearch.accelerator ​

readonly accelerator: "breadthFirstSearch" = "breadthFirstSearch"

breadthFirstSearch.category ​

readonly category: "traversal" = "traversal"

breadthFirstSearch.direction ​

readonly direction: "any" = "any"

breadthFirstSearch.dispatch ​

readonly dispatch: "breadthFirstSearch" = "breadthFirstSearch"

breadthFirstSearch.fn ​

readonly fn: (g, startNode, options) => BfsResult = breadthFirstSearch

Breadth-first search over out-neighbours. Takes any AdjacencyView, so s.reverse() gives an in-neighbour BFS with no extra code.

Parameters ​
g ​

AdjacencyView

The adjacency to traverse

startNode ​

NodeRef

The node to start from: its index, or { id }

options? ​

BfsOptions = {}

Traversal options

Returns ​

BfsResult

The visit order, the parent array, the depth array and the visited count

breadthFirstSearch.inputs ​

readonly inputs: readonly [AlgorithmInput]

breadthFirstSearch.name ​

readonly name: "breadthFirstSearch" = "breadthFirstSearch"

breadthFirstSearch.requiredOptions ​

readonly requiredOptions: readonly [] = []

breadthFirstSearch.result ​

readonly result: "traversal" = "traversal"

breadthFirstSearch.values ​

readonly values: readonly ["depth", "parent"]

breadthFirstSearch.weights ​

readonly weights: "never" = "never"

closenessCentrality ​

readonly closenessCentrality: object

closenessCentrality.accelerator ​

readonly accelerator: "closenessCentrality" = "closenessCentrality"

closenessCentrality.category ​

readonly category: "centrality" = "centrality"

closenessCentrality.direction ​

readonly direction: "any" = "any"

closenessCentrality.dispatch ​

readonly dispatch: "closenessCentrality" = "closenessCentrality"

closenessCentrality.fn ​

readonly fn: (s, options) => ClosenessResult = closenessCentrality

Closeness centrality of every node: 1 / sum(distance to each reached node) by default, the legacy closenessCentrality (hops) and weightedClosenessCentrality (weighted: true) numbers. The weighted route reads the snapshot's f32 arc weights, so it matches legacy to f32 rounding; pass the f64 weights as weights for the exact legacy sums. As in legacy, a node's distance is final once it is searched from, so a negative weight gives the legacy (not the true shortest) distance and never loops. An unreached node adds nothing, and a node that reaches nothing scores 0.

SAMPLED (sources or k): the searches run from the sampled sources over the IN-arcs, so each search measures every node's distance TO that source, and each node's sums run over the sources it reaches (itself excluded) instead of over every node it reaches. Everything else is unchanged: the same formula is applied to those sums, with the same n - 1 under normalized and no extrapolation to the whole graph -- the UNSCALED rule sampled betweenness follows. So a sample of every node gives exactly the exact scores (up to the order floating-point sums are added in), and on a sample of k sources 1 / score is the summed distance to those k sources: multiply the plain score by k / n for the Eppstein-Wang estimate of the exact one. A harmonic score (normalized or not) sums reciprocal distances, so it needs the inverse, n / k; a normalized plain score divides by the number of sources reached, which already rescales it, so it needs no factor. On an undirected snapshot the in-arcs are the out-arcs. Two corners are measured from the source's side and so differ from an exact run even over a full sample: a weighted cutoff (the node just past it is admitted from the source's end of the path) and a negative weight (the legacy settle rule is not symmetric).

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

ClosenessOptions = {}

Normalisation, harmonic form, cutoff, weights and sampling

Returns ​

ClosenessResult

One score per node index; iterations and sourcesUsed are the number of searches run

Throws ​

RangeError for a bad sources or k

closenessCentrality.inputs ​

readonly inputs: readonly [] = []

closenessCentrality.name ​

readonly name: "closenessCentrality" = "closenessCentrality"

closenessCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

closenessCentrality.result ​

readonly result: "node-scores" = "node-scores"

closenessCentrality.values ​

readonly values: readonly ["scores"]

closenessCentrality.weights ​

readonly weights: "on-request" = "on-request"

commonNeighborsForPairs ​

readonly commonNeighborsForPairs: object

commonNeighborsForPairs.accelerator ​

readonly accelerator: null = null

commonNeighborsForPairs.category ​

readonly category: "link-prediction" = "link-prediction"

commonNeighborsForPairs.direction ​

readonly direction: "any" = "any"

commonNeighborsForPairs.dispatch ​

readonly dispatch: null = null

commonNeighborsForPairs.fn ​

readonly fn: (s, pairs, o) => F64 = commonNeighborsForPairs

Common-neighbour scores of the given pairs, in order.

Parameters ​
s ​

GraphSnapshot

The snapshot

pairs ​

NodePairs

The pairs

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

F64

One score per pair

commonNeighborsForPairs.inputs ​

readonly inputs: readonly [AlgorithmInput]

commonNeighborsForPairs.name ​

readonly name: "commonNeighborsForPairs" = "commonNeighborsForPairs"

commonNeighborsForPairs.requiredOptions ​

readonly requiredOptions: readonly [] = []

commonNeighborsForPairs.result ​

readonly result: "pair-scores" = "pair-scores"

commonNeighborsForPairs.values ​

readonly values: readonly [] = []

commonNeighborsForPairs.weights ​

readonly weights: "never" = "never"

commonNeighborsPrediction ​

readonly commonNeighborsPrediction: object

commonNeighborsPrediction.accelerator ​

readonly accelerator: null = null

commonNeighborsPrediction.category ​

readonly category: "link-prediction" = "link-prediction"

commonNeighborsPrediction.direction ​

readonly direction: "any" = "any"

commonNeighborsPrediction.dispatch ​

readonly dispatch: "commonNeighborsPrediction" = "commonNeighborsPrediction"

commonNeighborsPrediction.fn ​

readonly fn: (s, o) => LinkPredictionResult = commonNeighborsPrediction

Common-neighbour scores of every pair not already joined, ranked.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

LinkPredictionOptions = {}

Options

Returns ​

LinkPredictionResult

The pairs with a positive score, highest first

commonNeighborsPrediction.inputs ​

readonly inputs: readonly [] = []

commonNeighborsPrediction.name ​

readonly name: "commonNeighborsPrediction" = "commonNeighborsPrediction"

commonNeighborsPrediction.requiredOptions ​

readonly requiredOptions: readonly [] = []

commonNeighborsPrediction.result ​

readonly result: "link-predictions" = "link-predictions"

commonNeighborsPrediction.values ​

readonly values: readonly [] = []

commonNeighborsPrediction.weights ​

readonly weights: "never" = "never"

commonNeighborsScore ​

readonly commonNeighborsScore: object

commonNeighborsScore.accelerator ​

readonly accelerator: null = null

commonNeighborsScore.category ​

readonly category: "link-prediction" = "link-prediction"

commonNeighborsScore.direction ​

readonly direction: "any" = "any"

commonNeighborsScore.dispatch ​

readonly dispatch: null = null

commonNeighborsScore.fn ​

readonly fn: (s, u, v, o) => number = commonNeighborsScore

The number of distinct common neighbours of two nodes, by a merge of their sorted rows.

Parameters ​
s ​

GraphSnapshot

The snapshot

u ​

number

A node index

v ​

number

A node index

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

number

The count of distinct common neighbours

commonNeighborsScore.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

commonNeighborsScore.name ​

readonly name: "commonNeighborsScore" = "commonNeighborsScore"

commonNeighborsScore.requiredOptions ​

readonly requiredOptions: readonly [] = []

commonNeighborsScore.result ​

readonly result: "number" = "number"

commonNeighborsScore.values ​

readonly values: readonly [] = []

commonNeighborsScore.weights ​

readonly weights: "never" = "never"

compareAdamicAdarWithCommonNeighbors ​

readonly compareAdamicAdarWithCommonNeighbors: object

compareAdamicAdarWithCommonNeighbors.accelerator ​

readonly accelerator: null = null

compareAdamicAdarWithCommonNeighbors.category ​

readonly category: "link-prediction" = "link-prediction"

compareAdamicAdarWithCommonNeighbors.direction ​

readonly direction: "any" = "any"

compareAdamicAdarWithCommonNeighbors.dispatch ​

readonly dispatch: null = null

compareAdamicAdarWithCommonNeighbors.fn ​

readonly fn: (s, edges, nonEdges, o) => object = compareAdamicAdarWithCommonNeighbors

Both evaluations on the same held-out sets. The common-neighbour side always intersects the two OUT rows, whatever directed says, as the legacy function of this name does; the Adamic-Adar side honours directed.

Parameters ​
s ​

GraphSnapshot

The training snapshot

edges ​

NodePairs

The held-out edges

nonEdges ​

NodePairs

The non-edges

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

object

The two sets of metrics

adamicAdar ​

adamicAdar: LinkPredictionMetrics

commonNeighbors ​

commonNeighbors: LinkPredictionMetrics

compareAdamicAdarWithCommonNeighbors.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

compareAdamicAdarWithCommonNeighbors.name ​

readonly name: "compareAdamicAdarWithCommonNeighbors" = "compareAdamicAdarWithCommonNeighbors"

compareAdamicAdarWithCommonNeighbors.requiredOptions ​

readonly requiredOptions: readonly [] = []

compareAdamicAdarWithCommonNeighbors.result ​

readonly result: "metrics" = "metrics"

compareAdamicAdarWithCommonNeighbors.values ​

readonly values: readonly [] = []

compareAdamicAdarWithCommonNeighbors.weights ​

readonly weights: "never" = "never"

condensation ​

readonly condensation: object

condensation.accelerator ​

readonly accelerator: null = null

condensation.category ​

readonly category: "components" = "components"

condensation.direction ​

readonly direction: "directed" = "directed"

condensation.dispatch ​

readonly dispatch: null = null

condensation.fn ​

readonly fn: (s, options) => CondensationResult = condensation

The condensation of a directed graph: its strongly connected components, and the DAG with one node per component that contract() builds from their labels. The labels already run 0..k-1, so contract keeps them as block indices and the condensed node numbering is the component numbering.

Parameters ​
s ​

GraphSnapshot

A directed snapshot

options? ​

ArcOrderOption = {}

The neighbour order Tarjan tries arcs in, which fixes the component numbering

Returns ​

CondensationResult

The components and the condensed graph

Throws ​

Error when the snapshot is undirected

condensation.inputs ​

readonly inputs: readonly [] = []

condensation.name ​

readonly name: "condensation" = "condensation"

condensation.requiredOptions ​

readonly requiredOptions: readonly [] = []

condensation.result ​

readonly result: "partition" = "partition"

condensation.values ​

readonly values: readonly ["components.labels"]

condensation.weights ​

readonly weights: "never" = "never"

connectedComponents ​

readonly connectedComponents: object

connectedComponents.accelerator ​

readonly accelerator: "connectedComponents" = "connectedComponents"

connectedComponents.category ​

readonly category: "components" = "components"

connectedComponents.direction ​

readonly direction: "undirected" = "undirected"

connectedComponents.dispatch ​

readonly dispatch: "connectedComponents" = "connectedComponents"

connectedComponents.fn ​

readonly fn: (s) => LabelResult = connectedComponents

Connected components of an UNDIRECTED snapshot.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

Returns ​

LabelResult

The partition

connectedComponents.inputs ​

readonly inputs: readonly [] = []

connectedComponents.name ​

readonly name: "connectedComponents" = "connectedComponents"

connectedComponents.requiredOptions ​

readonly requiredOptions: readonly [] = []

connectedComponents.result ​

readonly result: "partition" = "partition"

connectedComponents.values ​

readonly values: readonly ["labels"]

connectedComponents.weights ​

readonly weights: "never" = "never"

degreeCentrality ​

readonly degreeCentrality: object

degreeCentrality.accelerator ​

readonly accelerator: null = null

degreeCentrality.category ​

readonly category: "centrality" = "centrality"

degreeCentrality.direction ​

readonly direction: "any" = "any"

degreeCentrality.dispatch ​

readonly dispatch: null = null

degreeCentrality.fn ​

readonly fn: (s, options) => F64 = degreeCentrality

Degree centrality: each node's number of distinct neighbours (in, out, or both on a directed snapshot), optionally divided by n - 1. Equals the legacy degreeCentrality on every graph it can hold, and on a multigraph equals it on the same graph with each pair's parallel edges merged.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

DegreeCentralityOptions = {}

Direction and normalisation

Returns ​

F64

One score per node index

degreeCentrality.inputs ​

readonly inputs: readonly [] = []

degreeCentrality.name ​

readonly name: "degreeCentrality" = "degreeCentrality"

degreeCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

degreeCentrality.result ​

readonly result: "node-scores" = "node-scores"

degreeCentrality.values ​

readonly values: readonly [""]

degreeCentrality.weights ​

readonly weights: "never" = "never"

degrees ​

readonly degrees: object

degrees.accelerator ​

readonly accelerator: null = null

degrees.category ​

readonly category: "centrality" = "centrality"

degrees.direction ​

readonly direction: "any" = "any"

degrees.dispatch ​

readonly dispatch: "degrees" = "degrees"

degrees.fn ​

readonly fn: (s) => DegreesResult = degrees

Each node's edges counted from the edge list: every logical edge once at its declared source (out) and once at its declared target (in), so a self-loop counts once in each half. The orientation is the one each edge was declared with, on an undirected snapshot too, so in plus out is the degree counted once -- where the snapshot's own degree views give an undirected node its whole degree as both halves. Parallel edges each count; merge them first to count a pair once.

Parameters ​
s ​

GraphSnapshot

The snapshot

Returns ​

DegreesResult

The two halves, one count per node index

degrees.inputs ​

readonly inputs: readonly [] = []

degrees.name ​

readonly name: "degrees" = "degrees"

degrees.requiredOptions ​

readonly requiredOptions: readonly [] = []

degrees.result ​

readonly result: "node-scores" = "node-scores"

degrees.values ​

readonly values: readonly ["inDegree", "outDegree"]

degrees.weights ​

readonly weights: "never" = "never"

depthFirstSearch ​

readonly depthFirstSearch: object

depthFirstSearch.accelerator ​

readonly accelerator: null = null

depthFirstSearch.category ​

readonly category: "traversal" = "traversal"

depthFirstSearch.direction ​

readonly direction: "any" = "any"

depthFirstSearch.dispatch ​

readonly dispatch: "depthFirstSearch" = "depthFirstSearch"

depthFirstSearch.fn ​

readonly fn: (g, startNode, options) => DfsResult = depthFirstSearch

Depth-first search over out-neighbours, trying them in row (ascending index) order unless options.arcOrder gives another. Takes any AdjacencyView, so s.reverse() walks in-neighbours.

Parameters ​
g ​

AdjacencyView

The adjacency to traverse

startNode ​

NodeRef

The node to start from: its index, or { id }

options? ​

DfsOptions = {}

Traversal options

Returns ​

DfsResult

The visit order, the DFS tree as a parent array, the tree depths and the visited count

depthFirstSearch.inputs ​

readonly inputs: readonly [AlgorithmInput]

depthFirstSearch.name ​

readonly name: "depthFirstSearch" = "depthFirstSearch"

depthFirstSearch.requiredOptions ​

readonly requiredOptions: readonly [] = []

depthFirstSearch.result ​

readonly result: "traversal" = "traversal"

depthFirstSearch.values ​

readonly values: readonly ["depth", "parent"]

depthFirstSearch.weights ​

readonly weights: "never" = "never"

dijkstra ​

readonly dijkstra: object

dijkstra.accelerator ​

readonly accelerator: "sssp" = "sssp"

dijkstra.category ​

readonly category: "shortest-path" = "shortest-path"

dijkstra.direction ​

readonly direction: "any" = "any"

dijkstra.dispatch ​

readonly dispatch: "sssp" = "sssp"

dijkstra.fn ​

readonly fn: (g, sourceNode, options) => SsspResult = dijkstra

Dijkstra over an adjacency view, with the predecessor recorded as the relaxing ARC so a parallel edge on the path is identified exactly.

Parameters ​
g ​

AdjacencyView

The adjacency to search

sourceNode ​

NodeRef

The node to start from: its index, or { id }

options? ​

SsspOptions = {}

Cutoff and per-arc weight override

Returns ​

SsspResult

The distances, the predecessor arcs, and the two path accessors

dijkstra.inputs ​

readonly inputs: readonly [AlgorithmInput]

dijkstra.name ​

readonly name: "dijkstra" = "dijkstra"

dijkstra.requiredOptions ​

readonly requiredOptions: readonly [] = []

dijkstra.result ​

readonly result: "shortest-paths" = "shortest-paths"

dijkstra.values ​

readonly values: readonly ["dist", "predArc"]

dijkstra.weights ​

readonly weights: "always" = "always"

directionOptimizedBfs ​

readonly directionOptimizedBfs: object

directionOptimizedBfs.accelerator ​

readonly accelerator: null = null

directionOptimizedBfs.category ​

readonly category: "traversal" = "traversal"

directionOptimizedBfs.direction ​

readonly direction: "any" = "any"

directionOptimizedBfs.dispatch ​

readonly dispatch: null = null

directionOptimizedBfs.fn ​

readonly fn: (s, sourceNode, options) => BfsResult = directionOptimizedBfs

Direction-optimising breadth-first search (Beamer, Asanovic and Patterson, SC'12): a top-down step expands the frontier's out-arcs, a bottom-up step has every unvisited node look for a frontier node among its in-neighbours over s.reverse(), and the search switches between the two by the arcs each would read. Both steps give a node the LOWEST-index frontier node that reaches it as its parent, so the result does not depend on which steps ran: depth equals breadthFirstSearch's, and order lists the visited nodes level by level, ascending within a level.

Parameters ​
s ​

GraphSnapshot

The snapshot to traverse

sourceNode ​

NodeRef

The node to start from: its index, or { id }

options? ​

DirectionOptimizedBfsOptions = {}

The switching thresholds

Returns ​

BfsResult

The visit order, the parent array, the depth array and the visited count

directionOptimizedBfs.inputs ​

readonly inputs: readonly [AlgorithmInput]

directionOptimizedBfs.name ​

readonly name: "directionOptimizedBfs" = "directionOptimizedBfs"

directionOptimizedBfs.requiredOptions ​

readonly requiredOptions: readonly [] = []

directionOptimizedBfs.result ​

readonly result: "traversal" = "traversal"

directionOptimizedBfs.values ​

readonly values: readonly ["depth", "parent"]

directionOptimizedBfs.weights ​

readonly weights: "never" = "never"

edgeBetweennessCentrality ​

readonly edgeBetweennessCentrality: object

edgeBetweennessCentrality.accelerator ​

readonly accelerator: "edgeBetweennessCentrality" = "edgeBetweennessCentrality"

edgeBetweennessCentrality.category ​

readonly category: "centrality" = "centrality"

edgeBetweennessCentrality.direction ​

readonly direction: "any" = "any"

edgeBetweennessCentrality.dispatch ​

readonly dispatch: "edgeBetweennessCentrality" = "edgeBetweennessCentrality"

edgeBetweennessCentrality.fn ​

readonly fn: (s, options) => EdgeScoresResult = edgeBetweennessCentrality

Edge betweenness centrality by Brandes' algorithm, one score per logical edge.

On a directed snapshot an edge's score equals the legacy edgeBetweennessCentrality value keyed "source-target". On an undirected one it is the number of pairs whose shortest paths cross the edge in either direction, which is the SUM of the two values the legacy function reports under "u-v" and "v-u" (each of those holds half), and is the score the WebGPU accelerator returns.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

EdgeBetweennessOptions = {}

Normalisation, sampling and the alive-edge mask

Returns ​

EdgeScoresResult

One score per logical edge

Throws ​

RangeError for a bad sources or k, or an alive mask shorter than the edge count

edgeBetweennessCentrality.inputs ​

readonly inputs: readonly [] = []

edgeBetweennessCentrality.name ​

readonly name: "edgeBetweennessCentrality" = "edgeBetweennessCentrality"

edgeBetweennessCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

edgeBetweennessCentrality.result ​

readonly result: "edge-scores" = "edge-scores"

edgeBetweennessCentrality.values ​

readonly values: readonly ["scores"]

edgeBetweennessCentrality.weights ​

readonly weights: "never" = "never"

eigenvectorCentrality ​

readonly eigenvectorCentrality: object

eigenvectorCentrality.accelerator ​

readonly accelerator: "eigenvectorCentrality" = "eigenvectorCentrality"

eigenvectorCentrality.category ​

readonly category: "centrality" = "centrality"

eigenvectorCentrality.direction ​

readonly direction: "any" = "any"

eigenvectorCentrality.dispatch ​

readonly dispatch: "eigenvectorCentrality" = "eigenvectorCentrality"

eigenvectorCentrality.fn ​

readonly fn: (s, o) => EigenvectorResult = eigenvectorCentrality

Eigenvector centrality by power iteration on (A + I), as networkx does: the identity shift leaves the eigenvectors alone and makes the largest eigenvalue the only one of largest magnitude, so a bipartite or periodic graph converges instead of oscillating. Each node's neighbours are counted once however many parallel edges join them, as in the legacy neighbour sets. When the relation has no cycle (no arcs, or a directed acyclic graph) its matrix is nilpotent and every score is exactly 0.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

EigenvectorOptions = {}

Algorithm options

Returns ​

EigenvectorResult

The scores, the iteration count and the convergence flag

Throws ​

When maxIterations passes do not meet the tolerance

eigenvectorCentrality.inputs ​

readonly inputs: readonly [] = []

eigenvectorCentrality.name ​

readonly name: "eigenvectorCentrality" = "eigenvectorCentrality"

eigenvectorCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

eigenvectorCentrality.result ​

readonly result: "node-scores" = "node-scores"

eigenvectorCentrality.values ​

readonly values: readonly ["scores"]

eigenvectorCentrality.weights ​

readonly weights: "never" = "never"

evaluateAdamicAdar ​

readonly evaluateAdamicAdar: object

evaluateAdamicAdar.accelerator ​

readonly accelerator: null = null

evaluateAdamicAdar.category ​

readonly category: "link-prediction" = "link-prediction"

evaluateAdamicAdar.direction ​

readonly direction: "any" = "any"

evaluateAdamicAdar.dispatch ​

readonly dispatch: null = null

evaluateAdamicAdar.fn ​

readonly fn: (s, edges, nonEdges, o) => LinkPredictionMetrics = evaluateAdamicAdar

Ranking metrics of the Adamic-Adar score on held-out edges against non-edges.

Parameters ​
s ​

GraphSnapshot

The training snapshot

edges ​

NodePairs

The held-out edges

nonEdges ​

NodePairs

The non-edges

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

LinkPredictionMetrics

The metrics

evaluateAdamicAdar.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

evaluateAdamicAdar.name ​

readonly name: "evaluateAdamicAdar" = "evaluateAdamicAdar"

evaluateAdamicAdar.requiredOptions ​

readonly requiredOptions: readonly [] = []

evaluateAdamicAdar.result ​

readonly result: "metrics" = "metrics"

evaluateAdamicAdar.values ​

readonly values: readonly [] = []

evaluateAdamicAdar.weights ​

readonly weights: "never" = "never"

evaluateCommonNeighbors ​

readonly evaluateCommonNeighbors: object

evaluateCommonNeighbors.accelerator ​

readonly accelerator: null = null

evaluateCommonNeighbors.category ​

readonly category: "link-prediction" = "link-prediction"

evaluateCommonNeighbors.direction ​

readonly direction: "any" = "any"

evaluateCommonNeighbors.dispatch ​

readonly dispatch: null = null

evaluateCommonNeighbors.fn ​

readonly fn: (s, edges, nonEdges, o) => LinkPredictionMetrics = evaluateCommonNeighbors

Ranking metrics of the common-neighbour score on held-out edges against non-edges.

Parameters ​
s ​

GraphSnapshot

The training snapshot

edges ​

NodePairs

The held-out edges

nonEdges ​

NodePairs

The non-edges

o? ​

CommonNeighborsOptions = {}

Options

Returns ​

LinkPredictionMetrics

The metrics

evaluateCommonNeighbors.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

evaluateCommonNeighbors.name ​

readonly name: "evaluateCommonNeighbors" = "evaluateCommonNeighbors"

evaluateCommonNeighbors.requiredOptions ​

readonly requiredOptions: readonly [] = []

evaluateCommonNeighbors.result ​

readonly result: "metrics" = "metrics"

evaluateCommonNeighbors.values ​

readonly values: readonly [] = []

evaluateCommonNeighbors.weights ​

readonly weights: "never" = "never"

findAllIsomorphisms ​

readonly findAllIsomorphisms: object

findAllIsomorphisms.accelerator ​

readonly accelerator: null = null

findAllIsomorphisms.category ​

readonly category: "structure" = "structure"

findAllIsomorphisms.direction ​

readonly direction: "any" = "any"

findAllIsomorphisms.dispatch ​

readonly dispatch: null = null

findAllIsomorphisms.fn ​

readonly fn: (s1, s2, options) => U32[] = findAllIsomorphisms

Every isomorphism from s1 to s2, with the neighbourhood rules of isGraphIsomorphic. Two empty graphs have one, the empty mapping.

Parameters ​
s1 ​

GraphSnapshot

The first graph

s2 ​

GraphSnapshot

The second graph

options? ​

IsomorphismOptions = {}

Node and edge match predicates

Returns ​

U32[]

One array per isomorphism: the image in s2 of every node of s1

findAllIsomorphisms.inputs ​

readonly inputs: readonly [{ kind: "graph"; name: "other"; }]

findAllIsomorphisms.name ​

readonly name: "findAllIsomorphisms" = "findAllIsomorphisms"

findAllIsomorphisms.requiredOptions ​

readonly requiredOptions: readonly [] = []

findAllIsomorphisms.result ​

readonly result: "isomorphisms" = "isomorphisms"

findAllIsomorphisms.values ​

readonly values: readonly [] = []

findAllIsomorphisms.weights ​

readonly weights: "never" = "never"

getTopAdamicAdarCandidatesForNode ​

readonly getTopAdamicAdarCandidatesForNode: object

getTopAdamicAdarCandidatesForNode.accelerator ​

readonly accelerator: null = null

getTopAdamicAdarCandidatesForNode.category ​

readonly category: "link-prediction" = "link-prediction"

getTopAdamicAdarCandidatesForNode.direction ​

readonly direction: "any" = "any"

getTopAdamicAdarCandidatesForNode.dispatch ​

readonly dispatch: null = null

getTopAdamicAdarCandidatesForNode.fn ​

readonly fn: (s, uNode, o) => LinkPredictionResult = getTopAdamicAdarCandidatesForNode

One node's best Adamic-Adar candidates, ranked.

Parameters ​
s ​

GraphSnapshot

The snapshot

uNode ​

NodeRef

The node: its index, or { id }

o? ​

CandidateOptions = {}

Options

Returns ​

LinkPredictionResult

(u, v) pairs with a positive score, highest first

getTopAdamicAdarCandidatesForNode.inputs ​

readonly inputs: readonly [AlgorithmInput]

getTopAdamicAdarCandidatesForNode.name ​

readonly name: "getTopAdamicAdarCandidatesForNode" = "getTopAdamicAdarCandidatesForNode"

getTopAdamicAdarCandidatesForNode.requiredOptions ​

readonly requiredOptions: readonly [] = []

getTopAdamicAdarCandidatesForNode.result ​

readonly result: "link-predictions" = "link-predictions"

getTopAdamicAdarCandidatesForNode.values ​

readonly values: readonly [] = []

getTopAdamicAdarCandidatesForNode.weights ​

readonly weights: "never" = "never"

getTopCandidatesForNode ​

readonly getTopCandidatesForNode: object

getTopCandidatesForNode.accelerator ​

readonly accelerator: null = null

getTopCandidatesForNode.category ​

readonly category: "link-prediction" = "link-prediction"

getTopCandidatesForNode.direction ​

readonly direction: "any" = "any"

getTopCandidatesForNode.dispatch ​

readonly dispatch: null = null

getTopCandidatesForNode.fn ​

readonly fn: (s, uNode, o) => LinkPredictionResult = getTopCandidatesForNode

One node's best common-neighbour candidates, ranked.

Parameters ​
s ​

GraphSnapshot

The snapshot

uNode ​

NodeRef

The node: its index, or { id }

o? ​

CandidateOptions = {}

Options

Returns ​

LinkPredictionResult

(u, v) pairs with a positive score, highest first

getTopCandidatesForNode.inputs ​

readonly inputs: readonly [AlgorithmInput]

getTopCandidatesForNode.name ​

readonly name: "getTopCandidatesForNode" = "getTopCandidatesForNode"

getTopCandidatesForNode.requiredOptions ​

readonly requiredOptions: readonly [] = []

getTopCandidatesForNode.result ​

readonly result: "link-predictions" = "link-predictions"

getTopCandidatesForNode.values ​

readonly values: readonly [] = []

getTopCandidatesForNode.weights ​

readonly weights: "never" = "never"

girvanNewman ​

readonly girvanNewman: object

girvanNewman.accelerator ​

readonly accelerator: null = null

girvanNewman.category ​

readonly category: "community" = "community"

girvanNewman.direction ​

readonly direction: "undirected" = "undirected"

girvanNewman.dispatch ​

readonly dispatch: "girvanNewman" = "girvanNewman"

girvanNewman.fn ​

readonly fn: (s, options) => GirvanNewmanResult = girvanNewman

Girvan-Newman divisive community detection (PNAS 99:7821, 2002) over an undirected snapshot: repeatedly delete every edge whose betweenness is the maximum (within 1e-10), recording the connected components after each round as one level of a dendrogram.

Edges are deleted by clearing bits of an alive mask over logical edges that the edge betweenness reads, so no graph is rebuilt. Betweenness is unweighted, as in the legacy function; a pair of nodes joined by parallel edges is one neighbour relation whose share goes to the first alive parallel, so the parallels are deleted one round at a time. Modularity reads the edge weights, the exact f64 ones when the snapshot keeps them, with graph-format's weightedDegree() rule (a self-loop counts twice); on a graph without self-loops it equals the legacy function's.

The run stops when no edge is left, after maxIterations rounds, when a level has maxCommunities communities of at least minCommunitySize nodes, or when that count reaches the node count. Every level is returned whole: the legacy function drops communities below minCommunitySize from the lists it returns, which a caller does with levels[i] and a size count.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

options? ​

GirvanNewmanOptions = {}

Stopping rules

Returns ​

GirvanNewmanResult

The levels and their modularity

Throws ​

Error on a directed snapshot

girvanNewman.inputs ​

readonly inputs: readonly [] = []

girvanNewman.name ​

readonly name: "girvanNewman" = "girvanNewman"

girvanNewman.requiredOptions ​

readonly requiredOptions: readonly [] = []

girvanNewman.result ​

readonly result: "hierarchy" = "hierarchy"

girvanNewman.values ​

readonly values: readonly [] = []

girvanNewman.weights ​

readonly weights: "always" = "always"

greedyBipartiteMatching ​

readonly greedyBipartiteMatching: object

greedyBipartiteMatching.accelerator ​

readonly accelerator: null = null

greedyBipartiteMatching.category ​

readonly category: "matching" = "matching"

greedyBipartiteMatching.direction ​

readonly direction: "any" = "any"

greedyBipartiteMatching.dispatch ​

readonly dispatch: null = null

greedyBipartiteMatching.fn ​

readonly fn: (s, options) => BipartiteMatchingResult = greedyBipartiteMatching

Greedy maximal bipartite matching: every left node in index order takes its first unmatched right neighbour in row order (the lowest index; out-arcs before in-arcs). The size depends on those orders, so it can differ from the legacy function, which visits left nodes in its colouring BFS order and neighbours in insertion order; it is at least half the maximum.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

BipartiteMatchingOptions = {}

The two sides, and which arcs to follow on a directed snapshot

Returns ​

BipartiteMatchingResult

The partner of every matched left node and the number of pairs

Throws ​

Error when the sides are inferred and the graph is not bipartite

greedyBipartiteMatching.inputs ​

readonly inputs: readonly [] = []

greedyBipartiteMatching.name ​

readonly name: "greedyBipartiteMatching" = "greedyBipartiteMatching"

greedyBipartiteMatching.requiredOptions ​

readonly requiredOptions: readonly [] = []

greedyBipartiteMatching.result ​

readonly result: "matching" = "matching"

greedyBipartiteMatching.values ​

readonly values: readonly ["matching"]

greedyBipartiteMatching.weights ​

readonly weights: "never" = "never"

grsbm ​

readonly grsbm: object

grsbm.accelerator ​

readonly accelerator: null = null

grsbm.category ​

readonly category: "community" = "community"

grsbm.direction ​

readonly direction: "any" = "any"

grsbm.dispatch ​

readonly dispatch: null = null

grsbm.fn ​

readonly fn: (s, options) => GrsbmResult = grsbm

GRSBM over a snapshot: recursive spectral bisection. Each cluster's Laplacian (over the arcs between its members, self-loops left out) gives an approximate Fiedler vector; members are sorted by it and cut at the point between 20% and 80% that maximises modularity; the split is kept only when it raises the modularity of the whole partition (every other cluster held as it is). The change is the two halves' community terms minus the cluster's, so scoring a cut costs the arcs of the cluster alone. Clusters are split breadth first. The cut and the modularity arithmetic are the legacy grsbm's; the acceptance rule is not (legacy compared the two halves' terms alone with the parent split's, and kept a split that lowered that by up to 0.01, issue #960), nor is the bisection vector, because legacy's iteration converged to the eigenvector of the Laplacian's largest eigenvalue rather than the Fiedler vector. The port draws from its own generator instead of replacing Math.random.

Modularity uses weightedDegree() (a self-loop counts twice) against totalWeight(), or degree() against the edge count when unweighted. A self-loop follows the standard convention (left out of the Laplacian, twice in the degree), so on a graph with self-loops the result differs from legacy's, which scores the whole graph as one community above 0. On a directed graph the unweighted path keeps legacy's halving of internal arcs; the weighted path does not, so there the whole graph as one community scores 0. Weights must be finite and non-negative (RangeError).

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

GrsbmOptions = {}

GrsbmOptions

Returns ​

GrsbmResult

The leaf partition and the hierarchy

grsbm.inputs ​

readonly inputs: readonly [] = []

grsbm.name ​

readonly name: "grsbm" = "grsbm"

grsbm.requiredOptions ​

readonly requiredOptions: readonly [] = []

grsbm.result ​

readonly result: "partition" = "partition"

grsbm.values ​

readonly values: readonly ["labels"]

grsbm.weights ​

readonly weights: "by-default" = "by-default"

hasCycle ​

readonly hasCycle: object

hasCycle.accelerator ​

readonly accelerator: null = null

hasCycle.category ​

readonly category: "structure" = "structure"

hasCycle.direction ​

readonly direction: "any" = "any"

hasCycle.dispatch ​

readonly dispatch: null = null

hasCycle.fn ​

readonly fn: (g) => boolean = hasCycle

Whether the graph has a cycle. Directed: a DFS back arc. Undirected: an edge closing a loop in a union-find forest. A self-loop is a cycle; a parallel pair is not -- the graph is read as simple, the adjacent-skip idiom of graph-format design section 3.5.

Parameters ​
g ​

AdjacencyView

The adjacency to test

Returns ​

boolean

True when a cycle exists

hasCycle.inputs ​

readonly inputs: readonly [] = []

hasCycle.name ​

readonly name: "hasCycle" = "hasCycle"

hasCycle.requiredOptions ​

readonly requiredOptions: readonly [] = []

hasCycle.result ​

readonly result: "boolean" = "boolean"

hasCycle.values ​

readonly values: readonly [] = []

hasCycle.weights ​

readonly weights: "never" = "never"

hierarchicalClustering ​

readonly hierarchicalClustering: object

hierarchicalClustering.accelerator ​

readonly accelerator: null = null

hierarchicalClustering.category ​

readonly category: "community" = "community"

hierarchicalClustering.direction ​

readonly direction: "any" = "any"

hierarchicalClustering.dispatch ​

readonly dispatch: null = null

hierarchicalClustering.fn ​

readonly fn: (s, options) => HierarchicalResult = hierarchicalClustering

Agglomerative hierarchical clustering over hop distances, the index-based port of the legacy hierarchicalClustering: every node starts as its own cluster and the closest pair is merged until one cluster remains or no remaining pair is linked by a path.

The distance between two nodes is the BFS hop count over out-arcs (weights are ignored, as the legacy function ignores them); an unreachable pair has none and is left out of every linkage. The distance between two clusters over the member pairs that have one is their minimum (single), maximum (complete), mean (average), or mean times |A| |B| / (|A| + |B|) (ward). A pair with no connected member pair is never merged. On a directed snapshot the distance is taken in one direction, and which one follows the legacy function exactly, as do the tie-breaks: the merges, their order and their distances equal the legacy function's.

One difference in what the result offers: cut descends into every root of a disconnected snapshot, where the legacy clusters map lists all nodes as one cluster at every height (its forest node has no children, so its cut never splits it).

O(n^2) memory for the distance aggregates and O(n^3) time for the pair search; the legacy function is the same order with Map and Set per step.

Parameters ​
s ​

AdjacencyView

Any snapshot or adjacency view

options? ​

HierarchicalOptions = {}

The linkage

Returns ​

HierarchicalResult

The dendrogram

hierarchicalClustering.inputs ​

readonly inputs: readonly [] = []

hierarchicalClustering.name ​

readonly name: "hierarchicalClustering" = "hierarchicalClustering"

hierarchicalClustering.requiredOptions ​

readonly requiredOptions: readonly [] = []

hierarchicalClustering.result ​

readonly result: "hierarchy" = "hierarchy"

hierarchicalClustering.values ​

readonly values: readonly [] = []

hierarchicalClustering.weights ​

readonly weights: "never" = "never"

hits ​

readonly hits: object

hits.accelerator ​

readonly accelerator: "hits" = "hits"

hits.category ​

readonly category: "centrality" = "centrality"

hits.direction ​

readonly direction: "any" = "any"

hits.dispatch ​

readonly dispatch: "hits" = "hits"

hits.fn ​

readonly fn: (s, o) => HitsResult = hits

HITS by alternating power iteration: an authority sums the hub scores of the nodes pointing at it, a hub sums the authority scores of the nodes it points at, and both vectors are L2-normalized every round. On an undirected snapshot the two adjacencies are the same array, so the hubs and the authorities coincide.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

HitsOptions = {}

Algorithm options

Returns ​

HitsResult

The two score vectors, the iteration count and the convergence flag

hits.inputs ​

readonly inputs: readonly [] = []

hits.name ​

readonly name: "hits" = "hits"

hits.requiredOptions ​

readonly requiredOptions: readonly [] = []

hits.result ​

readonly result: "node-scores" = "node-scores"

hits.values ​

readonly values: readonly ["hubs", "authorities"]

hits.weights ​

readonly weights: "on-request" = "on-request"

isBipartite ​

readonly isBipartite: object

isBipartite.accelerator ​

readonly accelerator: null = null

isBipartite.category ​

readonly category: "structure" = "structure"

isBipartite.direction ​

readonly direction: "any" = "any"

isBipartite.dispatch ​

readonly dispatch: null = null

isBipartite.fn ​

readonly fn: (s, options) => BipartiteResult = isBipartite

Two-colour the graph by BFS, one BFS per component in index order. A self-loop makes a graph non-bipartite; parallel arcs change nothing. Arc direction plays no part in bipartiteness, so on a directed snapshot every node is coloured against its in-neighbours (over s.reverse()) as well as its out-neighbours. Following out-arcs only -- as the legacy bipartitePartition does -- makes the answer depend on node order: with the single arc a -> b, a walk that starts at b never meets a, colours it as a new root and then finds the arc inside one side. options.arcs: "out" gives that legacy answer.

Parameters ​
s ​

GraphSnapshot

The snapshot to test

options? ​

BipartiteOptions = {}

Which arcs to follow on a directed snapshot

Returns ​

BipartiteResult

Whether the graph is bipartite and, when it is, its two sides

isBipartite.inputs ​

readonly inputs: readonly [] = []

isBipartite.name ​

readonly name: "isBipartite" = "isBipartite"

isBipartite.requiredOptions ​

readonly requiredOptions: readonly [] = []

isBipartite.result ​

readonly result: "bipartition" = "bipartition"

isBipartite.values ​

readonly values: readonly [] = []

isBipartite.weights ​

readonly weights: "never" = "never"

isGraphIsomorphic ​

readonly isGraphIsomorphic: object

isGraphIsomorphic.accelerator ​

readonly accelerator: null = null

isGraphIsomorphic.category ​

readonly category: "structure" = "structure"

isGraphIsomorphic.direction ​

readonly direction: "any" = "any"

isGraphIsomorphic.dispatch ​

readonly dispatch: null = null

isGraphIsomorphic.fn ​

readonly fn: (s1, s2, options) => IsomorphismResult = isGraphIsomorphic

Whether two snapshots are isomorphic, by a VF2-style search. Neighbourhoods are simple-graph: parallel arcs count once and a self-loop maps only to a self-loop. On a directed snapshot both arc directions are preserved.

Parameters ​
s1 ​

GraphSnapshot

The first graph

s2 ​

GraphSnapshot

The second graph

options? ​

IsomorphismOptions = {}

Node and edge match predicates

Returns ​

IsomorphismResult

Whether an isomorphism exists and, when it does, the first one found

isGraphIsomorphic.inputs ​

readonly inputs: readonly [{ kind: "graph"; name: "other"; }]

isGraphIsomorphic.name ​

readonly name: "isGraphIsomorphic" = "isGraphIsomorphic"

isGraphIsomorphic.requiredOptions ​

readonly requiredOptions: readonly [] = []

isGraphIsomorphic.result ​

readonly result: "isomorphism" = "isomorphism"

isGraphIsomorphic.values ​

readonly values: readonly [] = []

isGraphIsomorphic.weights ​

readonly weights: "never" = "never"

kargerMinCut ​

readonly kargerMinCut: object

kargerMinCut.accelerator ​

readonly accelerator: null = null

kargerMinCut.category ​

readonly category: "flow" = "flow"

kargerMinCut.direction ​

readonly direction: "any" = "any"

kargerMinCut.dispatch ​

readonly dispatch: "kargerMinCut" = "kargerMinCut"

kargerMinCut.fn ​

readonly fn: (s, options) => MinCutResult = kargerMinCut

Global minimum cut by Karger's randomised contraction, reading every edge as undirected. Each trial unions the endpoints of the edges in a seeded random order (an IntUnionFind, no graph is contracted) until two groups remain, so every edge is equally likely to be contracted next whatever its weight; the trial's cut is the weight of the edges between the two groups. A graph with more than two components gives a cut of 0 with node 0's component on side. O(m alpha(n)) per trial.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

KargerOptions = {}

Trials, seed and weight override

Returns ​

MinCutResult

The lightest cut found; with fewer than two nodes the value is 0 and side is empty

Throws ​

RangeError when randomSeed is not an integer or iterations is not a positive integer

kargerMinCut.inputs ​

readonly inputs: readonly [] = []

kargerMinCut.name ​

readonly name: "kargerMinCut" = "kargerMinCut"

kargerMinCut.requiredOptions ​

readonly requiredOptions: readonly [] = []

kargerMinCut.result ​

readonly result: "cut" = "cut"

kargerMinCut.values ​

readonly values: readonly [] = []

kargerMinCut.weights ​

readonly weights: "always" = "always"

katzCentrality ​

readonly katzCentrality: object

katzCentrality.accelerator ​

readonly accelerator: "katzCentrality" = "katzCentrality"

katzCentrality.category ​

readonly category: "centrality" = "centrality"

katzCentrality.direction ​

readonly direction: "any" = "any"

katzCentrality.dispatch ​

readonly dispatch: "katzCentrality" = "katzCentrality"

katzCentrality.fn ​

readonly fn: (s, o) => KatzResult = katzCentrality

Katz centrality by power iteration over incoming arcs: x[v] = alpha * sum(x[u] for u -> v) + beta.

reverse() supplies the in-arcs, and is the forward adjacency itself on an undirected snapshot, so one loop serves both directions exactly as the legacy function's in-neighbours / neighbours split does.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

KatzOptions = {}

Algorithm options

Returns ​

KatzResult

The scores, the iteration count and the convergence flag

katzCentrality.inputs ​

readonly inputs: readonly [] = []

katzCentrality.name ​

readonly name: "katzCentrality" = "katzCentrality"

katzCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

katzCentrality.result ​

readonly result: "node-scores" = "node-scores"

katzCentrality.values ​

readonly values: readonly ["scores"]

katzCentrality.weights ​

readonly weights: "on-request" = "on-request"

kCoreDecomposition ​

readonly kCoreDecomposition: object

kCoreDecomposition.accelerator ​

readonly accelerator: "kCoreDecomposition" = "kCoreDecomposition"

kCoreDecomposition.category ​

readonly category: "components" = "components"

kCoreDecomposition.direction ​

readonly direction: "undirected" = "undirected"

kCoreDecomposition.dispatch ​

readonly dispatch: "kCoreDecomposition" = "kCoreDecomposition"

kCoreDecomposition.fn ​

readonly fn: (s) => CorenessResult = kCoreDecomposition

Core number of every node, by the Batagelj-Zaversnik bucket peel: O(nodes + arcs), no priority queue and no per-node object.

Core numbers are defined on a SIMPLE graph, so a parallel arc counts once (parallels are adjacent within a row, invariant I4) and a self-loop does not count at all, as NetworkX defines it. The legacy implementation's adjacency-of-sets counts a self-loop as one neighbour, so there a node with a self-loop can sit higher, and so can a node without one whose core leaned on self-looped neighbours. The result equals the legacy function's on the graph with every self-loop removed.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

Returns ​

CorenessResult

The core numbers, the largest of them, and the lazy grouping

kCoreDecomposition.inputs ​

readonly inputs: readonly [] = []

kCoreDecomposition.name ​

readonly name: "kCoreDecomposition" = "kCoreDecomposition"

kCoreDecomposition.requiredOptions ​

readonly requiredOptions: readonly [] = []

kCoreDecomposition.result ​

readonly result: "node-scores" = "node-scores"

kCoreDecomposition.values ​

readonly values: readonly ["coreness"]

kCoreDecomposition.weights ​

readonly weights: "never" = "never"

kruskalMST ​

readonly kruskalMST: object

kruskalMST.accelerator ​

readonly accelerator: "minimumSpanningTree" = "minimumSpanningTree"

kruskalMST.category ​

readonly category: "spanning-tree" = "spanning-tree"

kruskalMST.direction ​

readonly direction: "any" = "any"

kruskalMST.dispatch ​

readonly dispatch: "minimumSpanningTree" = "minimumSpanningTree"

kruskalMST.fn ​

readonly fn: (s, o) => MstResult = kruskalMST

Kruskal's minimum spanning forest over logical edges.

The sort is a comparator over an f64 key array, tie-broken by edge index, rather than the design's radix sort on the f32 bit pattern (plan departure DEP-8A-D): the tie-break makes it stable by construction and it has to serve both the f32 arc array and an f64 override.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

MstOptions = {}

The optional per-arc weight override

Returns ​

MstResult

The accepted edge indices and their total weight

kruskalMST.inputs ​

readonly inputs: readonly [] = []

kruskalMST.name ​

readonly name: "kruskalMST" = "kruskalMST"

kruskalMST.requiredOptions ​

readonly requiredOptions: readonly [] = []

kruskalMST.result ​

readonly result: "spanning-tree" = "spanning-tree"

kruskalMST.values ​

readonly values: readonly [] = []

kruskalMST.weights ​

readonly weights: "always" = "always"

labelPropagation ​

readonly labelPropagation: object

labelPropagation.accelerator ​

readonly accelerator: "labelPropagation" = "labelPropagation"

labelPropagation.category ​

readonly category: "community" = "community"

labelPropagation.direction ​

readonly direction: "any" = "any"

labelPropagation.dispatch ​

readonly dispatch: "labelPropagation" = "labelPropagation"

labelPropagation.fn ​

readonly fn: (s, options) => LabelPropagationResult = labelPropagation

Community detection by fast label propagation (FLPA; Traag and Subelj, Sci. Rep. 13:2701, 2023, Algorithm 3), the queue-driven form of Raghavan, Albert and Kumara's asynchronous label propagation.

Every node starts in its own community. Nodes are visited from a queue that starts as a seeded shuffle of all of them; a visited node adopts the label with the largest summed arc weight among its neighbours, drawing uniformly at random among tied labels (its current label included, with no priority). When its label changes, every neighbour holding a different label is queued again. The run ends when the queue empties -- then every node's label is dominant among its neighbours and converged is true -- or after maxIterations * nodeCount node visits.

Conventions: self-loops are skipped; parallel arcs are summed; on a directed snapshot a node's neighbours are its out-arcs AND its in-arcs, so a reciprocal pair counts twice. With weighted: false each distinct neighbour votes once. A negative, NaN or infinite weight throws. Votes use the exact f64 weights when the snapshot keeps them (as toSnapshot does for a legacy graph whose weights are not all f32-exact), so a weight rounded in the f32 arc array never decides a vote.

One randomSeed gives one result, bit for bit. The partitions differ from the legacy labelPropagation for the same seed: the random stream and the stop rule are different (design design/algorithms/label-propagation-indexed-port-design.md, section 3).

Parameters ​
s ​

GraphSnapshot

Any snapshot

options? ​

LabelPropagationOptions = {}

Work cap, seed and weighting

Returns ​

LabelPropagationResult

The partition, the full-sweep equivalents run, and whether the work queue emptied

labelPropagation.inputs ​

readonly inputs: readonly [] = []

labelPropagation.name ​

readonly name: "labelPropagation" = "labelPropagation"

labelPropagation.requiredOptions ​

readonly requiredOptions: readonly [] = []

labelPropagation.result ​

readonly result: "partition" = "partition"

labelPropagation.values ​

readonly values: readonly ["labels"]

labelPropagation.weights ​

readonly weights: "by-default" = "by-default"

labelPropagationSemiSupervised ​

readonly labelPropagationSemiSupervised: object

labelPropagationSemiSupervised.accelerator ​

readonly accelerator: null = null

labelPropagationSemiSupervised.category ​

readonly category: "community" = "community"

labelPropagationSemiSupervised.direction ​

readonly direction: "any" = "any"

labelPropagationSemiSupervised.dispatch ​

readonly dispatch: null = null

labelPropagationSemiSupervised.fn ​

readonly fn: (s, seeds, options) => LabelPropagationResult = labelPropagationSemiSupervised

Semi-supervised label propagation: the FLPA kernel of labelPropagation with some nodes held at a given label (the initial / fixed inputs of igraph's community_label_propagation).

A seeded node keeps its label for the whole run and is never visited. Every other node starts UNLABELED, as a negative initial value means in igraph: it casts no vote, and on a visit it takes the label with the largest summed vote among its labeled neighbours, drawing uniformly among tied labels (its current one included), or stays unlabeled while it has none. So seed labels spread outward from the seeds, and every node joined to a seed by a path of voting arcs (any arc but a self-loop, with a positive weight when weighted) ends with some seed's label once the run converges. Seeds that share a label share one community from the start, and seeds with different labels are never merged, so in the result two seeds carry the same label exactly when their seed labels are equal.

Nodes no seed label reached -- a component with no seed, or a node cut off by the work cap -- end as igraph labels them: each connected group of them (joined by voting arcs) becomes a community of its own, so every node gets a label and the result is an ordinary partition. To tell those groups from the spread labels, compare labels[u] with the labels of the seed nodes. With no seed at all the result is one community per connected component.

The result is renumbered to 0..count-1 in first-seen node order like every other partition here, so a seed label's VALUE is not kept: read a seed's community through labels[seedNode].

converged is true when the work queue emptied, or when maxIterations is 0 and the starting labels already are dominant: no unseeded node has a labeled neighbour whose label outvotes its own (an unlabeled node next to a labeled one is not settled). Seeded nodes are not held to that.

Parameters ​
s ​

GraphSnapshot

Any snapshot

seeds ​

U32

One entry per node: its fixed label, any value but INVALID_INDEX, or INVALID_INDEX for a node free to move

options? ​

LabelPropagationOptions = {}

Work cap, seed of the visit order and weighting

Returns ​

LabelPropagationResult

The partition, the full-sweep equivalents run, and whether the work queue emptied

Throws ​

RangeError when seeds is not one entry per node, or for a bad option or weight

labelPropagationSemiSupervised.inputs ​

readonly inputs: readonly [{ kind: "seed-labels"; name: "seeds"; }]

labelPropagationSemiSupervised.name ​

readonly name: "labelPropagationSemiSupervised" = "labelPropagationSemiSupervised"

labelPropagationSemiSupervised.requiredOptions ​

readonly requiredOptions: readonly [] = []

labelPropagationSemiSupervised.result ​

readonly result: "partition" = "partition"

labelPropagationSemiSupervised.values ​

readonly values: readonly ["labels"]

labelPropagationSemiSupervised.weights ​

readonly weights: "by-default" = "by-default"

labelPropagationSynchronous ​

readonly labelPropagationSynchronous: object

labelPropagationSynchronous.accelerator ​

readonly accelerator: "labelPropagation" = "labelPropagation"

labelPropagationSynchronous.category ​

readonly category: "community" = "community"

labelPropagationSynchronous.direction ​

readonly direction: "any" = "any"

labelPropagationSynchronous.dispatch ​

readonly dispatch: "labelPropagationSynchronous" = "labelPropagationSynchronous"

labelPropagationSynchronous.fn ​

readonly fn: (s, options) => LabelPropagationResult = labelPropagationSynchronous

Label propagation in synchronous passes: every node reads its neighbours' labels from the previous pass, and all nodes move at once. Deterministic, with no random stream.

A node keeps its label when that label is dominant among its neighbours; otherwise it takes, of the labels with the largest summed vote, the one of lowest PRIORITY. A label's priority is a fixed scramble of its value (the murmur3 32-bit finalizer, a one-to-one map, so no two labels share a priority). Ranking labels by their raw value instead ties the outcome to the node numbering: on a path or a cycle numbered in order every interior node is tied between its two neighbours, the lowest label wins every tie, and it spreads one node per two passes -- 1,998 passes to settle a 1,000-node path, into a single community. Under the scrambled priority the winners of those ties are spread along the chain, so a path or a cycle settles in a few passes into short runs of nodes, as labelPropagation does, and a star or a clique still ends as one community.

Synchronous updates alone make two neighbours trade labels for ever (on a single edge a-b, a takes b's label while b takes a's), so passes alternate a swap guard: an even pass (the first is pass 0) lets a node move only to a label of higher priority, an odd pass only to one of lower priority (the up/down rule of cuGraph's Louvain move phase). The run stops after two passes in a row with no move, one up and one down -- then every node's label is dominant and converged is true -- or after maxIterations passes.

The guard stops the single-edge swap but not every cycle: on some weighted graphs a node climbs to a higher-priority label on each up pass and falls back on each down pass. When a pass returns the labels of two passes before, the run can only repeat itself, so it stops there with converged false; the result is then the same for any larger maxIterations. Longer cycles run to the cap.

This is what the legacy labelPropagationAsync does, despite its name, with the swap guard it lacks and the tie rule applied to the finished tally rather than to a running one. Conventions match labelPropagation: self-loops are skipped, parallel arcs summed, a directed snapshot reads out- and in-neighbours, weights are the exact f64 ones when the snapshot keeps them, and a negative, NaN or infinite weight throws.

Parameters ​
s ​

GraphSnapshot

Any snapshot

options? ​

SynchronousLabelPropagationOptions = {}

Pass cap and weighting

Returns ​

LabelPropagationResult

The partition, the passes run, and whether every label ended dominant

labelPropagationSynchronous.inputs ​

readonly inputs: readonly [] = []

labelPropagationSynchronous.name ​

readonly name: "labelPropagationSynchronous" = "labelPropagationSynchronous"

labelPropagationSynchronous.requiredOptions ​

readonly requiredOptions: readonly [] = []

labelPropagationSynchronous.result ​

readonly result: "partition" = "partition"

labelPropagationSynchronous.values ​

readonly values: readonly ["labels"]

labelPropagationSynchronous.weights ​

readonly weights: "by-default" = "by-default"

leiden ​

readonly leiden: object

leiden.accelerator ​

readonly accelerator: null = null

leiden.category ​

readonly category: "community" = "community"

leiden.direction ​

readonly direction: "undirected" = "undirected"

leiden.dispatch ​

readonly dispatch: "leiden" = "leiden"

leiden.fn ​

readonly fn: (s, options) => LeidenResult = leiden

Leiden community detection (Traag, Waltman and van Eck, Sci. Rep. 9:5233, 2019) over an undirected snapshot: fast local moving, refinement into well-connected sub-communities, and aggregation by contract() once per level. Whole passes repeat from the previous answer, keeping a pass only when it raises modularity, until three passes in a row improve it by no more than threshold or maxIterations passes have run; every pass starts by moving single original nodes, so the answer is also a local optimum of those moves.

Modularity follows graph-format's weightedDegree() convention (a self-loop counts twice), which on a graph without self-loops equals the legacy leiden's. Weights are the exact f64 ones when the snapshot keeps them. The partition is not the legacy function's move for move: the legacy leiden splits disconnected communities rather than refining them, and visits nodes in another order; what this guarantees is connected communities. Both are randomised heuristics, so for one seed either can come out ahead; on the shared fixtures this one's modularity is at least the legacy's at the default seed and on average over seeds.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

options? ​

LeidenOptions = {}

Resolution, seed, pass cap and stopping threshold

Returns ​

LeidenResult

The partition, its modularity, and the levels processed

Throws ​

Error on a directed snapshot; RangeError for a negative, NaN or infinite weight or a fractional seed

leiden.inputs ​

readonly inputs: readonly [] = []

leiden.name ​

readonly name: "leiden" = "leiden"

leiden.requiredOptions ​

readonly requiredOptions: readonly [] = []

leiden.result ​

readonly result: "partition" = "partition"

leiden.values ​

readonly values: readonly ["labels"]

leiden.weights ​

readonly weights: "always" = "always"

louvain ​

readonly louvain: object

louvain.accelerator ​

readonly accelerator: "louvain" = "louvain"

louvain.category ​

readonly category: "community" = "community"

louvain.direction ​

readonly direction: "undirected" = "undirected"

louvain.dispatch ​

readonly dispatch: "louvain" = "louvain"

louvain.fn ​

readonly fn: (s, o) => LouvainResult = louvain

Louvain community detection over a snapshot: local moving to the best modularity gain, then collapse each community into a node and repeat, until a level stops paying for itself.

The legacy louvain switches implementation at 50 nodes (useOptimized) and its small-graph path has no aggregation phase at all, so this port is not move-for-move identical to either branch of it -- what it guarantees is a partition whose modularity is at least as high, measured by the same formula.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

o? ​

LouvainOptions = {}

Algorithm options

Returns ​

LouvainResult

The partition, its modularity, and the number of levels that improved it

louvain.inputs ​

readonly inputs: readonly [] = []

louvain.name ​

readonly name: "louvain" = "louvain"

louvain.requiredOptions ​

readonly requiredOptions: readonly [] = []

louvain.result ​

readonly result: "partition" = "partition"

louvain.values ​

readonly values: readonly ["labels"]

louvain.weights ​

readonly weights: "always" = "always"

markovClustering ​

readonly markovClustering: object

markovClustering.accelerator ​

readonly accelerator: null = null

markovClustering.category ​

readonly category: "community" = "community"

markovClustering.direction ​

readonly direction: "any" = "any"

markovClustering.dispatch ​

readonly dispatch: null = null

markovClustering.fn ​

readonly fn: (s, options) => MarkovResult = markovClustering

Markov clustering (MCL; van Dongen, 2000), the index-based port of the legacy markovClustering.

The flow matrix starts as the column-normalised adjacency: entry (i, j) is the weight of the arc i -> j, so column j spreads j's flow over the nodes with an arc into it (on an undirected snapshot, its neighbours). With selfLoops every diagonal entry is first set to 1, replacing a self-loop's weight. Each round raises the matrix to the expansion power, raises every entry to the inflation power, renormalises the columns, drops the entries below pruningThreshold and renormalises again, until no entry moves by more than tolerance or maxIterations rounds ran. Node j then joins the attractor with the largest entry in its column, the lowest index on a tie; a node whose column emptied is a community of its own.

The matrix is kept sparse, and every sum is taken in the order the legacy dense loops take it, so the rounds are bit-identical to the legacy function's and so are the communities, their order and the attractors. Communities are labelled in the legacy function's order: the flow clusters by their lowest member, then the nodes whose column emptied. Two differences: parallel arcs are summed (a legacy graph has none), and iterations counts the rounds run, where the legacy function reports one more than maxIterations when it stops at the cap. A negative, NaN or infinite weight throws.

Parameters ​
s ​

AdjacencyView

Any snapshot or adjacency view

options? ​

MarkovOptions = {}

MCL parameters and the weight override

Returns ​

MarkovResult

The partition, the attractors, the rounds run and whether they converged

markovClustering.inputs ​

readonly inputs: readonly [] = []

markovClustering.name ​

readonly name: "markovClustering" = "markovClustering"

markovClustering.requiredOptions ​

readonly requiredOptions: readonly [] = []

markovClustering.result ​

readonly result: "partition" = "partition"

markovClustering.values ​

readonly values: readonly ["labels"]

markovClustering.weights ​

readonly weights: "always" = "always"

maxFlow ​

readonly maxFlow: object

maxFlow.accelerator ​

readonly accelerator: null = null

maxFlow.category ​

readonly category: "flow" = "flow"

maxFlow.direction ​

readonly direction: "any" = "any"

maxFlow.dispatch ​

readonly dispatch: "maxFlow" = "maxFlow"

maxFlow.fn ​

readonly fn: (s, sourceNode, sinkNode, options) => MaxFlowResult = maxFlow

Maximum flow from source to sink by augmenting paths.

Paths, bottlenecks and per-edge flows equal the legacy edmondsKarp / fordFulkerson on a graph with no parallel edges and no two opposite directed edges: the residual is kept per node pair and searched in the legacy row order (see buildResidual). Where two opposite directed edges carry flow, legacy records every push on the edge in the push's direction, so one edge can show more flow than its capacity; this port reports the net flow of the pair on the edges in its direction instead, each within its capacity.

Parameters ​
s ​

GraphSnapshot

The snapshot

sourceNode ​

NodeRef

The source node: its index, or { id }

sinkNode ​

NodeRef

The sink node: its index, or { id }

options? ​

MaxFlowOptions = {}

The path search and the capacity override

Returns ​

MaxFlowResult

The flow value, the per-edge flows, the source side and the cut edges

Throws ​

RangeError when source or sink is not a node index, or they are the same node

maxFlow.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

maxFlow.name ​

readonly name: "maxFlow" = "maxFlow"

maxFlow.requiredOptions ​

readonly requiredOptions: readonly [] = []

maxFlow.result ​

readonly result: "flow" = "flow"

maxFlow.values ​

readonly values: readonly ["flow"]

maxFlow.weights ​

readonly weights: "always" = "always"

maximumBipartiteMatching ​

readonly maximumBipartiteMatching: object

maximumBipartiteMatching.accelerator ​

readonly accelerator: null = null

maximumBipartiteMatching.category ​

readonly category: "matching" = "matching"

maximumBipartiteMatching.direction ​

readonly direction: "any" = "any"

maximumBipartiteMatching.dispatch ​

readonly dispatch: "maximumBipartiteMatching" = "maximumBipartiteMatching"

maximumBipartiteMatching.fn ​

readonly fn: (s, options) => BipartiteMatchingResult = maximumBipartiteMatching

Maximum matching of a bipartite graph by augmenting paths (Kuhn's algorithm, O(V E)).

Tie rule: among the equally large matchings it returns the one 2.x returned. Left nodes search in the order a breadth-first walk first reaches them (roots in node order, as isBipartite colours), and every node tries its neighbours in the order of the edge that joins them, the earliest added first. The search is depth-first and iterative. Parallel arcs and arc direction (by default) make no difference to the matching size.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

BipartiteMatchingOptions = {}

The two sides, and which arcs to follow on a directed snapshot

Returns ​

BipartiteMatchingResult

The partner of every matched left node and the number of pairs

Throws ​

Error when the sides are inferred and the graph is not bipartite

maximumBipartiteMatching.inputs ​

readonly inputs: readonly [] = []

maximumBipartiteMatching.name ​

readonly name: "maximumBipartiteMatching" = "maximumBipartiteMatching"

maximumBipartiteMatching.requiredOptions ​

readonly requiredOptions: readonly [] = []

maximumBipartiteMatching.result ​

readonly result: "matching" = "matching"

maximumBipartiteMatching.values ​

readonly values: readonly ["matching"]

maximumBipartiteMatching.weights ​

readonly weights: "never" = "never"

minSTCut ​

readonly minSTCut: object

minSTCut.accelerator ​

readonly accelerator: null = null

minSTCut.category ​

readonly category: "flow" = "flow"

minSTCut.direction ​

readonly direction: "any" = "any"

minSTCut.dispatch ​

readonly dispatch: "minSTCut" = "minSTCut"

minSTCut.fn ​

readonly fn: (s, sourceNode, sinkNode, options) => MinCutResult = minSTCut

Minimum s-t cut: the source side and value of a maximum flow (max-flow min-cut theorem). The side is the set reachable from the source in the final residual graph, which is the same for every maximum flow, so the path search does not change it. The search defaults to "ford-fulkerson", as the legacy minSTCut uses: on weights that are not binary fractions another search adds the bottlenecks in another order and the value can differ in its last bits.

Parameters ​
s ​

GraphSnapshot

The snapshot

sourceNode ​

NodeRef

The source node: its index, or { id }

sinkNode ​

NodeRef

The sink node: its index, or { id }

options? ​

MaxFlowOptions = {}

The path search and the capacity override

Returns ​

MinCutResult

The cut value, the source side and the cut edges

Throws ​

RangeError as maxFlow does

minSTCut.inputs ​

readonly inputs: readonly [AlgorithmInput, AlgorithmInput]

minSTCut.name ​

readonly name: "minSTCut" = "minSTCut"

minSTCut.requiredOptions ​

readonly requiredOptions: readonly [] = []

minSTCut.result ​

readonly result: "cut" = "cut"

minSTCut.values ​

readonly values: readonly [] = []

minSTCut.weights ​

readonly weights: "always" = "always"

modularity ​

readonly modularity: object

modularity.accelerator ​

readonly accelerator: null = null

modularity.category ​

readonly category: "community" = "community"

modularity.direction ​

readonly direction: "any" = "any"

modularity.dispatch ​

readonly dispatch: null = null

modularity.fn ​

readonly fn: (s, labels, options) => number = modularity

Newman's modularity of a partition: sum_c in_c / 2m - gamma * (tot_c / 2m)^2, where 2m is twice the total edge weight, in_c counts every edge inside community c twice and tot_c sums its nodes' weighted degrees. Degrees follow graph-format's weightedDegree() convention -- a self-loop counts twice -- so sum(tot_c) === 2m. On a directed snapshot the direction is ignored: every arc counts as an undirected edge, and a node's degree is its in-weight plus its out-weight.

On an undirected snapshot without self-loops this equals the legacy calculateModularity. On a directed snapshot or one with self-loops the two differ, and this one is the NetworkX value: the legacy degree counts a self-loop once and reads only out-neighbours on a directed graph, so its degrees do not sum to 2m.

It is NOT the legacy calculateMCLModularity, in two ways. That function subtracts the null-model term d(u) d(v) / 2m once per edge whatever the partition: on two separate triangles it scores one community and the two triangles both 1/3, where this returns 0 and 1/2. And it ignores edge weights, where this reads the snapshot's weights by default; pass weights filled with 1 for the unweighted value.

Parameters ​
s ​

AdjacencyView

Any snapshot or adjacency view

labels ​

U32

Community of every node; INVALID_INDEX leaves a node out of every community

options? ​

ModularityOptions = {}

Resolution and the weight override

Returns ​

number

The modularity, 0 when the snapshot has no edge weight

modularity.inputs ​

readonly inputs: readonly [{ kind: "node-labels"; name: "labels"; }]

modularity.name ​

readonly name: "modularity" = "modularity"

modularity.requiredOptions ​

readonly requiredOptions: readonly [] = []

modularity.result ​

readonly result: "number" = "number"

modularity.values ​

readonly values: readonly [] = []

modularity.weights ​

readonly weights: "always" = "always"

nodeClosenessCentrality ​

readonly nodeClosenessCentrality: object

nodeClosenessCentrality.accelerator ​

readonly accelerator: null = null

nodeClosenessCentrality.category ​

readonly category: "centrality" = "centrality"

nodeClosenessCentrality.direction ​

readonly direction: "any" = "any"

nodeClosenessCentrality.dispatch ​

readonly dispatch: null = null

nodeClosenessCentrality.fn ​

readonly fn: (s, nodeRef, options) => number = nodeClosenessCentrality

Closeness centrality of one node, with one search rather than n.

Parameters ​
s ​

GraphSnapshot

The snapshot

nodeRef ​

NodeRef

The node: its index, or { id }

options? ​

Omit<ClosenessOptions, "sources" | "k"> = {}

As closenessCentrality, without sampling: one node's exact score is one search

Returns ​

number

The node's score

Throws ​

RangeError for a node index outside [0, nodeCount)

nodeClosenessCentrality.inputs ​

readonly inputs: readonly [AlgorithmInput]

nodeClosenessCentrality.name ​

readonly name: "nodeClosenessCentrality" = "nodeClosenessCentrality"

nodeClosenessCentrality.requiredOptions ​

readonly requiredOptions: readonly [] = []

nodeClosenessCentrality.result ​

readonly result: "number" = "number"

nodeClosenessCentrality.values ​

readonly values: readonly [] = []

nodeClosenessCentrality.weights ​

readonly weights: "on-request" = "on-request"

pageRank ​

readonly pageRank: object

pageRank.accelerator ​

readonly accelerator: "pageRank" = "pageRank"

pageRank.category ​

readonly category: "centrality" = "centrality"

pageRank.direction ​

readonly direction: "any" = "any"

pageRank.dispatch ​

readonly dispatch: "pageRank" = "pageRank"

pageRank.fn ​

readonly fn: (s, o) => PageRankResult = pageRank

PageRank by pull over reverse(), with the dangling mass redistributed uniformly. On an undirected snapshot every edge carries rank both ways (a self-loop once), which is PageRank on the directed graph holding both arcs of every edge.

Parameters ​
s ​

GraphSnapshot

The snapshot

o? ​

PageRankOptions = {}

Algorithm options

Returns ​

PageRankResult

The scores, the iteration count and the convergence flag

pageRank.inputs ​

readonly inputs: readonly [] = []

pageRank.name ​

readonly name: "pageRank" = "pageRank"

pageRank.requiredOptions ​

readonly requiredOptions: readonly [] = []

pageRank.result ​

readonly result: "node-scores" = "node-scores"

pageRank.values ​

readonly values: readonly ["scores"]

pageRank.weights ​

readonly weights: "on-request" = "on-request"

personalizedPageRank ​

readonly personalizedPageRank: object

personalizedPageRank.accelerator ​

readonly accelerator: "personalizedPageRank" = "personalizedPageRank"

personalizedPageRank.category ​

readonly category: "centrality" = "centrality"

personalizedPageRank.direction ​

readonly direction: "any" = "any"

personalizedPageRank.dispatch ​

readonly dispatch: "personalizedPageRank" = "personalizedPageRank"

personalizedPageRank.fn ​

readonly fn: (s, personalization, o) => PageRankResult = personalizedPageRank

Personalized PageRank, as the legacy function computes it: the personalization vector, normalised to sum 1, replaces the uniform 1 / n in the teleport, and each node receives d * dangling / n of the dangling mass scaled by its personalization. That keeps only a 1 / n share of the dangling mass, so on a graph with a dangling node the scores sum to less than 1 (networkx spreads all of it). An all-zero vector gives plain PageRank, as the legacy function does for an empty list of personal nodes.

Parameters ​
s ​

GraphSnapshot

The snapshot

personalization ​

F64 | F32

One finite, non-negative mass per node index

o? ​

PageRankOptions = {}

Algorithm options

Returns ​

PageRankResult

The scores, the iteration count and the convergence flag

personalizedPageRank.inputs ​

readonly inputs: readonly [{ kind: "node-values"; name: "personalization"; }]

personalizedPageRank.name ​

readonly name: "personalizedPageRank" = "personalizedPageRank"

personalizedPageRank.requiredOptions ​

readonly requiredOptions: readonly [] = []

personalizedPageRank.result ​

readonly result: "node-scores" = "node-scores"

personalizedPageRank.values ​

readonly values: readonly ["scores"]

personalizedPageRank.weights ​

readonly weights: "on-request" = "on-request"

primMST ​

readonly primMST: object

primMST.accelerator ​

readonly accelerator: null = null

primMST.category ​

readonly category: "spanning-tree" = "spanning-tree"

primMST.direction ​

readonly direction: "undirected" = "undirected"

primMST.dispatch ​

readonly dispatch: "primMST" = "primMST"

primMST.fn ​

readonly fn: (s, o) => PrimResult = primMST

Prim's minimum spanning tree, grown from a start node by always taking the cheapest arc from the tree to a node outside it (an indexed heap keyed per node, so of several parallel edges the cheapest, and of equal ones the lowest-indexed, is the one taken). edges lists the logical edges in the order they joined the tree and totalWeight sums them in that order, as legacy primMST does. The start index is checked: one outside the graph throws a RangeError.

Parameters ​
s ​

GraphSnapshot

An undirected snapshot

o? ​

PrimOptions = {}

Per-arc weight override, start node and the spanning-forest switch

Returns ​

PrimResult

The accepted edges, their total weight and the discovery arc per node

Throws ​

Error on a directed snapshot, and on a disconnected one unless forest is set

primMST.inputs ​

readonly inputs: readonly [] = []

primMST.name ​

readonly name: "primMST" = "primMST"

primMST.requiredOptions ​

readonly requiredOptions: readonly [] = []

primMST.result ​

readonly result: "spanning-tree" = "spanning-tree"

primMST.values ​

readonly values: readonly ["predArc"]

primMST.weights ​

readonly weights: "always" = "always"

spectralClustering ​

readonly spectralClustering: object

spectralClustering.accelerator ​

readonly accelerator: null = null

spectralClustering.category ​

readonly category: "community" = "community"

spectralClustering.direction ​

readonly direction: "any" = "any"

spectralClustering.dispatch ​

readonly dispatch: null = null

spectralClustering.fn ​

readonly fn: (s, options) => SpectralResult = spectralClustering

Spectral clustering, the index-based port of the legacy spectralClustering: the k eigenvectors of the graph Laplacian with the smallest eigenvalues embed every node as a point in k dimensions, and k-means splits the points into at most k clusters.

The Laplacian is applied straight from the CSR rows and never built: D - A (unnormalized), I - D^-1/2 A D^-1/2 (normalized, whose embedded rows are then scaled to unit length, as Ng, Jordan and Weiss do) or I - D^-1 A (randomWalk, whose eigenvectors are D^-1/2 times the normalized ones). A node of degree 0 has a zero row. Self-loops are ignored (they cancel in D - A) and a directed snapshot is read as undirected, a reciprocal pair summing. A negative, NaN or infinite weight throws. With k >= nodeCount every node is its own cluster.

The eigenpairs come from subspace iteration with Rayleigh-Ritz, so they are the true smallest ones when converged is true; converged is false when the iteration stopped at its round cap (a small spectral gap, such as a path of hundreds of nodes), and the eigenpairs are then only approximate. The legacy function uses fixed placeholder eigenvalues for k <= 3 and plain power iteration (which finds the LARGEST eigenvectors) above that, and draws its k-means seeds from Math.random unless given a seed. The partitions therefore differ from the legacy function's; one seed gives one result. Labels are dense in first-seen order, so count is below k when k-means leaves a cluster empty.

Parameters ​
s ​

GraphSnapshot

Any snapshot

options ​

SpectralOptions

k, the Laplacian, the k-means limits, the seed and the weight override

Returns ​

SpectralResult

The partition and the eigenpairs it came from

spectralClustering.inputs ​

readonly inputs: readonly [] = []

spectralClustering.name ​

readonly name: "spectralClustering" = "spectralClustering"

spectralClustering.requiredOptions ​

readonly requiredOptions: readonly ["k"]

spectralClustering.result ​

readonly result: "partition" = "partition"

spectralClustering.values ​

readonly values: readonly ["labels"]

spectralClustering.weights ​

readonly weights: "always" = "always"

stoerWagner ​

readonly stoerWagner: object

stoerWagner.accelerator ​

readonly accelerator: null = null

stoerWagner.category ​

readonly category: "flow" = "flow"

stoerWagner.direction ​

readonly direction: "any" = "any"

stoerWagner.dispatch ​

readonly dispatch: "stoerWagner" = "stoerWagner"

stoerWagner.fn ​

readonly fn: (s, options) => MinCutResult = stoerWagner

Global minimum cut by Stoer-Wagner, reading every edge as undirected (a directed snapshot's arcs count in both directions, so two opposite arcs between one pair add up).

No graph is contracted (graph-format design 14.2): a representative array and member lists merge the last two nodes of each phase, and each phase's maximum-adjacency order accumulates the weights of the ORIGINAL arcs of the merged members in an IndexedMaxHeap. A phase starts from the lowest-index remaining representative and takes equal keys lowest index first, and the first phase with the lightest cut wins, which is the order the legacy implementation uses. O(n (m + n) log n).

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

StoerWagnerOptions = {}

The weight override

Returns ​

MinCutResult

The cut value, the side holding the last node of the winning phase, and the cut edges; with fewer than two nodes the value is 0 and every node is on side

stoerWagner.inputs ​

readonly inputs: readonly [] = []

stoerWagner.name ​

readonly name: "stoerWagner" = "stoerWagner"

stoerWagner.requiredOptions ​

readonly requiredOptions: readonly [] = []

stoerWagner.result ​

readonly result: "cut" = "cut"

stoerWagner.values ​

readonly values: readonly [] = []

stoerWagner.weights ​

readonly weights: "always" = "always"

stronglyConnectedComponents ​

readonly stronglyConnectedComponents: object

stronglyConnectedComponents.accelerator ​

readonly accelerator: null = null

stronglyConnectedComponents.category ​

readonly category: "components" = "components"

stronglyConnectedComponents.direction ​

readonly direction: "directed" = "directed"

stronglyConnectedComponents.dispatch ​

readonly dispatch: "stronglyConnectedComponents" = "stronglyConnectedComponents"

stronglyConnectedComponents.fn ​

readonly fn: (g, options) => LabelResult = stronglyConnectedComponents

Strongly connected components by an iterative Tarjan: roots in index order, neighbours in row order unless options.arcOrder gives another, and component c is the c-th to complete -- the numbering the legacy stronglyConnectedComponents gives its result array. Completion order is a reverse topological order of the condensation.

Parameters ​
g ​

AdjacencyView

A directed adjacency

options? ​

ArcOrderOption = {}

The neighbour order

Returns ​

LabelResult

The partition, labels in completion order

Throws ​

Error when the graph is undirected

stronglyConnectedComponents.inputs ​

readonly inputs: readonly [] = []

stronglyConnectedComponents.name ​

readonly name: "stronglyConnectedComponents" = "stronglyConnectedComponents"

stronglyConnectedComponents.requiredOptions ​

readonly requiredOptions: readonly [] = []

stronglyConnectedComponents.result ​

readonly result: "partition" = "partition"

stronglyConnectedComponents.values ​

readonly values: readonly ["labels"]

stronglyConnectedComponents.weights ​

readonly weights: "never" = "never"

syncClustering ​

readonly syncClustering: object

syncClustering.accelerator ​

readonly accelerator: null = null

syncClustering.category ​

readonly category: "community" = "community"

syncClustering.direction ​

readonly direction: "any" = "any"

syncClustering.dispatch ​

readonly dispatch: null = null

syncClustering.fn ​

readonly fn: (s, options) => SyncClusteringResult = syncClustering

SynC over a snapshot: node embeddings seeded from degree and a seeded generator, each moved part of the way to the mean of its out-neighbors' embeddings at every step, and clustered by k-means with k-means++ centers. Smoothing gathers a connected community within a few steps, and run long enough it would gather each whole connected part into one point, so the run stops once the cluster assignment has held for 10 iterations (or the loss settles). Unconnected cliques of any size come back as separate clusters, and planted communities as their own clusters. The order of every random draw is the legacy syncClustering's, but legacy took a fixed gradient step that also pulled every node toward the origin, so its results differ (see issues #1600 and #1698). The port draws from its own generator instead of replacing Math.random for the duration of the call.

Weights are ignored and a parallel arc pulls once per arc. The seeding degree is legacy's: in plus out when directed, the stored arc count when undirected, so an undirected self-loop counts once.

Parameters ​
s ​

GraphSnapshot

The snapshot

options ​

SyncClusteringOptions

SyncClusteringOptions

Returns ​

SyncClusteringResult

Assignments, embeddings and convergence

syncClustering.inputs ​

readonly inputs: readonly [] = []

syncClustering.name ​

readonly name: "syncClustering" = "syncClustering"

syncClustering.requiredOptions ​

readonly requiredOptions: readonly ["numClusters"]

syncClustering.result ​

readonly result: "partition" = "partition"

syncClustering.values ​

readonly values: readonly ["labels"]

syncClustering.weights ​

readonly weights: "never" = "never"

teraHAC ​

readonly teraHAC: object

teraHAC.accelerator ​

readonly accelerator: null = null

teraHAC.category ​

readonly category: "community" = "community"

teraHAC.direction ​

readonly direction: "any" = "any"

teraHAC.dispatch ​

readonly dispatch: null = null

teraHAC.fn ​

readonly fn: (s, options) => TeraHacResult = teraHAC

TeraHAC over a snapshot: agglomerative clustering that repeatedly merges the closest pair of clusters, with the same distances, merge order and tie-breaks as the legacy teraHAC -- but over node indices, so the result no longer depends on what the node ids are.

The linkage is kept per ordered cluster pair as an aggregate (minimum, maximum, sum of distances or sum of squared distances) and updated on each merge, instead of rescanning every member pair; the pairwise distances are integers, so the sums, and the means divided out of them, are exact. A pair's distance reads the aggregate in the orientation legacy reads it, which matters on a directed snapshot, and ties go to the pair legacy's stable sort puts first: two original nodes before any pair with a merged cluster, and among those the most recent merge last.

Weights are ignored (legacy counts hops). O(n^2) memory and O(n (n + m)) for the distances; the merging keeps each cluster's closest partner and rescans a row only when that partner merges.

Parameters ​
s ​

GraphSnapshot

The snapshot

options? ​

TeraHacOptions = {}

TeraHacOptions

Returns ​

TeraHacResult

The flat clustering and the dendrogram

teraHAC.inputs ​

readonly inputs: readonly [] = []

teraHAC.name ​

readonly name: "teraHAC" = "teraHAC"

teraHAC.requiredOptions ​

readonly requiredOptions: readonly [] = []

teraHAC.result ​

readonly result: "partition" = "partition"

teraHAC.values ​

readonly values: readonly ["labels"]

teraHAC.weights ​

readonly weights: "never" = "never"

topologicalSort ​

readonly topologicalSort: object

topologicalSort.accelerator ​

readonly accelerator: null = null

topologicalSort.category ​

readonly category: "structure" = "structure"

topologicalSort.direction ​

readonly direction: "directed" = "directed"

topologicalSort.dispatch ​

readonly dispatch: null = null

topologicalSort.fn ​

readonly fn: (g, options) => U32 | null = topologicalSort

Topological order of a directed graph: reverse DFS post-order, roots taken in index order and neighbours in row order unless options.arcOrder gives another.

Parameters ​
g ​

AdjacencyView

A directed adjacency

options? ​

ArcOrderOption = {}

The neighbour order

Returns ​

U32 | null

The node indices in topological order, or null when the graph has a cycle

Throws ​

Error when the graph is undirected

topologicalSort.inputs ​

readonly inputs: readonly [] = []

topologicalSort.name ​

readonly name: "topologicalSort" = "topologicalSort"

topologicalSort.requiredOptions ​

readonly requiredOptions: readonly [] = []

topologicalSort.result ​

readonly result: "order" = "order"

topologicalSort.values ​

readonly values: readonly [] = []

topologicalSort.weights ​

readonly weights: "never" = "never"

triangleCount ​

readonly triangleCount: object

triangleCount.accelerator ​

readonly accelerator: "triangleCount" = "triangleCount"

triangleCount.category ​

readonly category: "structure" = "structure"

triangleCount.direction ​

readonly direction: "any" = "any"

triangleCount.dispatch ​

readonly dispatch: "triangleCount" = "triangleCount"

triangleCount.fn ​

readonly fn: (s) => TriangleCountResult = triangleCount

Triangle counting, with each node's clustering coefficient and the graph's transitivity, over the simple undirected graph underlying the snapshot: arc directions are ignored, parallel edges count once and self-loops not at all, so a directed snapshot and its undirected twin give the same answer. Each edge is oriented from the lower to the higher node in (degree, index) order and the two oriented rows of every oriented edge are intersected, so each triangle is found exactly once: O(m^1.5).

Parameters ​
s ​

GraphSnapshot

Any snapshot

Returns ​

TriangleCountResult

The per-node and total triangles, the clustering coefficient and the transitivity

triangleCount.inputs ​

readonly inputs: readonly [] = []

triangleCount.name ​

readonly name: "triangleCount" = "triangleCount"

triangleCount.requiredOptions ​

readonly requiredOptions: readonly [] = []

triangleCount.result ​

readonly result: "node-scores" = "node-scores"

triangleCount.values ​

readonly values: readonly ["perNode", "coefficient"]

triangleCount.weights ​

readonly weights: "never" = "never"

weaklyConnectedComponents ​

readonly weaklyConnectedComponents: object

weaklyConnectedComponents.accelerator ​

readonly accelerator: "weaklyConnectedComponents" = "weaklyConnectedComponents"

weaklyConnectedComponents.category ​

readonly category: "components" = "components"

weaklyConnectedComponents.direction ​

readonly direction: "any" = "any"

weaklyConnectedComponents.dispatch ​

readonly dispatch: "weaklyConnectedComponents" = "weaklyConnectedComponents"

weaklyConnectedComponents.fn ​

readonly fn: (s) => LabelResult = weaklyConnectedComponents

Weakly connected components: the same union-find pass with the direction check dropped.

Parameters ​
s ​

GraphSnapshot

Any snapshot

Returns ​

LabelResult

The partition

weaklyConnectedComponents.inputs ​

readonly inputs: readonly [] = []

weaklyConnectedComponents.name ​

readonly name: "weaklyConnectedComponents" = "weaklyConnectedComponents"

weaklyConnectedComponents.requiredOptions ​

readonly requiredOptions: readonly [] = []

weaklyConnectedComponents.result ​

readonly result: "partition" = "partition"

weaklyConnectedComponents.values ​

readonly values: readonly ["labels"]

weaklyConnectedComponents.weights ​

readonly weights: "never" = "never"

Example ​

ts
import { ALGORITHMS } from "@graphty/algorithms";

for (const a of Object.values(ALGORITHMS)) {
    if (a.direction !== "directed" && a.inputs.length === 0 && a.result === "node-scores") {
        console.log(a.name, a.weights);
    }
}