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作业君