1    The Ford-Fulkerson Algorithm

You’ll implement Ford-Fulkerson, to find the maximum flow 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;

ArrayList<Edge>  adjlist;

ArrayList<Edge>  adjlistResid;

public  Node(int  name)  {

this.name  =  name ;

this.adjlist  =  new  ArrayList<Edge>();

this.adjlistResid  =  new  ArrayList<Edge>();

}

public  void  add(Edge  edge)  {

this.adjlist.add(edge);

}

public  void  addResidualEdge(Edge  edge)  {

this.adjlistResid.add(edge);

}

}

This will let you build the residual graph for a flow using the same nodes as the flow 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 node’s 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, finding the bottleneck in that path, and augmenting the flow

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 flow in the graph.  Check also that the flow

out of the source node is equal to the flow 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 flows you are computing are valid. private  void  constructResidualGraph()