CPSC Assignment 4 Graphs Solved

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:

    1. Read the adjacency matrix for a directed graph from the input file and store it in a corresponding data structure.
    2. 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.
    3. 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 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.

Create your own input files to test your code. 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 Dijkstra’s 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.

Questions

    1. Describe the algorithm based on the graph traversal to find if there is a loop (a path of directed edges of the graph that starts and ends at the same node). Which traversal technique (breadth-first or depth-first) is more suitable? What is the worst-case complexity of this algorithm?
    2. For a given query file, which traversal technique (breadth-first or depth-first) is more efficient in determining if the path exists between the given nodes? Use the provided input file and query file to help answer this question.

Submit electronically using the D2L dropbox:

    1. A readme.txt text file, which indicates how to compile and run your program, and if you are doing the bonus part.
    2. Your source code files. Your TA will run your program to verify that it works correctly. Make sure your Java program compiles and runs on the Computer Science Linux servers.
    3. The output files that your program generates. Name these output1.txt, output2.txt, and output3.txt (if doing the bonus part of the assignment).
    4. The answers to the above questions, in Word or PDF format

Collaboration 

The assignment must be done individually so everything that you hand in must be your original work, except for the code copied from the text or course directory, or that supplied by your TA. When someone else's code is used like this, you must acknowledge the source explicitly. Copying another student's work will be deemed academic misconduct. Contact your TA if you have problems getting your code to work.