Comp 251 Ford-Fulkerson & Bellman-Ford Solved

(50 points) Ford-Fulkerson

We will implement the Ford-Fulkerson algorithm to calculate the Maximum Flow of a di-rected weighted graph. Here, you will use the files WGraph.java and FordFulkerson.java, which are available on the course website. Your role will be to complete two methods in the template FordFulkerson.java.

The file WGraph.java is similar to the file that you used in your previous assignment to build graphs. The only differences are the addition of setter and getter methods for the Edges and the addition of the parameters “source” and “destination”. There is also an additional constructor that will allow the creation of a graph cloning a WGraph object. Graphs are encoded using a similar format than the one used in the previous assignment. The only difference is that now the first line corresponds to two integers, separated by one space, that represent the “source” and the “destination” nodes. An example of such file can be found on the course website in the file ff2.txt. These files will be used as an input in the program FordFulkerson.java to initialize the graphs. This graph corresponds to the same graph depicted in [CLRS2009] page 727.

Your task will be to complete the two static methods (fordfulkerson WGraph graph) and pathDFS(Integer source, Integer destination, WGraph graph). The second method pathDFS finds a path via Depth First Search (DFS) between the nodes “source” and “destination” in the “graph”. You must return an ArrayList of Integers with the list of unique nodes belonging to the path found by the DFS. The first element in the list must correspond to the “source” node, the second element in the list must be the second node in the path, and so on until the last element (i.e., the “destination” node) is stored. If the path does not exist, return an empty path. The method fordfulkerson must compute an integer corresponding to the max flow of the “graph”, as well as the graph encoding the assignment associated with this max flow.

Once completed, compile all the java files and run the command line java FordFulkerson ff2.txt. Your program will output a String containing the relevant information. An example of the expected output is available in the file ff2testout.txt. This output keeps the same format than the file used to build the graph; the only difference is that the first line now represents the maximum flow (instead of the “source” and “destina-tion” nodes). The other lines represent the same graph with the weights updated to the values that allow the maximum flow. The file ff226testout.txt represents the answer to the example showed in [CLRS2009] Page 727. You are invited to run other examples of your own to verify that your program is correct.

    1. (50 points) Bellman-Ford

We want to implement the Bellman-Ford algorithm for finding the shortest path in a graph where edges can have negative weights. Once again, you will use the object WGraph. Your task is to complete the method BellmanFord(WGraph g, int source) and shortestPath(int destination) in the file BellmanFord.java.

The method BellmanFord takes an object WGraph named g as an input and an integer that indicates the source of the paths. If the input graph g contains a negative cycle, then the method should throw an exception (see template). Otherwise, it will return

an object BellmanFord that contains the shortest path estimates (the private array of integers distances), and for each node, its predecessor in the shortest path from the source (the private array of integers predecessors).

The method shortestPath will return the list of nodes as an array of integers along the shortest path from the source to the destination. If this path does not exists, the method should throw an exception (see template). An example input is available in bf1.txt.

    3. (0 points) Knapsack Problem

We have seen in class the Knapsack problem and a dynamic programming algorithm. One could define the Knapsack problem as following:

Definition. Let n > 0 be the number of distinct items and W > 0 be the knapsack capacity. For each item i, wi > 0 denotes the item weight and vi > 0 denotes its value. The goal is to maximize the total value




while

n
X
vixi

i=1

n
X
wixi ≤ W
i=1

where xi ∈ {0, 1} for i ∈ {1, . . . , n}.

Algorithm. We recall the recursive form of the dynamic programming algorithm. Let OP T (i, w) be the maximum profit subset of items 1, . . . , i with weight limit w. If OP T does not select the item i, then OP T selects among items {1, . . . , i−1} with weight limit w. Otherwise, OP T selects among items {1, . . . , i − 1} with weight limit w − wi. We could formalize as

OP T (i, w) =

0

1, w)
if i = 0


OP T (i
−

if wi > w














max{OP T (i − 1, w), vi + OP T (i − 1, w − wi)}
otherwise





















Correctness of dynamic programming algorithm (0)

Usually, a dynamic programming algorithm can be seen as a recursion and proof by induction is one of the easiest way to show its correctness. The structure of a proof by strong induction for one variable, say n, contains three parts. First, we define the Proposition P (n) that we want to prove for the variable n. Next, we show that the proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive step, we assume that P (n) holds for any value of n strictly smaller than n0 , then we prove that P (n0 ) also holds.

Use the proof by strong induction properly to show that the algorithm of the Knapsack problem above is correct.

Bounded Knapsack Problem (0)

Let us consider a similar problem, in which each item i has ci > 0 copies (ci is an integer). Thus, xi is no longer a binary value, but a non-negative integer at most equal to ci, 0 ≤ xi ≤ ci. Modify the dynamic programming algorithm seen at class for this problem.

Note: One could consider a new set, in which item i has ci occurrences. Then, the algorithm seen as class can be applied. However, this could be costly since ci might be large. Therefore, the algorithm you propose should be different than this one.

Unbounded Knapsack Problem (0-bonus)

In this question, we consider the case where the quantity of each item is unlimited. Thus, xi could be any non-negative integer. Provide a dynamic programming algorithm for this problem.