Yog.FSharp
Getting Started Examples API Reference GitHub

MinCut Module

Namespace: Yog.Flow
Assembly: Yog.FSharp.dll

Stoer-Wagner global minimum cut algorithm.

Finds the minimum weight cut that partitions the graph into two non-empty sets, without specifying which nodes must be on which side (unlike s-t min cut).

When to Use

  • Graph partitioning and clustering
  • Finding the weakest link in a network
  • Image segmentation
  • VLSI design (circuit partitioning)
  • Community detection in networks

Key Concepts

Global Minimum Cut

A partition of nodes into two non-empty sets A and B that minimizes the sum of weights of edges crossing from A to B.

Stoer-Wagner Algorithm

Uses Maximum Adjacency Search (MAS) to find the "most tightly connected" node pair, then contracts them and repeats.

Complexity

  • Time: O(V³) - cubic in number of vertices
  • Space: O(V + E)

Comparison with Max-Flow Min-Cut

Aspect

Global Min Cut (Stoer-Wagner)

s-t Min Cut (Max Flow)

Source/Sink

Not specified

Must be specified

Partitions

Any two non-empty sets

Separates specific nodes

Algorithm

Contraction-based

Augmenting paths

Complexity

O(V³)

O(VE²)

Maximum Adjacency Search

The key subroutine orders vertices by their connectivity strength to the growing set, identifying the most tightly connected pair.

Types

Type Description

MinCut

Represents the sizes and weight of a graph partition.

Returned by globalMinCut, describes the minimum cut found.

Functions and values

Function or value Description

globalMinCut graph

Full Usage: globalMinCut graph

Parameters:
Returns: MinCut

MinCut containing the minimum cut weight and partition sizes.

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

Parameters

  • graph: Input graph with integer edge weights

Algorithm

  1. Run Maximum Adjacency Search to find most tightly connected pair
  2. The last node added has a cut separating it from the rest
  3. Contract the pair and repeat
  4. Return the minimum cut found across all iterations

Complexity

  • Time: O(V³)
  • Space: O(V + E)

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 

// Create a weighted undirected graph
let graph =
    empty Undirected
    |> addNode 0 () |> addNode 1 () |> addNode 2 () |> addNode 3 ()
    |> addEdge 0 1 3 |> addEdge 0 2 2 |> addEdge 1 2 4 |> addEdge 2 3 1

let result = globalMinCut graph
// result.Weight = 1 (cut between node 2 and node 3)
// result.GroupASize = 3, result.GroupBSize = 1

Use Cases

  • Network reliability: Find minimum edges to remove to disconnect graph
  • Clustering: Natural graph partitioning point
  • Image segmentation: Separate foreground from background
val graph: obj
val result: obj

graph : Graph<'n, int>
Returns: MinCut

MinCut containing the minimum cut weight and partition sizes.