Project Solution

In this programming assignment, you will implement specified algorithms for computing a maximum flow in a flow network.   You program  should read  in the  flow network  from an ASCII file named input.txt and write the output to an ASCII file named output.txt.  The first line of input.txt contains two  integers  nV  and nE,  which are the  number  of vertices  and number  of weighted edges in the flow network  G (a directed  graph).   The  second line of input.txt  contains  three  integers  s,  t, and k, where s and t denote the source node and the destination node, and k is a positive integer (for checking your program).   The next  nE  lines each contain  three  integers  u, v, and capacity, where u and  v are the  start  and  end vertices  of the  corresponding  edge and  capacity is the  capacity  of that  edge.  The vertices are numbered  from 1 to nV .  The edges are numbered  from 1 to nE.  For example, the following input  file specifies a flow network with 4 vertices and 5 edges.

 

4
5
 
1
4
3
1
2
4
1
3
1
2
3
5
2
4
1
3
4
4
 

For this example, the source node is 1, the destination node is 4, and k = 3.  The edge from 1 to

2 has capacity  4. The edge from 1 to 3 has capacity  1. The edge from 2 to 3 has capacity  5. The edge from 2 to 4 has capacity  1. The edge from 3 to 4 has capacity  4.

On reading the input,  your program should do the following.

 

• Initialize  your chosen data  structure for the  graph  (your  choices will be between  adjacency list and adjacency matrix)  with dynamic memory allocation.

 

• Compute  the  maximum  flow using  an  augmenting  path  algorithm,  where  you  compute  a shortest  path  (in hops) in the residual graph as the augmenting  path.

 

• Output the augmenting  path  computed  during  the kth  iteration  of your algorithm.   Output the  maximum  flow computed.   Here you need to output the  value of the  maximum  flow, as well as the positive flows on the edges. For a positive flow f (x, y) on edge (x, y), there should be a corresponding  line in the form of x y f (x, y).

 

 

 

• Output the corresponding  min-cut  and its capacity.  Here you need to output the capacity  of the min-cut,  as well as the cut itself.

 

For the sample input,  your program should generate the following output.

 

The augmenting path at iteration 3 is

1 2 3 4

 

 

Flow value=5

The max-flow is

1
2
4
1
3
1
2
3
3
2
4
1
3
4
4
 

 

Min-cut capacity=5

The min-cut is

1

2, 3, 4

 

Grading  policies:  You should use the  programming  language  C++.  Your program  should be working on general.asu.edu,  as it will be graded there.  You will need to submit  it electronically  at the class web-site.

 

(10 pts)  You should have a module that constructs  the residual graph.  The input  to this module will be the flow graph and the current flow. The output of this module will be the residual graph.

 

(10 pts)  You should have a module that  computes  the augmenting  path.  The input  to this module is the residual graph.  The output of this module is the augmenting  path.

 

(10 pts)  You should have a module that  updates  the flow. The input to this module is the augmenting path,  together  with the current flow and the flow network.  The output of this module is the updated  flow.

 

(10 pts)  You should have a module that  computes  a min-cut  when there  is no augmenting  path  for the current flow.

 

(10 pts)  You should have a module for input and output. You also need to have a driver for the overall program,  and provides a Makefile.

 

 

 

Extra Credit Work

You can earn up to an extra  30 pts on this project by doing the following.

 

 

(15 pts)  Write a report  to carefully describe the algorithms  you implemented  and analyze their worst- case  time  complexities.    In  particular, you  need  to  state  why  you  are  choosing the  data structures in terms  of improving worst-case time complexities.  Why are the data  structures you used are better  than  other options?

 

(15 pts)  Implement  another  variant of the  max-flow algorithm,  where  the  augmenting  path  is the widest path  in the residual graph.  Compare the two algorithms  with randomly generated test cases, and compare the performance, in terms of (1) the number of augmenting  paths  needed, and (2) the running  time.

 

Please note that you  have to typeset  your report using either LATEX or  Microsoft Word. Hand-written report will  not be  graded. You need to submit a single electronic file  at the digital drop box.