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.
Please submit a source file maxflow.py on Moodle. It should contain 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}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.