SE2205留学生代做、Data Structures代写、代写Java设计、Java程序调试

日期：2019-04-09 11:36

SE2205: Algorithms and Data Structures for Object-Oriented Design

Lab Assignment 3

Assigned: Mar 20, 2019; Due: April 8, 2019 @ 10:00 a.m.

If you are working in a group of two, then indicate the associated student IDs

and numbers in the Assignment3.java file as a comment in the header.

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 Pi∈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<V>> vertices();

public int numEdges();

public Iterable<Edges<E>> edges();

public Edge<E> getEdge(Vertex<V> u,Vertex<V> v);

public Iterable<Vertex<V>> endVertices(Edge<E> e);

public Vertex<V> opposite(Vertex<V> v, Edge<E> e);

public int outDegree(Vertex<V> v);

4

public int inDegree(Vertex<V> v);

public Iterable<Edges<E>> outgoingEdges(Vertex<V> v);

public Iterable<Edges<E>> incomingEdges(Vertex<V> v);

public void insertVertex(Vertex<V> v);

public void insertEdge(Vertex<V> u, Vertex<V> v, E x);

public void removeVertex(Vertex<V> v);

public void removeEdge(Edge<E> e);

public Vertex<V> getVertex(int label);

For the Edge<E> ADT, the value that you are storing can be flow and flow capacity (combined into E).

You can assume that the following Edge<E> 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<V> 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<V> 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:

ENSURE that your work satisfies the following checklist:

You submit before the deadline

6