Matrix Graph

Graphs

You are given an input adjacency matrix representing a directed graph in the following format:

0 0 0 1 0
0 0 1 0 1
1 0 0 0 0
0 1 0 0 1
0 0 0 0 0

Nodes are to be indexed from 0 to n 1, where n is the total number of nodes.

You are also given a query file that contains pairs of graph nodes. Your task is to determine if there is a path between these nodes in the graph and to record this path in the output file. You must also indicate if the path does not exist.

The format of the query file is start_node, end_node. For example:

0 1
4 2

The format of the output file is start_node, path_node, . . ., path_node, end_node if the path is found, and start_node, -1, end_node if the path is not found. For the above example, the output file will be:

0, 3, 1
4, -1, 2

Create a Java program that performs the following steps:

• Read the adjacency matrix for a directed graph from the input file and store it in a corresponding data structure.
• Find the paths between the nodes given in the query file by traversing the graph using a depth-first graph traversal. Print the paths to the output1.txt text file.
• Find the paths between the nodes given in the query file by traversing the graph using a breadth-first graph traversal. Print the paths to the output2.txt text file.

Be sure to use proper headings and fixed-width columns for both of the output files. The program will be invoked from the command line as follows:

java Assign4 input query output1 output2

where Assign4 is the name of the file containing executable bytecode for your program, input is the name of the input text file containing the adjacency matrix, query is the name of the input text file containing the sequence of nodes for which connecting paths should be found, output1 is the name of the text file containing the paths obtained using the depth-first graph traversal, and output2 is the name of the text file containing paths obtained using the breadth-first graph traversal. If the command line arguments are improperly specified, the program should print out a "usage" message and abort. Be sure the specified files can be opened or created.

An official input file and query file will be made available to the class before the due date; use these files to create your output files. You must program all the data structures from scratch; in other words, do not use any classes from the Java libraries to implement the graph or queue/stack.

Bonus (optional)

Adapt your program so that it also finds the shortest weighted path between the specified start node and end node in a weighted directed graph. Use Dijkstras Algorithm. Modify your program so that an additional output file (specified as output3.txt on the command line) is produced. Create your own input files to test your code. Additional official input and query files will also be made available; use these to generate your third output file.