chapel-lang/chapel

/* Function that implements the Ford-Fulkerson Max Flow algorithm
 * 
 * Return: the maxium flow from s to t
 * resGraph: an adjacency matrix that contains the capacities
 * s: source vertex
 * t: sink vertex
 */

proc FordFulkerson(resGraph: [], s: int, t: int) 
{ 
  // array that stores the path by BFS
  var parent: [0..V-1] int;
  var max_flow: int = 0; // no flow initially

  while (bfs(resGraph, s, t, parent)) {   
    // Find the minimum residual capacity of the edges
    var path_flow: int = max(int);
    var q = new list((int, int));  

    var v: int = t;
    while (v != s) {
      q.append((v, parent[v]));
      v = parent[v];
    }   

    const Space = {0..q.size-1}; 
    var D = Space dmapped Block(Space);
    var A: [D] (int, int) = q.toArray();

    forall i in A with (min reduce path_flow) do
      path_flow = min(path_flow, resGraph[i(1), i(0)]);

    // Update residual capacities of the edges and reverse edges along the path
    forall i in A with (ref resGraph) {
      resGraph[i(1), i(0)] -= path_flow;
      resGraph[i(0), i(1)] += path_flow;
    }

    // Add path flow to overall flow
    max_flow += path_flow;

  }
  return max_flow;
} //End of the FordFulkerson function