Description
1 Objectives
In this assignment, you will implement an algorithm that computes the maximum flow possible in a flow network digraph. A flow network can represent a network of pipelines having different flow rates. Please refer to the diagram in Figure 1 for an example of a flow network. In a flow network, there are two special nodes called the source and destination nodes (marked as S and D in Figure 1).
Material such as oil fluids can propagate through the network starting from the source S and flow into the destination node D. Intermediate nodes (i.e. 1 to 7 in the example) can represent pumping stations. Figure 1: A sample flow network
1.1 Constraints
Since a flow network is a special kind of network subject to physical limitations, flow and capacity constraints do apply. Every edge ei,j or pipeline connected by vertices vi and vj has a maximum capacity of ci,j .
Hence, due to this physical capacity limitation, any substance flowing through pipeline ei,j must have a flow of fi,j that is between 0 and ci,j (i.e. 0 ≤ fi,j ≤ ci,j ). Referring back to Figure 1, e0,2 has a flow of f0,2 = 11 and a capacity of 12. Since f0,2 ≤ c0,2, this is a valid flow. Next, suppose three pipelines or edges meet at a single node and two pipelines leave that node (consider e2,5, e3,5, e4,5, e5,6, e5,7).
Any substance flowing into a node must be equal to the substance flowing out of the node and this is called flow conservation. In Figure 1, f2,5 + f3,5 + f4,5 = 18 and f5,6 + f5,7 = 18 and more generally this can be expressed as P i∈V fi,j = P i∈V fj,i for all vj with the exception of S and D as these are source and sink nodes (generate or consume substance).
Finally, there is the notion of back flow. For instance, if there exists positive flow fi,j on edge ei,j , then it is possible for substance to flow in the opposite direction ej,i where 0 ≤ fj,i ≤ fi,j . If there is no substance in the pipeline then nothing can propagate in the opposite direction. However, if there is some material flowing through the pipe in one direction, then it is entirely possible for this material to flow in the opposite direction.
1.2 General Algorithm for Finding Maximum Flow in the Network
If you attempt to increase the flows on edges of the flow network provided in Figure 1, you will notice that this is not possible. Suppose you are increasing flow on e0,2 by 1 to 12. In order to satisfy flow conservation, the 1 flow on e2,5 must also increase by 1. This is impossible as this will violate the maximum capacity restriction on e2,5 (i.e. maximum flow possible through this edge is 11 not 12). Hence, if you attempt to increase the flow like this on every edge, you will realize that this is not feasible. For this reason, all flows listed in Figure 1 are the maximum possible flows throughout the flow network.
The amount of substance leaving from node 0 which is the source node is 23 and similarly the amount of substance entering the destination node 8 is also 23. For this reason, the maximum flow throughout this flow network is 23! In this assignment, you will implement a well known algorithm to compute the maximum flow throughout a flow network. In general, this algorithm is composed of the following steps: • Find a path p from S to D that consists of no edges with flow that is equal to the full capacity of the edge (i.e. fi,j 6= ci,j )
• Find the maximum flow that can be added to the path so that none of the edges in the path violate their flow capacity constraints • Add this flow to every edge in the path p • Repeat the above until no more paths exist in the graph from S to D to which more flow can be added This assignment is divided into two parts. In the first part, you will implement a breadth-first search algorithm to discover a path from S to D to which more flow can be added to all edges in this path. These paths will be referred to as augmenting paths. In the second part, you will implement code that calls on this path discovering algorithm repeatedly to add flow to the flow network until no more flow can be added.
You can assume that you are provided with the definitions to the Graph ADT and Edge class (you can assume that all the functions provided in the ”Graphs” lecture slides are available). An Edge is composed of the following members: • public int flow; • public int flowCap; Edge represents an edge and stores the current flow in that edge and the maximum capacity of that edge in the flow and flowCap members respectively. You will implement the function public int breadthFirstPathSearch(Graph FN, int s, int d) function.
This function uses breadth-first search to find an augmenting path connecting vertices s and d to which flow can be added without infringing on capacity constraints of the network. Since this is a breadth-first search algorithm, you will have to use a queue in your implementation. You can assume that all the interface functions associated with the LinkedListQueue are provided. In order to understand the general breadth-first path-finding algorithm, consider Figures 2, 3, 4.
Figure 2 illustrates the initial flow network which has no flow yet on any edges. The path-finding algorithm should find a path connecting s and d which are source and destination nodes that consists of no edges with flow being equal to the maximum edge capacity. The breadth-first search algorithm attempts to find such a path that has the shortest distance (i.e. smallest number of edges) from s to d. A breadth-first search algorithm will start from s and examine all children/adjacent nodes of s (by enqueueing these nodes into a queue) one by one.
For the network in Figure 2, node 1 will be examined first and checked to see if it has been visited or not and whether the current flow in the edge (v0, v1) has not reached maximum capacity. If these conditions are met, node 1 is set to be visited and in the index corresponding to node 1 in the parent array is set to node 0 as node 0 is the parent of node 1 forming the edge (v0, v1) and then node 1 is enqueued into the queue. All the children of node 0 are examined in a similar manner and enqueued into the queue if the checking conditions are met.
After examining all adjacent nodes of node 0, parent={-1, 0, 0, 0, -1, -1, -1, -1, -1}. The next node in the queue will be node 1 and its child node 4 is examined. As 4 is unvisited and has no flow, the parent of node 4 is set to node 1, marked as visited and enqueued into the queue. Proceeding in this manner, parent of 5 is set to 2 and node 5 is enqueued into the queue. The next node examined is 3 and its children are 5 and 7. Since 5 has already been visited, its parent will not change and it will not be enqueued into the queue.
However, since 7 is not visited, its parent is set to 3, marked as visited and enqueued into the queue. This will proceed until all nodes in the graph are examined (i.e. the queue is empty). At this point, the parent array for the flow network in Figure 2 will be parent={-1, 0, 0, 0, 2 Figure 2: Initial network with no flow Figure 3: First Augmenting Path from S-D 1, 2, 5, 3, 7}. Starting from the last index corresponding to node 8 which is the destination node, it is clear that the parent of 8 is 7, the parent of 7 is 3, the parent of 3 is 0.
Hence, the augmenting path from s to d in which flow can be increased is 0-3-7-8 and this is the shortest available path from node 0 to 8 as illustrated in Figure 3. Figure 4: Second Augmenting Path from S-D Suppose that a flow of 5 has been added to the path 0-3-7-8. If the breadth-first search algorithm is called again to operate on this flow network, the parent of 7 will not be set to be 3 anymore as the flow on the edge (v3, v7) is 5 which is the maximum capacity of that edge (no more flow can be added without infringing on the capacity constraint of that edge).
The parent of 7 in this case will be set to 5. The augmented path resulting from this graph will then be 0-2-5-6-8 as illustrated in Figure 4. Hence, the path-finding algorithm will successfully avoid the edge that is full. At the conclusion of the path search, the function will return 1 if the destination node has been visited and 0 otherwise. If the return value is 0, then an augmenting path 3 does not exist that connects s to d. This breadth-first searching algorithm is called the Edmonds-Karp algorithm.
The implementation of this algorithm is summarized in the following: • First set all elements in the visitedNodes array to 0 (to mark all nodes as unvisited) • Initialize a queue and enqueue the starting node • Begin a while-loop in which: – The queue is dequeued (say the dequeued node is vi) – For every node vj that is adjacent to the dequeued node vi , check if this adjacent node is unvisited and whether the current flow in the edge (vi , vj ) is such that more than 0 flow added to the edge (i.e. ci,j − fi,j > 0)
– If these conditions are met, then set the parent of this adjacent node vj to be the dequeued node vi and enqueue the adjacent node into the queue – Repeat the above until the queue is empty – Before the function terminates return 1 if d is visited and 0 otherwise Next, you will implement the function public void maximizeFlowNetwork(Graph fN, int s, int t). This is the function that computes the maximum flow in the flow network fN.
Following are the three main components of this function:
• The breadthFirstPathSearch function is called to find an augmented path • If such a path exists then the return value of this function is 1.(i.e. if node d is visited by the path searching algorithm). In this case, the maximum possible flow that can be added on all edges that form the augmenting path is computed (this flow must heed the capacity constraints of the edge) • The flow on all edges forming the augmenting path is incremented to the value computed in the previous step.
For every edge in which flow is added, ensure that you account for the back flow in the opposite direction • All three steps above are repeated until no more flow can be added to the flow network For instance, suppose that the augmented path computed by the path searching algorithm is 0-2-5-7-8. From Figure 3, it is clear that the maximum flow that can be added/augmented to all edges in this path is 10 due to edge (v5, v7) resulting in the flow network illustrated in Figure 4. This algorithm is called the Ford-Fulkerson algorithm. Available Functions (Clarifications) If you have already completed the assignment, do not worry about this section.
If you need more guidance on the return types of the Graph ADT, then you can utilize the following function declarations (this can be different): • public int numVertices(); • public Iterable<Vertex> vertices(); • public int numEdges(); • public Iterable<Edges> edges(); • public Edge getEdge(Vertex u,Vertex v); • public Iterable<Vertex> endVertices(Edge e); • public Vertex opposite(Vertex v, Edge e); • public int outDegree(Vertex v); 4 • public int inDegree(Vertex v); • public Iterable<Edges> outgoingEdges(Vertex v); • public Iterable<Edges> incomingEdges(Vertex v); • public void insertVertex(Vertex v); • public void insertEdge(Vertex u, Vertex v, E x);
• public void removeVertex(Vertex v); • public void removeEdge(Edge e); • public Vertex getVertex(int label); For the Edge ADT, the value that you are storing can be flow and flow capacity (combined into E). You can assume that the following Edge interface functions are available (if you have already made your assumptions, then don’t worry about this). • public int flowCapacity(); • public int flow(); Similarly, for the Vertex ADT, you can assume that the following interface functions are available: • public int getLabel(); For the functions: public void maximizeFlowNetwork(Graph fN, int s, int t) and public int breadthFirstPathSearch(Graph FN, int s, int d), the last two arguments indicate the labels/numbers assigned to the vertices (start and end nodes).
You can utilize the function getVertex to obtain the reference to the vertex corresponding to the label. Or you can assume that the two arguments are of Vertex type (change the input arguments type). Grading We will evaluate the logic behind your function implementations (breadthFirstPathSearch and maximizeFlowNetwork) (i.e. we will not run it). Marks will be deducted for syntax errors and logical errors. Code Submission You will use git to submit this assignment.
Create a new repository for LabAssignment3: • Create a new folder SE2205B-LabAssignment3 and add the file Assignment3.java in which you will implement the two afore-mentioned functions. • Open GitHub Desktop. • Run File → Add local repository. • Click Choose and browse for the folder SE2205B-LabAssignment3.
• You will get the following warning: This directory does not appear to be a Git repository. Would you like to create a repository here instead? • Click on Create a Repository and then click on Create Repository. • In the GitHub Desktop tool bar, click Publish repository, check the option Keep this code private, choose your GitHub account, and then click Publish repository.
• Now a new repository called “SE2205B-LabAssignment3” should appear in your GitHub account. • You will need to add the instructor and the TAs to this repository. For this, 5 – In the GitHub account click the repository SE2205B-LabAssignment3 and then click Setting – Click Collaborators & teams option.
– At the bottom of the page and in the Collaborators section, enter the account id of the GitHub user you would like to add and then click Add collaborator. – You need to add the following accounts to your repo: ∗ psrikan ∗ LiYangHart ∗ jliu2325 ∗ mithun03 ENSURE that your work satisfies the following checklist: • You submit before the deadline 6
