def edmonds_karp(nodes, arcs, u, s, t):

 # assumes all capacities are finite

x_ts = 0

nU = len(nodes)*max(u.values())

new_arcs, r = build_residual(arcs, u)

adj = build_adjacency_list(nodes, new_arcs)

  mark = set([t])

  while t in mark:

  mark, pred = residual_bfs(adj, r, s)

  if t in mark:

  delta = nU

  j = t

  while pred[j] != 0:

  i = pred[j]

  if delta > r[(i,j)]:

  delta = r[(i,j)]

  j = i

  x_ts = x_ts + delta

  j = t

  while pred[j] != 0:

  i = pred[j]

  r[(i,j)] -= delta

  r[(j,i)] += delta

  j = i

  x = build_flows_from_residuals(arcs, u, r)

  return x_ts, x, mark

Discussion

The Edmonds-Karp (Edmonds and Karp, 1972) algorithm uses breadth first search (BFS) in the residual graph to find an augmenting path with the fewest possible arcs in each iteration. (Such a path is sometimes referred to as a “shortest augmenting path.”) This guarantees finite convergence and a polynomial runtime. It can be shown that Edmonds-Karp performs at most O(nm) augmentations, and each augmentation costs O(m) for the BFS (plus an inconsequential O(n) for finding the the capacity of the augmenting path and then updating the residual capacities along that path), for a total runtime of O(nm2).

There are other polynomial-time algorithms for the maximum flow problem (Chapter 7 in AMO reviews them), but this one is probably the most straightforward.

Exercise: Implement edmonds_karp() and test it on the network from exercise 6.12 in AMO, as illustrated in Figure 6.22(a). (You can ignore the x values; just build the nodes, arcs, and capacities.) You already have a version of build_adjacency_list() from a prior assignment that should work fine for this one, but this exercise will require writing supporting code in the form of:

1) build_residual(), which builds a new set of arcs, adding reverse arcs if they don’t already exist, and initializes the residual capacities, r, based on the capacities, u, (where new reverse arcs have capacity zero),

2) residual_bfs(), which performs breadth first search, but only uses arcs with positive residual capacity, and 

3) build_flows_from_residuals(), which creates the flow values, x, on original arcs based on their capacities, u, and the final residual capacities, r.

Hints:

1) When building the residual graph, create an empty list of arcs, new_arcs, and an empty dictionary of residual capacities, r. Loop through the original arc list, appending each arc to the list of new arcs and setting their residual capacities to their original capacities. 

For each of those original arcs, if the reverse arc is not already in the set of arcs, append it to the list of new arcs and set its residual capacity to zero. 

Code hint: if (j,i) not in arcs:

2) BFS on the residual graph is almost identical to normal BFS, but it has an extra argument: the dictionary of residual capacities. When you check to see if a node is not yet marked, you also need to check to see if the arc leading you to that node has positive residual capacity. If either test fails, skip it.

Code hint: if j not in mark and r[(i,j)]>0:

3) The main idea when building the solution from the residuals is that, for any arc in the original network, there will only be flow on the arc if the residual capacity is strictly less than the original capacity. (The residual capacity can actually be greater than the original capacity: how? And why does this mean there is no flow along this arc?)

Code hint: if r[(i,j)] < u[(i,j)]:

Data