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. Perfect for AoC 2023 Day 25, where you need to find the cut of weight 3 and compute the product of partition sizes.

Time Complexity: O(V³) or O(VE + V² log V) with a good priority queue

Example

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)
  |> yog.add_node(2, Nil)
  |> yog.add_node(3, Nil)
  |> yog.add_node(4, Nil)
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)
  |> yog.add_edge(from: 3, to: 4, with: 1)
  |> yog.add_edge(from: 1, to: 4, with: 1)

let result = min_cut.global_min_cut(in: graph)
// result.weight == 2 (minimum cut)
// result.group_a_size * result.group_b_size == product of partition sizes