# `Yog.Flow.MinCut`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/flow/min_cut.ex#L1)

Global minimum cut algorithms for undirected graphs.

This module finds the [global minimum cut](https://en.wikipedia.org/wiki/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 Summary

| Algorithm | Function | Complexity | Best For |
|-----------|----------|------------|----------|
| [Stoer-Wagner](https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm) | `global_min_cut/2` | O(V³) | Dense undirected graphs, exact result |
| [Karger-Stein](https://en.wikipedia.org/wiki/Karger%27s_algorithm) | `karger_stein/2` | O(V² log³ V) | Large graphs, randomized approach |
| [Gomory-Hu Tree](https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree) | `gomory_hu_tree/1` | O(V · MaxFlow) | All-pairs min-cut analysis |

## 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 the current set (used by Stoer-Wagner).
- **Edge Contraction**: Merging two nodes while preserving total edge weight to other nodes (used by Karger-Stein).

## Gomory-Hu Trees

The Gomory-Hu tree is a powerful structure that encodes all-pairs min-cuts using only `V-1` max-flow
computations. In the tree, the min-cut value between any two nodes `u` and `v` is the minimum
weight on the unique tree path between them.

Use `gomory_hu_tree/1` to build the tree and `min_cut_query/3` to extract values and partitions.

<div class="graphviz">
graph G {
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  rankdir=LR;

  1 -- 2 [label="7"];
  2 -- 3 [label="5"];
  2 -- 4 [label="6"];
  
  label="Example Gomory-Hu Tree";
  fontsize=12;
}
</div>

## Randomized Algorithms

For very large graphs where exact algorithms (O(V³)) might be slow, `karger_stein/2` 
provides a randomized approach based on edge contraction. It uses recursive branching 
to achieve a high probability of success.

## Comparison with s-t Min-Cut

For finding a cut between specific source and sink nodes, use `Yog.Flow.MaxFlow` or the convenience `s_t_min_cut/4`:
- `s_t_min_cut(graph, s, t, :dinic)`: Efficiently finds the cut separating `s` and `t`.
- `global_min_cut(graph)`: Finds the minimum weight cut across *any* possible partition.

## Examples

### Global Minimum Cut (Stoer-Wagner)

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

### All-Pairs Analysis (Gomory-Hu)

    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

## References

- [Wikipedia: Minimum Cut](https://en.wikipedia.org/wiki/Minimum_cut)
- [Wikipedia: Stoer-Wagner Algorithm](https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm)
- [Wikipedia: Karger's Algorithm](https://en.wikipedia.org/wiki/Karger%27s_algorithm)
- [Wikipedia: Gomory-Hu Tree](https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree)
- [CP-Algorithms: Stoer-Wagner](https://cp-algorithms.com/graph/stoer_wagner.html)

# `global_min_cut`

```elixir
@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

# `gomory_hu_tree`

```elixir
@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

# `karger_stein`

```elixir
@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

# `min_cut_query`

```elixir
@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

# `s_t_min_cut`

```elixir
@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

---

*Consult [api-reference.md](api-reference.md) for complete listing*