Algorithms tick 3

Algorithms Tick 3: maximum flow with Ford-Fulkerson / Edmonds-Karp

In this tick you will build a Ford–Fulkerson implementation from scratch. In fact you will implement the Edmonds–Karp variant of Ford–Fulkerson, which uses breadth first search (BFS) to find augmenting paths, and which has \(O(V E^2)\) running time.

The input data is a network, i.e. a directed graph where each edge is labelled with a capacity. You can see some sample networks here (CSV files, with a header row, and three columns; vertices are labelled by integers, and capacities are also integer):

Your task has two parts: finding a maximum flow from a given source to a given sink, given the capacity constraints on each edge; and finding a minimum cut. A cut is a set of vertices \(S\), including the source but not including the sink, and you need to find a cut whose capacity (i.e. the sum of capacities of edges from \(S\) to \(\bar{S}\)) is equal to the maximum flow.

Step 1: BFS path finder

The first step is to implement a BFS-based path finder. This finds the shortest path on an unweighted graph, i.e. the shortest path as measured by number of edges rather than by edge weights. (You will have to work out which graph to run BFS on, based on the edge capacities and the flow you’ve computed so far.)

For every vertex \(v\), you will need to store a boolean value that indicates whether \(v\) is reachable from the source, and also a come_from pointer that links \(v\) to the previous vertex on a shortest path.

Step 2: Ford-Fulkerson

The next step is to implement Ford–Fulkerson. In each iteration, you should find an augmenting path using your BFS path finder, work out how much flow to add along that path, and add it. Your algorithm should terminate when the BFS path finder is no longer able to find an augmenting path from source to sink.

Step 3: Finishing up

After running Ford–Fulkerson, you will need to return (1) the flow you computed on each edge, (2) the total value of the flow, (3) a minimum cut. A suitable minimum cut is simply the set of vertices reachable from the source, in the final iteration of BFS when it failed to find a path.


You may submit your answer on Moodle in either Python or Java.

Submission (Python)

Submission filename: maxflow.py

Please submit a source file maxflow.py that contains the following function:

'''
Args:
    capacity: a dictionary {(from,to):edge_capacity, ...}
    s, t: the source and sink vertices
Returns a triple  (flow_value, flow, cutset)  where:
    flow_value: the value of the flow, i.e. a number
    flow: a dictionary {(from,to):flow_amount, ...}
    cutset: a list or set of vertices
'''
compute_max_flow(capacity, s, t)

If you want to test your code, here’s a simple snippet, which reads edge capacities from a CSV (or you can use pandas.read_csv).

import csv
with open('flownetwork_00.csv') as f:
    rows = [row for row in csv.reader(f)][1:]
capacity = {(u, v): int(c) for u,v,c in rows}

Submission (Java)

Submission filename: MaxFlowFinder.java.

Please submit a class MaxFlowFinder that implements the interface uk.ac.cam.cl.tester.Algorithms.MaxFlow:

package uk.ac.cam.cl.tester.Algorithms;

public interface MaxFlow {
    // compute a max flow from s to t, in network g
    void maximize(LabelledGraph g, int s, int t);

    // return the flow value, the flow on each edge, and a cut
    int value();
    Iterable<LabelledGraph.Edge> flows();
    java.util.Set<Integer> cut();
}

The class LabelledGraph (also in uk.ac.cam.cl.tester.Algorithms) stores the network, and lets you get the capacity of an edge, and iterate through the edges. It also provides a constructor that can initialize a graph from a URL, or from a matrix. The subclass LabelledGraph.Edge is a triple (from, to, label), which is used in two ways: it describes the capacity of each edge in the network g, and you should use it to specify the flow on each edge as reported by your flows() function.

To get started, you can paste code from uk.ac.cam.djw1005.Algorithms.Tick3.MaxFlowFinderBase. This code sets up an adjacency matrix flow[][] to store the flow, and a vector cut[] to store the set of reachable vertices, and it implements value(), flows(), and cut(). You still have to implement breadth first search in getAugmentingPath(src,dst), as well as the main Ford–Fulkerson algorithm in maximize(g,s,t)!

Please note that your code must be in your own package, named after your CRSID, for example uk.ac.cam.spqr1.Algorithms.Tick3. You will therefore have to import MaxFlow and LabelledGraph from uk.ac.cam.cl.tester.Algorithms. The tester will use its own copy of those two files.

If your code gets stuck in an infinite loop, the tester will time out after 32 seconds, and it won’t show any output at all. If this seems to be a problem, use an iteration counter inside any dangerous loops, e.g. if (++iter > 1000) System.exit(1). Your code will still fail, but at least you’ll see feedback about what tests were running!


The MaxFlow interface asks for the flow as an Iterable<Edge>, which means you’re not tied to the adjacency matrix used in MaxFlowFinderBase. Can you implement your algorithm using an adjacency list representation instead?