Write code that finds a maximum flow in a directed graph, using the Ford-Fulkerson

algorithm on capacities given as matrix

void maximum flow(int n, int s, int t, int *capacity, int *flow)

Your function has the following arguments:

- 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.

The vertices are numbered from 0 to n-1, so s and t are numbers in that range.

capacity, flow are a pointers to n ~ n matrices of nonnegtive integers; the array el-

ement capacity[i][j] is the capacity of the edge from i to j, and can be accessed

as *(capacity + i*n + j). Your function should return in the matrix flow the flow

values of the maximum flow from s to t. The flow variable of your function points to

space allocated for the flow matrix.

Your function will need at least the following auxiliary arrays:

- an n ~ n matrix to hold the current flow,

- an n ~ n matrix to hold the current residual capacities,

- an array to maintain which vertices are already visited in the search of an augmenting

path from s to t with positive residual capacity.

You have to allocate the auxiliary arrays. You can use either BFS or DFS for the search

of the augmenting path.

Please use the test code below. Thank you.

Here is the test code:

int main(void)

{ int cap[1000][1000], flow[1000][1000];

int i,j, flowsum;

for(i=0; i< 1000; i++)

for( j =0; j< 1000; j++ )

cap[i][j] = 0;

for(i=0; i<499; i++)

for( j=i+1; j<500; j++)

cap[i][j] = 2;

for(i=1; i<500; i++)

cap[i][500 + (i/2)] =4;

for(i=500; i < 750; i++ )

{ cap[i][i-250]=3;

cap[i][750] = 1;

cap[i][751] = 1;

cap[i][752] = 5;

}

cap[751][753] = 5;

cap[752][753] = 5;

cap[753][750] = 20;

for( i=754; i< 999; i++)

{ cap[753][i]=1;

cap[i][500]=3;

cap[i][498]=5;

cap[i][1] = 100;

}

cap[900][999] = 1;

cap[910][999] = 1;

cap[920][999] = 1;

cap[930][999] = 1;

cap[940][999] = 1;

cap[950][999] = 1;

cap[960][999] = 1;

cap[970][999] = 1;

cap[980][999] = 1;

cap[990][999] = 1;

printf("prepared capacity matrix, now executing maxflow code ");

maximum_flow(1000,0,999,&(cap[0][0]),&(flow[0][0]));

for(i=0; i<=999; i++)

for(j=0; j<=999; j++)

{ if( flow[i][j] > cap[i][j] )

{ printf("Capacity violated "); exit(0);}

}

flowsum = 0;

for(i=0; i<=999; i++)

flowsum += flow[0][i];

printf("Outflow of 0 is %d, should be 10 ", flowsum);

flowsum = 0;

for(i=0; i<=999; i++)

flowsum += flow[i][999];

printf("Inflow of 999 is %d, should be 10 ", flowsum);

printf("End Test ");

}