Dinic's max flow algorithm implementation

dinic_max_flow.js

class Graph {
    constructor(verticies, edges) {
        this.verticies = verticies
        this.adj = new Array(verticies)
        for (let i = 0; i < verticies; i++) {
            this.adj[i] = []
        }

        edges.forEach(edge => {
            const forward = {v: edge.to, capacity: edge.weight, flow: 0}
            const residual = {v: edge.from, capacity: 0, flow: 0, residual: forward}
            forward.residual = residual
            this.adj[edge.from].push(forward)
            this.adj[edge.to].push(residual)
        })
        this.levels = new Array(verticies).fill(-1)
        this.next = new Array(verticies)
    }

    calcMaxFlow(src, dst) {
        // Dinic's alogrithm
        let maxFlow = 0

        while (this.bfs(src, dst)) {
            let flowIncrease = 0
            this.next.fill(0)
            do {
                flowIncrease = this.dfs(src, dst)
                maxFlow += flowIncrease
            } while (flowIncrease > 0)
        }

        return maxFlow
    }

    dfs(src, dst, u = src, bottleneck = 1) {
        if (u === dst) {
            return bottleneck
        }

        for (;this.next[u] < this.adj[u].length; this.next[u]++) {
            const edge = this.adj[u][this.next[u]]
            const residual = edge.capacity - edge.flow
            if (this.levels[edge.v] > this.levels[u] && residual > 0) {
                const flow = this.dfs(src, dst, edge.v, Math.min(bottleneck, residual))
                if (flow > 0) {
                    edge.flow += bottleneck
                    edge.residual.flow -= bottleneck
                    return bottleneck
                }
            }
        }

        return 0
    }

    bfs(src, dst) {
        this.levels.fill(-1)
        this.levels[src] = 0
        const q = [src]
        
        while (q.length > 0 && this.levels[dst] === -1) {
            const u = q.pop()
            for (let i = 0; i < this.adj[u].length; i++) {
                const nextEdge = this.adj[u][i]
                if (
                    (nextEdge.capacity - nextEdge.flow) > 0 && 
                    this.levels[nextEdge.v] === -1
                ) {
                    this.levels[nextEdge.v] = this.levels[u] + 1
                    q.push(nextEdge.v)
                }
            }
        }

        return this.levels[dst] !== -1
    }
}