JAVA

Given a directed graph, a source vertex source and a destination vertex dest, print all paths from a given source to a given dest. Consider the following directed graph. Let the source be 0 and dest be 4. There are 3 different paths from 0 to 4. [0, 2, 4], [0, 3, 2, 4] and [0, 3, 4]

1) Write a method to do Depth First Search (DFS) of a given directed graph. Implement the following methods: - public void printAllPaths(int s, int d) - private void printAllPathsUtil(Integer u, Integer d, ArrayList visited, List localPathList)

2) Run the Class TestGraph.java and see if the output is [0, 2, 4], [0, 3, 2, 4] and [0, 3, 4]. You may change values in TestGraph.java for testing purposes. Below is the file in which students will have to write their code wherever they find a comment: /* YOUR CODE HERE */

Graph.java package graphs; import java.util.ArrayList; import java.util.HashMap; import java.util.List; // A directed graph using adjacency list representation public class Graph { // No. of vertices in graph private int vertices; // adjacency list private HashMap> adjMap; private ArrayList adjList; public Graph(int vertices){ //initialise vertex count this.vertices = vertices; // initialise adjacency list adjMap = new HashMap>(); } // add edge from u to v public void addEdge(int u, int v) { // Add v to u's list. if(!adjMap.containsKey(u)){ adjMap.put(u, new ArrayList()); } adjMap.get(u).add(v); } // Prints all paths from 'source' to 'dest' public void printAllPaths(int source, int dest) {

/* Declare an ArrayList of Boolean values * Initialize ArrayList of Boolean values with 'false', size of list will be = 'vertices' */ /* YOUR CODE HERE */ /* Declare an ArrayList to store paths * Add source to list path */

/* YOUR CODE HERE */ /* Call recursive utility */ printAllPathsUtil(source, dest, visited, pathList); } /* * Mark the current node 'u' as true in visited list * if current node 'u' equals destination 'd' * Get arraylist 'verticeList' from 'adjMap' map for current node * recursively iterate over this 'verticeList' * check if vertice from this list is not visited already, add to 'localPathList' * recursively call this method for values from vertice list, set to current node * set current node as false after visiting it */ private void printAllPathsUtil(Integer u, Integer d, ArrayList visited, List localPathList) { /* YOUR CODE HERE */ } }

Java helper files (Students will need for testing Graph.java):

TestGraph.java package graphs; public class TestGraph { public static void main(String[] args) { // Create a sample graph Graph graph = new Graph(7); graph.addEdge(0,1); graph.addEdge(0,2); graph.addEdge(0,3); graph.addEdge(1,5); graph.addEdge(1,6); graph.addEdge(2,4); graph.addEdge(2,1); graph.addEdge(3,2); graph.addEdge(3,4); // source int source = 0; // destination int dest = 4; System.out.println("Following are all different paths from " + source + " to " + dest); graph.printAllPaths(source, dest); } }

SAMPLE OUTPUT: Following are all different paths from 0 to 4 [0, 2, 4] [0, 3, 2, 4] [0, 3, 4]

Please note a few points: 1. Create 2 separate java files for the above code and place them in a package named graphs. 2. Write your code in Graph.java wherever you find the comment /* YOUR CODE HERE */ 3. USE RECURSION for the implementation of printAllPathsUtil method.