@spec global_min_cut(
  Yog.graph(),
  keyword()
) :: Yog.Flow.MinCutResult.t()

Finds the global minimum cut of an undirected weighted graph.

This implementation uses the Stoer-Wagner algorithm. It repeatedly finds an s-t min-cut in a phase using Maximum Adjacency Search and then contracts the nodes s and t. The global minimum cut is the minimum of all phase cuts.

Time Complexity: O(V³) (O(V² log V) with priority queue optimization)

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.cut_value
5
iex> result.source_side_size + result.sink_side_size
3

Parameters

• graph - The undirected weighted graph
• opts - Options:
  • :track_partitions - If true, populates the source_side and sink_side fields in the result. (default: false)

Notes

• The graph must be undirected
• Edge weights must be integers
• Returns a Yog.Flow.MinCutResult struct

@spec gomory_hu_tree(Yog.graph()) :: Yog.graph()

Builds a Gomory-Hu tree representing all-pairs min-cuts in the graph.

The Gomory-Hu tree is a weighted tree on the same vertex set where the minimum edge weight on the path between any two nodes equals their min-cut value in the original graph. This implementation uses Gusfield's algorithm, requiring only V-1 max-flow computations.

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 3}, {1, 3, 4}, {2, 3, 2}, {2, 4, 5}, {3, 4, 1}])
iex> tree = Yog.Flow.MinCut.gomory_hu_tree(graph)
iex> length(Yog.Model.all_edges(tree))
3

@spec karger_stein(
  Yog.graph(),
  keyword()
) :: Yog.Flow.MinCutResult.t()

Finds the global minimum cut using the randomized Karger-Stein algorithm.

Karger-Stein uses repeated random edge contraction with recursive branching to achieve high success probability. It is particularly effective on large graphs where the exact Stoer-Wagner algorithm may be slower, as the randomized approach can often find the global minimum cut with very few iterations.

Parameters

• graph - The undirected weighted graph
• opts - Options:
  • :iterations - Number of independent runs of the recursive fast-cut procedure (default: max(1, trunc(n * log2(n + 1)))). Increasing the number of iterations improves the success probability.

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 5}, {2, 3, 3}, {1, 3, 2}])
iex> result = Yog.Flow.MinCut.karger_stein(graph)
iex> result.cut_value
5

@spec min_cut_query(Yog.graph(), Yog.node_id(), Yog.node_id()) ::
  {number(), MapSet.t(Yog.node_id()), MapSet.t(Yog.node_id())}

Queries the min-cut value and partitions between two nodes using a Gomory-Hu tree.

Returns {cut_value, partition_s, partition_t} where cut_value is the min-cut between node_a and node_b in the original graph, and the partitions are the two sides of that cut.

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 3}, {1, 3, 4}, {2, 3, 2}, {2, 4, 5}, {3, 4, 1}])
iex> tree = Yog.Flow.MinCut.gomory_hu_tree(graph)
iex> {cut_value, _s, _t} = Yog.Flow.MinCut.min_cut_query(tree, 1, 4)
iex> cut_value
6

@spec s_t_min_cut(Yog.graph(), Yog.node_id(), Yog.node_id(), atom()) ::
  Yog.Flow.MinCutResult.t()

Computes the minimum s-t cut using a max-flow algorithm.

This is a convenience wrapper that delegates to Yog.Flow.MaxFlow.max_flow/4 and extracts the corresponding min-cut from the residual graph.

Parameters

• graph - The flow network
• source - Source node ID
• sink - Sink node ID
• algorithm - Algorithm to use: :edmonds_karp (default), :dinic, or :push_relabel

Examples

iex> {:ok, graph} = Yog.directed()
...>   |> Yog.add_node(1, "s")
...>   |> Yog.add_node(2, "a")
...>   |> Yog.add_node(3, "t")
...>   |> Yog.add_edges([{1, 2, 10}, {2, 3, 5}])
iex> result = Yog.Flow.MinCut.s_t_min_cut(graph, 1, 3)
iex> result.cut_value
5