Java程序辅导

School of Computer Science & Software Engineering
The University of Western Australia
Crawley, Western Australia, 6009.
CRICOS Provider Code: 00126G
CITS3210 Algorithms Laboratory sheet 4
These exercises are worth 2.5% of your final grade and are due
at 5pm, Friday, October 5, 2012
1. Your task is to implement an algorithm to solve a maximal network flow problem
and apply it a network flow problem and a bipartite matching problem. You should
use the (new) class Graph and interface Flow.java to write a class FlowImp.java
that implements Flow. This class will contain
• a method, getMaxFlow which takes a graph, G, and the index of two vertices s
and t as parameters, and returns the maximal flow from s to t in the network
G, where the weights on the edges are assumed to be capacities of an edge.
This method should return a single integer which is the maximum flow from s
to t in the network.
• a method, getMaximumMatching, which takes an unweighted bipartite graph, G,
as a parameter, and returns number of pairs in a maximum bipartite matching
over that graph.
The class FlowTest has been provided to help you test your implementation. The
following is this output for a random graph with 6 vertices with 50% density.
Random flow network:
6
0 0 0 1 1 1
0 0 1 0 1 1
0 1 1 0 1 1
1 0 0 1 0 0
0 1 1 1 0 1
1 0 0 0 0 0
Max flow is 2
Random Bipartite Graph:
6
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 1 0 0
0 0 1 0 0 0
0 0 0 0 0 1
1 0 0 0 1 0
Max matching is 2
1
Note you should download the most recent version of the graph class with additional
methods for generating random bipartite graphs. We will use the convention that
odd vertices form one parition and even vertices form the other partition.
As an automated marker is used you should include print statements etc in your imple-
mentation. However, a test class FlowTest.java is available for your convenience. Submit
the file FlowImp.java to https://secure.csse.uwa.edu.au/run/cssubmit. There is
an automated script that will compile and run your code, and estimate your final mark.
2