@graphty/algorithms / index / indexed / kargerMinCut

Function: kargerMinCut()

kargerMinCut(s, options?): MinCutResult

Defined in: indexed/min-cut.ts:156

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