Yog.Flow.MinCut (YogEx v0.70.0)

Global minimum cut algorithms for undirected graphs.

This module finds the global minimum cut in an undirected weighted graph - the partition of nodes into two non-empty sets that minimizes the total weight of edges crossing between the sets.

Algorithm

Algorithm	Function	Complexity	Best For
Stoer-Wagner	`global_min_cut/1`	O(V³)	Dense undirected graphs

The implementation uses the Stoer-Wagner algorithm with Maximum Adjacency Search.

Key Concepts

Global Min-Cut: The minimum cut over all possible partitions of the graph
s-t Cut: A cut that separates specific nodes s and t
Maximum Adjacency Search: Orders vertices by strength of connection to current set
Node Contraction: Merging two nodes while preserving edge weights

Comparison with s-t Min-Cut

For finding a cut between specific source and sink nodes, use Yog.Flow.MaxFlow instead:

Yog.Flow.MaxFlow.edmonds_karp/8 + extract_min_cut/1: O(VE²), for directed graphs
Yog.Flow.MinCut.global_min_cut/1: O(V³), for undirected graphs, finds best cut globally

Use Cases

Network reliability: Identify weakest points in communication networks
Image segmentation: Separate foreground from background in computer vision
Clustering: Graph partitioning for community detection
VLSI design: Circuit partitioning to minimize wire crossings

Example

graph =
  Yog.undirected()
  |> Yog.add_node(1, "A")
  |> Yog.add_node(2, "B")
  |> Yog.add_node(3, "C")
  |> Yog.add_node(4, "D")
  |> Yog.add_edges([
    {1, 2, 3},
    {1, 3, 4},
    {2, 3, 2},
    {2, 4, 5},
    {3, 4, 1}
  ])

result = Yog.Flow.MinCut.global_min_cut(graph)
# => %{weight: 3, group_a_size: 1, group_b_size: 3}

References

Summary

Types

min_cut()

Result of a global minimum cut computation.

Functions

global_min_cut(graph)

Finds the global minimum cut of an undirected weighted graph.

Types

min_cut()

@type min_cut() :: %{
  weight: integer(),
  group_a_size: integer(),
  group_b_size: integer()
}

Result of a global minimum cut computation.

Contains the cut weight and the sizes of the two partitions.

Functions

global_min_cut(graph)

@spec global_min_cut(Yog.graph()) :: min_cut()

Finds the global minimum cut of an undirected weighted graph.

Uses a simplified approach: for small graphs, convert to directed and use max-flow min-cut by trying representative source-sink pairs.

Time Complexity: O(V · E²) worst case

Examples

Simple triangle graph:

iex> {:ok, graph} = Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 2}])
iex> result = Yog.Flow.MinCut.global_min_cut(graph)
iex> result.group_a_size + result.group_b_size
3

A larger example:

iex> {:ok, graph} = Yog.undirected()
...>   |> Yog.add_node(1, "A")
...>   |> Yog.add_node(2, "B")
...>   |> Yog.add_node(3, "C")
...>   |> Yog.add_node(4, "D")
...>   |> Yog.add_edges([
...>     {1, 2, 3},
...>     {1, 3, 4},
...>     {2, 3, 2},
...>     {2, 4, 5},
...>     {3, 4, 1}
...>   ])
iex> result = Yog.Flow.MinCut.global_min_cut(graph)
iex> result.weight > 0
true

Notes

The graph must be undirected
Edge weights must be integers