Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Programming Assignment #7

CS224 Spring 2022

1    The Ford-Fulkerson Algorithm

You’ll implement Ford-Fulkerson, to ﬁnd the maximum ﬂow in a network.  You may work alone or with a partner. Graduate students will also implement an enhanced version of Ford-Fulkerson

1.1    Data Structures

I will give you use Node, Edge, and Graph classes. The Node class is more complex now:

public  class  Node  {

int  name;

public  Node(int  name)  {

this.name  =  name ;

}

}

}

}

This will let you build the residual graph for a ow using the same nodes as the ow network itself.

The Edge class is also more complex:

public  class  Edge  {

int  capacity;

int  flow;

boolean  backward;

Node  n1;

Node  n2;

public  Edge(Node  n1,  Node  n2,  int  capacity,  boolean  backward)  {

this(n1,  n2,  capacity,  0,  backward);

}

public  Edge(Node  n1,  Node  n2,  int  capacity,  int  flow)  {

this.n1  =  n1;

this.n2  =  n2;

this.capacity  =  capacity;

this.flow  =  flow;

this.backward  =  false;

}

public  Edge(Node  n1,  Node  n2,  int  capacity,  int  flow,  boolean  backward)  {

this.n1  =  n1;

this.n2  =  n2;

this.capacity  =  capacity;

this.flow  =  flow;

this.backward  =  backward;

}

public  String  toString()  {

String  s  =  n1.name  +  "  ->  "  +  n2.name  +  "  (c="  +  capacity  +  ",  f="  +  flow  +  ")"; return  s;

}

}

The backward member variable is relevant only for residual graphs.

Do not make any changes to Node.java or Edge.java!

Note:  It’s customary in the examples of graphs for CS224 to give the nodes a name” that is an integer in the range 1, 2, ..., n, where n is the number of nodes in the graph.  This is slightly awkward if we want

to use an array to hold the nodes and use the name of the node as an array index, since Java arrays are

zero-indexed.  For example:  suppose I want to keep an array boolean[]  visited to show whether or not a

node has been visited during graph traversal.  In order to use the nodes name as an index, I need to allocate

the array to be of size n + 1. Then, to check whether node s has been visited, I look at visited[s.name].

1.2    Functions

Implement the following functions on Graph

public  int maxFlow(Node  s,  Node  t)

Implement the basic Ford-Fulkerson algorithm, with the loop of constructing the residual graph, selecting a source-to-sink path in the residual graph, ﬁnding the bottleneck in that path, and augmenting the ﬂow

along that path. Terminate the iteration when appropriate. Assume that s is the source node and t is the sink node.

public  boolean  checkFlow(Node  s,  Node  t)

This will check the capacity and conservation conditions for a ow in the graph.  Check also that the ow

out of the source node is equal to the ﬂow into the sink node. Return true if the conditions are met; return false otherwise.  Also, if a condition is not met, then print out information describing the problem.  This

function is really to help you debug—to help you know that the ﬂows you are computing are valid. private  void  constructResidualGraph()

For the current graph and ﬂow, construct the residual graph.  As a ﬁrst step, call adjlistResid.clear() on each node in the graph.

private  void  augment(ArrayList<Edge>  path)

Augment the given path in the graph.  To do this, you’ll have to ﬁnd the bottleneck in the path, so write this function:

private  int  findBottleneck(ArrayList<Edge>  path)

Find the bottleneck on the given path.

I’ve given you the following function in the starter code for Graph.java:

private  ArrayList<Edge>  findPathInResid(Node  s,  Node  t)

This will ﬁnd a path from node s to node t in the residual graph. If the length of the list it returns is zero, then there is no path in the residual graph between the two speciﬁed nodes.

2    Testing and Development

I’ve also given you a Main class that can use. Main has two test cases on which you can test your code.

I show the output from the tests in testOne.out, testTwo.out. My output shows a lot of information about

the processing. You don’t have to print similar output, but it will help you debug your code. Do not implement additional functions—just implement the ones listed above.

If you cant get each function to work completely, implement the functions that you can.

3    What to Submit

Submit your Graph.java le and your Main.java le.