COMP572 -- Fall 2004
You should implement the Edmonds-Karp version of the Ford Fulkerson Algorithm.
Input:
The input is read from standard input or a file (your documentation should
indicate which) The first line contains an integer n
where n is the number of nodes of the network. The nodes are numbered from 0 to
n-1. Each of the next n lines of the input contains n integers. The j-th integer
in the i-th line indicates the capacity of the directed edge from node i to node
j. The source and sink will always be 0 and n-1 respectively.
You can assume:
1. n is between 2 and 50.
2. All the capacities are less than 1,000,000,000.
3. The max-flow is less than 1,000,000,000.
Output:
Print out the value of the max-flow (which is always an integer) in the first
line.
Print out the complete flow of the network in next n lines as follow: The j-th
integer in the i-th line is the flow value from node i to node j. All the values
must be integers. If the flow from u to v is f, then print out 0 instead of -f
for the flow from v to u.
Print out the corresponding min-cut in next two lines as follow: The first line
should be a sorted sequence of nodes containing 0 and the second line should be
a sorted sequence of nodes containing n-1. These two sets of integers correspond
to the min-cut.
Note that the flow values and the cut may not be unique. You just need to output
one of them.
Follow the format as sample output. Don’t print any other text character. Always
use space to separate two values.
Sample input: (Maximum Flows, page 19)
6 0 16 13 0 0 0 0 0 10 12 0 0 0 4 0 0 14 0 0 0 9 0 0 20 0 0 0 7 0 4 0 0 0 0 0 0
23 0 11 12 0 0 0 0 0 0 12 0 0 0 1 0 0 11 0 0 0 0 0 0 19 0 0 0 7 0 4 0 0 0 0 0 0 0 1 2 4 3 5
B: (2 person) Implement (A) and a graphical user interface (GUI) for the FF algorithm.
Your program should also include a GUI that includes
Note that, even with the GUI, your program should also permit inputting text data via standard input or from a file following the specifications from part (A).
For your GUI you may assume that there are at most n=20 vertices in the graph.
C: (3 person) Implement part (B) along with another GUI that implements Max-Cardinality matching of Bipartite graphs using the FF algorithm
Your program should include another GUI (could either be separate or combined with the one from part B) that provides
For your GUI you may assume that there are at most n=20 vertices on edge side of the bipartite graph.
This page was released on November 19, 2004 and last revised on 11/19/2004 13:38 +0800