CS 330: Programming Assignment 4
Ford-Fulkerson for Maximum Flow
Deadline: Tuesday, December 15 at 11:59 pm (No late submissions!)
In this exercise you will implement the Ford-Fulkerson algorithm for solving the maximum flow
problem. Given a directed graph with positive capacities on the edges, as well as source and sink
vertices, find the maximum flow. The algorithm is described in Section 7.1 of Algorithm Design,
with the main pseudocode on page 344. Your code should run in at most O(mC) time, where m is
the number of edges and C is an upper bound on the value of the flow, the sum over the capacities
of edges exiting the source.
Tips
• The algorithm itself is simple: while you can, find an augmenting path in the residual graph
and augment it. Before starting, take some time to think about how you will keep track of
the necessary information. For instance, you’ll need to be able to keep track of which edges
in the residual graph are “forward” and which are “backward.”
• You need to be able to find simple s-t paths in the residual graph. BFS will work great here:
you can adapt your code from the first programming assignment or write it from scratch.
Submission Format
We will be providing starter code in Python titled ford fulkerson.py (when you submit to Grade-
scope, this name must match exactly). If you would prefer to code this assignment in Java, you
may, but we will not provide starter code. On ford fulkerson.java reading a text file input and
creating a text file output containing your solution following the specifications below. You may
submit other files containing additional functions and classes. The autograder will put your code
in the same directory as input, call it from the command line, and look for the file output in the
same directory.
There are 15 tests to pass on Gradescope. The assignment is graded out of 15 points:
1. Tests 1 and 2 check file names and compilation, and are worth 0 points.
2. Tests 3-5 are basic examples and are each worth 0 points. Their input files are available on
Gradescope in a file called pa4 inputs.zip for local debugging.
3. Tests 6-10 are worth 1 point each. Their input files are also available in pa4 inputs.zip.
4. Tests 11-15 are worth 2 points each, and their input files will not be made publicly available.
Input
The input format is similar to that of the other directed graph problems we’ve seen in previous
programming assignments. The file input will have m + 4 lines specifying a directed, weighted
graph:
1. The first line will be N , the number of vertices.
1
2. The second line will be m, the number of edges.
3. The third line will be the index s, specifying the source.
4. The forth line will be the index t, specifying the sink.
5. Every row after that will specify an edge by giving the starting node, the ending node, and
the capacity.
The capacities will all be positive integers. As in the book, you can assume that s will have no
edges coming into it, and t will have no edges leaving it. The vertices will be indexed 0 to n− 1.
Output
Your algorithm must create a text file output specifying the maximum flow, edge by edge. On each
line write the starting vertex, the ending vertex, and the value of the flow across that edge, each of
which is an int separated by commas. The value of the flow on an edge may be zero. Your output
file should have m lines; they can be written in any order.
Example begins on the next page.
2
Example
Consider the following directed, weighted graph. It is the first example in the lecture slides
lect 11 19 FF.pdf, available on Piazza. The source is vertex 0 and the sink is vertex 7. The
maximum flow has a value of 28.
0 2
1
3
4
5
6
7
10
5
15
9
15
4
8
4
15
10
15
10
15
6
10
input:
8
15
0
7
0,1,10
0,2,5
0,3,15
1,2,4
2,3,4
1,4,9
1,5,15
2,5,8
6,2,6
3,6,15
4,5,15
5,6,15
4,7,10
5,7,10
6,7,10
The output file is on the next page.
3
output:
0,1,10
0,2,5
0,3,13
1,2,0
2,3,0
1,4,9
1,5,1
2,5,8
6,2,3
3,6,13
4,5,0
5,6,0
4,7,9
5,7,9
6,7,10
4

欢迎咨询51作业君