Description
Submit your Java codes via Blackboard. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
-
(25) [Capacity-scaling max flow: programming] Write a program code implementing the Capacity Scaling Max-Flow algorithm discussed in class (see the lecture slide and the textbook page 353) and run the program against the flow network shown below.
The program should give output as required below.
Every time a new augmenting path is found during the -scaling phase of program execution, output the current capacity-scale ( ) value and the augmenting path as well as the bottleneck residual capacity of the path as follows – e.g., “Capacity-scale 8: augmenting path s a c
t with bottleneck 3 found.”
At the end of each -scaling phase, output that no more augmenting path exists, for example,
“Capacity-scale 8: no augmenting path found.”
At the end of the program, output the resulting maximum flow value (e.g., “Maximum flow
value = 100”) and the minimum cut (e.g., “Minimum cut = ({s, a, c}, {b, d, t})”). Represent the flow network using a data structure (e.g., adjacency list, adjacency matrix, edge list) of your choice. Your program should work correctly and display the output correctly, or there will be no point given. Besides, your program codes should be easy to read; many points will be deducted for codes hard to read.
