For this part of the assignment, you will write a short Java program that uses recursive backtracking to find a path through a graph or indicate that no path exists.

Objectives:

read data from a file and store it in a simple data structure

demonstrate exception handling

use recursive backtracking to perform a depth-first search

Introduction:

In mathematics and computer programming, a graph is a group of nodes connected to each other by edges. The diagram below shows an example of a "directed graph", where each edge has a single direction associated with it. In this example, each edge also has a "weight". So, this is a "weighted directed graph". Notice also that the nodes in the graph are numbered in sequence beginning with 0.

This is the kind of graph your program will analyze. Look at the graph above. Can you see any way to get from node 1 to node 5 by following the arrows? You should see two different paths. We will identify these paths like this: 1->3->5and 1->2->3->5. We could also identify a "cost" for each of these paths. The cost might be the number of nodes in the path, or it might be the sum of the weights of the edges (11 and 9 respectively for the two paths shown), or the cost might be determined by some other formula. In any case, we will not be using the weights or be worried about cost in this assignment; your goal is simply to find any path from the specified starting point to the end.

Data File:

How can we represent a graph like this in a data file or a computer program? A number of different ways to describe a graph in data exist. Soon we will cover linked data structures; these provide an intuitive way to model graphs, although not necessarily the most efficient. For this assignment we will use a modified adjacency matrix that specifies the weight for each edge in the graph. Here is the adjacency matrix that describes the graph shown above:

columns 0 1 2 3 4 5 6 +-------------------- r 0 | 0 0 0 0 0 0 4 o 1 | 0 0 3 9 0 0 0 w 2 | 5 0 0 4 0 0 0 s 3 | 0 2 0 0 0 2 8 4 | 2 0 1 0 0 0 7 5 | 0 2 0 0 0 0 0 6 | 0 0 0 0 0 0 0

In the adjacency matrix, the row and column numbers correspond to nodes in the graph. Each non-zero entry in the matrix defines an edge connecting two nodes. The edge is directed from the node corresponding to the row number to the node corresponding to the column number. For example, find the number '5' in the matrix. The 5 is in row 2, column 0; this defines an edge directed from node 2 to node 0. No negative numbers are allowed in the matrix.

The matrix will be provided in a simple text data file with a format like this:

The first line of the file will contain a single number: the size of the matrix.

Each line that follows defines one row in the matrix in a comma-delimited format.

Here is a link to the data file that defines the graph shown above: graph1.txt

Specification:

This assignment should be written in a single class named A4Graph. This class uses only static methods. No static variables, instance variables, instance methods or constructors are allowed. No user interface is required, but you may include a 'main' method with any code you wish (including a user interface) for testing purposes.

Three methods are required as defined below. Other private helper methods may be used if desired to organize your code.

public static int[][] getMatrix(String filename) -- This method takes a file name as a parameter and returns an 2D int array. The array should be filled with the values of the adjacency matrix that defines the graph. Basically, you need to read the data from the file and then fill the array based on the data.

The getMatrix method should never throw an exception under any circumstances. Instead, if an error is detected, the method should write a short message to the console (i.e. use System.out.println()) describing the problem, and then return the value null. This is not good behavior for a method in general, but I want to see that you are able to handle exceptions.

public static String getPath(int[][] adjacencyMatrix, int startNode, int endNode) -- This public, non-recursive "kick-off" method takes an array like the one returned by the getMatrix method and returns a String value (no printing) representing any one path through the graph represented by the matrix starting at 'startNode' and ending at 'endNode', or the string "no path" if there is no path. Some test graphs will have no possible paths. Others will have multiple paths. When there are multiple paths, any possible path may be returned. The string value returned must exactly follow the format shown in the sample results show below. Notice that if the starting and ending nodes are the same, the path is simply that node number. If there is no path, the exact string value shown should be returned. Otherwise, any one path should be identified using the format shown (in cases where multiple paths exist, your output may show a different path than mine, which is ok):

getPath(m, 1, 3): 1->2->3 getPath(m, 4, 1): 4->2->3->5->1 getPath(m, 1, 4): no path getPath(m, 1, 1): 1 getPath(m, 1, 5): 1->3->5

*Important note: a path may not visit the same node more than one time. Think about how this impacts your recursive algorithm.

The getPath method should throw an IllegalArgumentException if there is any problem with any parameter -- e.g. if the array parameter is null or if the array does not meet the requirements for defining an adjacency matrix (our definition is that every value in the array must be a non-negative number). To save time, you may assume the array is square.

Note that the getPath method should not "print" anything once you have it working; rather, it should simply return a string value or throw an exception.

The third required method is a private, recursive method that actually performs the depth-first search (i.e. the search for a path through the graph). You may use whatever parameter signature you like for this method.

Testing:

As always, you should do whatever tests you deem necessary to convince yourself that the code is working. If you wish, you may write JUnit tests. As a model for how JUnit tests can be constructed, and to help you determine if you are on the right track, the following test class has been developed that partially checks the project. Your code should pass all these tests if it follows the specification. You will need MORE tests to confirm for sure that it is working.

https://facweb.northseattle.edu/voffenba/class/csc143/A/A4GraphF18/SampleJUnitTestClassForA4Graph.java

It is important to remember that the getMatrix and getPath methods should work independently of each other. Each should be able to be tested separately any number of times. Remember the goal of minimize coupling. The getPath method should work only with the array passed in to it as a parameter.