min_cut

Stoer-Wagner algorithm for global minimum cut.

Types

pub type MinCut {
  MinCut(weight: Int, group_a_size: Int, group_b_size: Int)
}

MinCut(weight: Int, group_a_size: Int, group_b_size: Int)

</>

pub fn global_min_cut(in graph: model.Graph(n, Int)) -> MinCut

Finds the global minimum cut of an undirected weighted graph using the Stoer-Wagner algorithm.

Returns the minimum cut weight and the sizes of the two partitions.

Time Complexity: O(V³)

let result = min_cut.global_min_cut(in: graph)