// -*- coding: utf-8; indent-tabs-mode: nil -*-
\ALGORITHM{Edmonds–Karp} \WITH
    \INPUT{
      \expr{graph}:  \expr{graph[v]} should be the list of edges coming out of vertex \expr{v} in the
              original graph and their corresponding constructed reverse edges
              which are used for push-back flow.
              Each edge should have a capacity \expr{cap}, \expr{flow}, source \expr{s} and sink \expr{t} 
              as parameters, as well as a pointer to the reverse edge \expr{rev}.
      \expr{s}:      Source vertex
      \expr{t}:      Sink vertex}
    \OUTPUT{
      \expr{flow}:  Value of maximum flow)}
\IS
    flow := 0
    \REPEAT
        /* Run a breadth-first search (bfs) to find the shortest s-t path.
           We use 'pred' to store the edge taken to get to each vertex,
           so we can recover the path afterwards. */
        q := queue()
        q.push(s)
        pred := array(graph.length)
        \WHILE not empty(q) and pred[t] = null \DO
            cur := q.pop()
            \FOR \text{Edge} e in graph[cur] \DO
                \IF pred[e.t] = null and e.t != s and e.cap > e.flow \THEN
                    pred[e.t] := e
                    q.push(e.t)
                \END IF
            \END FOR
        \END WHILE
        \IF not (pred[t] = null) \THEN
            /* We found an augmenting path.
               See how much flow we can send */
            df := ∞
            \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
                df := min(df, e.cap - e.flow)
            \END FOR
            /* And update edges by that amount */
            \FOR (e := pred[t]; e != null; e := pred[e.s]) \DO
                e.flow  := e.flow + df
                e.rev.flow := e.rev.flow - df
            \END FOR
            flow := flow + df
        \END IF
    \UNTIL pred[t] = null      \REM i.e., until no augmenting path was found
    \RETURN flow
\END ALGORITHM {Edmonds–Karp}