Edmonds-Karp Algorithm

from collections import deque

class Edge:
    def __init__(self, to: int, rev: int, residual: int) -> None:
        self.to, self.rev, self.residual = to, rev, residual

class EdmondsKarp:
    def __init__(self, n: int) -> None:
        if n <= 0:
            raise ValueError("n must be positive")
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, capacity: int) -> None:
        if not (0 <= u < len(self.graph) and 0 <= v < len(self.graph)):
            raise IndexError("vertex out of range")
        if u == v:
            raise ValueError("self-loops are not supported")
        if capacity < 0:
            raise ValueError("capacity must be non-negative")
        forward = Edge(v, len(self.graph[v]), capacity)
        reverse = Edge(u, len(self.graph[u]), 0)
        self.graph[u].append(forward)
        self.graph[v].append(reverse)

    def _bfs(self, source: int, sink: int):
        parent = [None] * len(self.graph)  # (previous vertex, edge index)
        parent[source] = (-1, -1)
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for edge_index, edge in enumerate(self.graph[u]):
                if edge.residual == 0 or parent[edge.to] is not None:
                    continue
                parent[edge.to] = (u, edge_index)
                if edge.to == sink:
                    return parent
                queue.append(edge.to)
        return None

    def max_flow(self, source: int, sink: int) -> int:
        if not (0 <= source < len(self.graph) and 0 <= sink < len(self.graph)):
            raise IndexError("vertex out of range")
        if source == sink:
            raise ValueError("source and sink must differ")
        total = 0
        while (parent := self._bfs(source, sink)) is not None:
            bottleneck = None
            v = sink
            while v != source:
                u, edge_index = parent[v]
                residual = self.graph[u][edge_index].residual
                bottleneck = residual if bottleneck is None else min(bottleneck, residual)
                v = u
            assert bottleneck is not None
            v = sink
            while v != source:
                u, edge_index = parent[v]
                edge = self.graph[u][edge_index]
                edge.residual -= bottleneck
                self.graph[edge.to][edge.rev].residual += bottleneck
                v = u
            total += bottleneck
        return total

flow = EdmondsKarp(6)
for edge in [
    (0,1,16), (0,2,13), (1,2,10), (2,1,4), (1,3,12),
    (2,4,14), (3,2,9), (4,3,7), (3,5,20), (4,5,4),
]:
    flow.add_edge(*edge)
assert flow.max_flow(0, 5) == 23

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class EdmondsKarp {
    static final class Edge {
        final int to, rev;
        long residual;
        Edge(int to, int rev, long residual) {
            this.to = to; this.rev = rev; this.residual = residual;
        }
    }

    private final List<List<Edge>> graph;
    EdmondsKarp(int n) {
        if (n <= 0) throw new IllegalArgumentException("n must be positive");
        graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    }

    void addEdge(int u, int v, long capacity) {
        if (u < 0 || u >= graph.size() || v < 0 || v >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (u == v) throw new IllegalArgumentException("self-loop");
        if (capacity < 0) throw new IllegalArgumentException("negative capacity");
        Edge forward = new Edge(v, graph.get(v).size(), capacity);
        Edge reverse = new Edge(u, graph.get(u).size(), 0L);
        graph.get(u).add(forward);
        graph.get(v).add(reverse);
    }

    private boolean bfs(int source, int sink, int[] parentV, int[] parentE) {
        Arrays.fill(parentV, -1);
        parentV[source] = source;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(source);
        while (!queue.isEmpty()) {
            int u = queue.remove();
            for (int i = 0; i < graph.get(u).size(); i++) {
                Edge edge = graph.get(u).get(i);
                if (edge.residual == 0 || parentV[edge.to] != -1) continue;
                parentV[edge.to] = u;
                parentE[edge.to] = i;
                if (edge.to == sink) return true;
                queue.add(edge.to);
            }
        }
        return false;
    }

    long maxFlow(int source, int sink) {
        if (source < 0 || source >= graph.size() || sink < 0 || sink >= graph.size()) {
            throw new IndexOutOfBoundsException("vertex out of range");
        }
        if (source == sink) throw new IllegalArgumentException("source == sink");
        int[] parentV = new int[graph.size()];
        int[] parentE = new int[graph.size()];
        long total = 0L;
        while (bfs(source, sink, parentV, parentE)) {
            long bottleneck = Long.MAX_VALUE;
            for (int v = sink; v != source; v = parentV[v]) {
                bottleneck = Math.min(bottleneck,
                    graph.get(parentV[v]).get(parentE[v]).residual);
            }
            for (int v = sink; v != source; v = parentV[v]) {
                Edge edge = graph.get(parentV[v]).get(parentE[v]);
                edge.residual -= bottleneck;
                graph.get(edge.to).get(edge.rev).residual += bottleneck;
            }
            total = Math.addExact(total, bottleneck);
        }
        return total;
    }

    public static void main(String[] args) {
        EdmondsKarp flow = new EdmondsKarp(6);
        long[][] edges = {
            {0,1,16}, {0,2,13}, {1,2,10}, {2,1,4}, {1,3,12},
            {2,4,14}, {3,2,9}, {4,3,7}, {3,5,20}, {4,5,4}
        };
        for (long[] edge : edges) flow.addEdge((int) edge[0], (int) edge[1], edge[2]);
        if (flow.maxFlow(0, 5) != 23L) throw new AssertionError();
    }
}