# Network Flow & Capacity

```elixir
Mix.install([
  {:yog_ex, path: "/home/mafinar/repos/elixir/yog_ex"},
  {:kino_vizjs, "~> 0.8.0"}
])
```

## Introduction

Network Flow algorithms help solve optimization problems where something (water, data, electricity, goods) moves through a network with limited capacity.

The most famous result in this field is the **Max-Flow Min-Cut Theorem**, which states that the maximum flow through a network is equal to the capacity of the smallest bottleneck (the minimum cut).

## 🚰 Maximum Flow

How much "stuff" can we push from a Source to a Sink?

```elixir
alias Yog.Flow.MaxFlow

# Create a flow network
# Edges represent (from, to, capacity)
g = Yog.directed()
  |> Yog.add_edges!([
    {:s, :a, 10}, {:s, :b, 10},
    {:a, :c, 8}, {:a, :b, 2},
    {:b, :c, 9},
    {:c, :t, 20}
  ])

# Calculate Max Flow using Dinic's algorithm (efficient for dense networks)
result = MaxFlow.dinic(g, :s, :t)

IO.puts "Maximum Flow from S to T: #{result.max_flow}"
```

## ✂️ Minimum Cut (Finding the Bottleneck)

The minimum cut is the set of edges that, if removed, would completely disconnect the source from the sink with the minimum possible total capacity. These are your network's true bottlenecks.

```elixir
# Extract the min-cut from the previous result
min_cut = MaxFlow.min_cut(result)

IO.puts "Min-Cut Capacity: #{min_cut.capacity}"
IO.inspect(min_cut.source_side, label: "Nodes on Source side")
IO.inspect(min_cut.sink_side, label: "Nodes on Sink side")

# Let's visualize the cut!
# We'll color nodes by which side of the cut they are on
cut_opts = Yog.Render.DOT.cut_to_options(min_cut)
dot = Yog.Render.DOT.to_dot(g, cut_opts)
Kino.VizJS.render(dot)
```

## 🌍 Global Min-Cut

Sometimes you want the minimum cut of the entire graph (not just between a specific source and sink). The Stoer-Wagner algorithm finds this efficiently.

```elixir
# Create an undirected graph
g = Yog.undirected()
  |> Yog.add_edges!([
    {:a, :b, 3}, {:a, :c, 2},
    {:b, :c, 4}, {:b, :d, 1},
    {:c, :d, 5}
  ])

# Find the global minimum cut
global_cut = Yog.Flow.MinCut.global_min_cut(g, track_partitions: true)
IO.puts("Global min-cut value: #{global_cut.cut_value}")
IO.inspect(global_cut.source_side, label: "Source side")
IO.inspect(global_cut.sink_side, label: "Sink side")
```

## 🤝 Bipartite Matching

One of the most powerful applications of Max-Flow is solving **Matching Problems** (e.g., matching jobs to candidates). By adding a virtual source and sink, any matching problem becomes a flow problem.

```elixir
# Yog provides a dedicated module for this too
g = Yog.undirected()
  |> Yog.add_edges!([
    {"Job1", "Alice", 1}, {"Job1", "Bob", 1},
    {"Job2", "Alice", 1},
    {"Job3", "Charlie", 1}
  ])

matching = Yog.Matching.HopcroftKarp.max_matching(g)
IO.inspect(matching, label: "Optimal Job-Candidate Pairs")

# Count how many jobs got matched
matched_jobs = matching |> Map.keys() |> Enum.filter(&String.starts_with?(&1, "Job")) |> length()
IO.puts("Matched #{matched_jobs} jobs")
```

## Summary

`Yog`'s Flow suite includes:

1. **Max-Flow** (Edmonds-Karp, Dinic, Push-Relabel) for throughput.
2. **Min-Cut** for bottleneck identification.
3. **Global Min-Cut** (Stoer-Wagner, Karger-Stein) for general graph clustering.
4. **Bipartite Matching** for assignment problems.

You've now explored the core pillars of the Yog library! Check the [Algorithm Catalog](ALGORITHMS.md) for even more advanced techniques.