[Solved] COMP251 Assignment 3-Ford-Fulkerson algorithm

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 inthe template FordFulkerson.java.The file WGraph.java is similar to the file that you used in your previous assignment tobuild graphs. The only differences are the addition of setter and getter methods for theEdges and the addition of the parameters source and destination. There is also anadditional 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 byone space, that represent the source and the destination nodes. An example of suchfile can be found on the course website in the file ff2.txt. These files will be usedas an input in the program FordFulkerson.java to initialize the graphs. This graphcorresponds to the same graph depicted in [CLRS2009] page 727.Your task will be to complete the two static methods fordfulkerson(Integer source,Integer destination, WGraph graph, String filePath) and pathDFS(Integer source,Integer destination, WGraph graph). The second method pathDFS finds a pathvia Depth First Search (DFS) between the nodes source and destination in thegraph. 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 tothe 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. The methodfordfulkerson 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. The methodfordfulkerson has a variable called myMcGillID, which must be initialized with yourMcGill ID number.Once completed, compile all the java files and run the command line java FordFulkersonff2.txt. Your program must use the function writeAnswer to save your output in a file.An example of the expected output file is available in the file ff226000000.txt. Thisoutput keeps the same format than the file used to build the graph; the only differenceis 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 updatedto the values that allow the maximum flow. The file ff226000000.txt represents theanswer to the example showed in [CLRS2009] Page 727. You are invited to run otherexamples of your own to verify that your program is correct.

Exercise 2. (25 points) Bellman-FordWe want to implement the Bellman-Ford algorithm for finding the shortest path ina graph where edges can have negative weights. Once again, you will use the objectWGraph. 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 integerthat 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 returnan object BellmanFord that contains the shortest path estimates (the private array ofintegers distances), and for each node, its predecessor in the shortest path from thesource (the private array of integers predecessors).The method shortestPath will return the list of nodes as an array of integers alongthe shortest path from the source to the destination. If this path does not exists, themethod should throw an exception (see template).Input graphs are available on the course webpage to test your program. Nonetheless, weinvite you to also make your own graphs to test your program.