@graphty/algorithms / index / stoerWagner
Function: stoerWagner() ​
stoerWagner(
s,options?):MinCutResult
Defined in: indexed/min-cut.ts:48
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 ​
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