Assignment 4
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.