Take the code you wrote for the Ford-Fulkerson algorithm for the maximum flow on a directed graph with capacities, and implement scaling on top of this code. You write a function
void maximum flow scale(int n, int s, int t, int *capacity, int *flow)
with the same arguments as the function maximum flow in Homework 3:
- n: the number of vertices of the graph,
- s: the start vertex,
- t: the target vertex
- capacity: the matrix of edge capacities.
- flow: the matrix used to return the maximum flow.
Scaling is a method to speed up the Ford-Fulkerson Algorithm for flows with large integer capacities. You construct a sequence of auxiliary capacities CAPi
from the original
capacities CAP0 by halving all capacities (integer division: rounding downward). Let CAPk be the last of these matrices which is not all zero. You solve first the problem with capacities
CAPk with your Ford-Fulkerson code; then you take the flow you found, double all flow values,and take that as initial flow for the capacities CAPk−1, and solve the problem for those capacities. You continue this doubling until you are back at the original
capacities. Since each step has a cut of size at most n − 1, each of the intermediate flow problems can augment at most n − 1 times, and there are only log(MaximumCapacity) many intermediate problems.