COMP572 -- Fall 2007

MAX-FLOW Project Specification

A: (1 person) Implement Ford-Fulkerson algorithm

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

• A graphical method for inputting/editing a flow network,  e.g., vertices, edges, capacities, denoting the source and sink
• A graphical method for illustrating the algorithm.  That is,  it should show the residual networks and augmenting flows in each step and
• shows the corresponding Max-Cut at the conclusion of the algorithm

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

• A graphical method for inputting/editing  an unweighted bipartite graph
• A graphical transformation of the bipartite matching problem to a flow network
• A graphical method of illustrating how FF works on the flow network.  At every stage your GUI should also indicate the current matching and the augmenting path (relative to that matching) constructed.
   

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 2, 2007 and last revised on 11/02/2007 13:23 +0800

Return to main project page