import { StackQueue } from '../data_structures/queue/stack_queue'
export default function edmondsKarp(
graph: [number, number][][],
source: number,
sink: number
): number {
const n = graph.length
const residualGraph: [number, number][][] = Array.from(
{ length: n },
() => []
)
for (let u = 0; u < n; u++) {
for (const [v, cap] of graph[u]) {
if (cap > 0) {
residualGraph[u].push([v, cap])
residualGraph[v].push([u, 0])
}
}
}
const findAugmentingPath = (parent: (number | null)[]): number => {
const visited = Array(n).fill(false)
const queue = new StackQueue<number>()
queue.enqueue(source)
visited[source] = true
parent[source] = null
while (queue.length() > 0) {
const u = queue.dequeue()
for (const [v, cap] of residualGraph[u]) {
if (!visited[v] && cap > 0) {
parent[v] = u
visited[v] = true
if (v === sink) {
let pathFlow = Infinity
let current = v
while (parent[current] !== null) {
const prev = parent[current]!
const edgeCap = residualGraph[prev].find(
([node]) => node === current
)![1]
pathFlow = Math.min(pathFlow, edgeCap)
current = prev
}
return pathFlow
}
queue.enqueue(v)
}
}
}
return 0
}
let maxFlow = 0
const parent = Array(n).fill(null)
while (true) {
const pathFlow = findAugmentingPath(parent)
if (pathFlow === 0) break
let v = sink
while (parent[v] !== null) {
const u = parent[v]!
const forwardEdge = residualGraph[u].find(([node]) => node === v)!
forwardEdge[1] -= pathFlow
const reverseEdge = residualGraph[v].find(([node]) => node === u)!
reverseEdge[1] += pathFlow
v = u
}
maxFlow += pathFlow
}
return maxFlow
}