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 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)  {



public  void  addResidualEdge(Edge  edge)  {




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

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()

For the current graph and flow, construct the residual graph.  As a first 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 find 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 find 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 specified 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.

4    Graduate Students

Students taking the course for graduate credit, and undergraduates for a little bit of extra credit: implement the scaling max-flow algorithm, shown on pp.  353-354.  Do this instead of the basic Ford-Fulkerson.  To do this, implement the following function:

void  constructResidualGraph(int  delta)

This will build a residual graph for the current ow with only those edges having a residual-ow value greater

or equal to the delta parameter.