Maximum Flow

Flow network:
  S → A (cap 10)    A → T (cap 10)
  S → B (cap 10)    B → T (cap 10)
  A → B (cap 1)

Rules:
  1. Capacity constraint:  0 ≤ flow(u,v) ≤ capacity(u,v)
  2. Flow conservation:    inflow(v) = outflow(v)  for all v except s,t
  3. Skew symmetry:        flow(u,v) = -flow(v,u)

Maximum flow S→T = 20 (10 through A, 10 through B)
(The A→B edge is irrelevant — neither path uses it)

Forward edge residual:  c - f  (remaining capacity)
Backward edge residual: f      (flow that can be "cancelled")

If edge S→A has capacity 10 and current flow 7:
  S→A residual = 10-7 = 3  (can push 3 more)
  A→S residual = 7         (can cancel 7 of existing flow)

The backward edge is how the algorithm "corrects" suboptimal paths.
An augmenting path in the residual graph increases total flow.

max_flow = 0
while there exists an augmenting path s→t in residual graph:
    bottleneck = min residual capacity along the path
    for each edge (u,v) on the path:
        residual[u][v] -= bottleneck   # reduce forward capacity
        residual[v][u] += bottleneck   # add backward capacity
    max_flow += bottleneck
return max_flow

from collections import deque, defaultdict

def edmonds_karp(graph, source, sink):
    """
    graph: {u: {v: capacity}}
    Returns maximum flow from source to sink.
    """
    # Build residual graph (copy of capacity graph)
    residual = defaultdict(lambda: defaultdict(int))
    for u in graph:
        for v, cap in graph[u].items():
            residual[u][v] += cap

    def bfs_augmenting_path():
        """BFS to find shortest augmenting path. Returns parent dict or None."""
        parent  = {source: None}
        visited = {source}
        queue   = deque([source])
        while queue:
            u = queue.popleft()
            for v, cap in residual[u].items():
                if v not in visited and cap > 0:
                    visited.add(v)
                    parent[v] = u
                    if v == sink:
                        return parent
                    queue.append(v)
        return None

    max_flow = 0
    while True:
        parent = bfs_augmenting_path()
        if parent is None:
            break                    # no augmenting path → done

        # Find bottleneck capacity along the path
        path_flow = float('inf')
        v = sink
        while v != source:
            u = parent[v]
            path_flow = min(path_flow, residual[u][v])
            v = u

        # Update residual capacities
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= path_flow
            residual[v][u] += path_flow
            v = u

        max_flow += path_flow

    return max_flow

# Example
graph = {
    "S": {"A": 10, "B": 10},
    "A": {"T": 10, "B": 1},
    "B": {"T": 10},
    "T": {}
}
print(edmonds_karp(graph, "S", "T"))   # 20

# Maximum flow models many real-world problems:

# 1. Network routing — maximum data throughput between two nodes
# 2. Bipartite matching — match workers to jobs optimally
#    (add source connected to all workers, all jobs connected to sink)
# 3. Image segmentation — foreground/background separation (min-cut)
# 4. Project scheduling — identify critical bottleneck resources
# 5. Baseball elimination — determine if a team is mathematically eliminated

# Bipartite matching example:
# Workers W1,W2 can do Jobs J1,J2,J3
# Source → each worker (cap 1)
# Each worker → jobs they can do (cap 1)
# Each job → Sink (cap 1)
# Max flow = maximum matching size