Description

General instructions (Read carefully!)
• Your solution must be submitted electronically on codePost. Here is a short tutorial to help you understand how the platform works. You should already be on the platform since this is the second assignment.
Technical considerations
• You are provided some starter code that you should fill in as requested. Add your code only where you are instructed to do so. You can add some helper methods. Do not modify the code in any other way and in particular, do not change the methods or constructors that are already given to you, do not import extra code and do not touch the method headers. The format that you see on the provided code is the only format accepted for programming questions. Any failure to comply with these rules will result in an automatic 0.
• Note that your code will be evaluated with Java 8 on a linux environment (similar to ubuntu). It is your responsibility to make sure your code compiles and runs correctly when executed from command line in this type of environment.
• Your code should be properly commented and indented.
• Do not change or alter the name of the files you must submit, or the method headers in these files. Files with the wrong name will not be graded. Make sure you are not changing file names by duplicating them. For example, main (2).java will not be graded. Do not add packages or change the import statements.
• Submit your files individually on codePost (no zips)
• You will automatically get 0 if the files you submitted on codePost do not compile, since you can ensure yourself that they do.
Exercise 1 Ford-Fulkerson (50 points) We will implement the Ford-Fulkerson algorithm to calculate the Maximum Flow of a directed 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 “destination” 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.
Exercise 2 Bellman-Ford (50 points) 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.
Submit your two Java classes on codepost.