Assignment 3 Graphs Solution

Graphs are invaluable data structures. You will be given a Java source code that implements Dijkstra’s Shortest Path algorithm and prints the resulting paths. In this assignment, you will write a parser to read a text file to construct an adjacency matrix graph used in the given Java code.


INSTRUCTIONS


Extend the given Java source code “DijkstrasAlgorithm” to perform the following tasks:


    1. Request the user for the name of a text file. Example input text file “ex6”


    • ex6.txt
    • 
04100029
00510320
0005000
45000038
00323600
02900210

This ex6.txt file

represents an
adjacency matrix
structuring the graph
on the right discussed
in class:








    2. Write a parser to read the input file and adapt it to the given Java code. Your parser will initialize the adjacency matrix after the input text file given by the user (i.e., yellow highlighted text below)

class Asgmt3 {

public static void main(String[] args) {

int[][] matrix = AdjacencyMatrixParser.parseFile(inputFileName);


DijkstrasAlgorithm.dijkstra(matrix, 0);

}


}

CPSC 319, Summer 2020    Asgmt #3 – Graphs    Page 2 of 3




Example of the resulting 6x6 matrix after parsing the input text file inputFileName = “ex6 “

int[][] matrix =













X

    3. Write the output of the given Java code to a text file. Note the given Java code displays the output on the screen. Your program should explicitly write the output to the text file with name “inputFileName_dijkstra_output”

Example of content of output file name “ex6_dijkstra_output”

















GIVEN CODES & TEXT FILES

    1. Asgmt3.java – You should adapt it to accept the input file name (Step 2)
    2. DijkstrasAlgorithm.java – Source code you should modify for the assignment
    3. FileIO.java – You should adapt it in your program

    4. Four input files representing cities and distances between them (you should process) and corresponding output (for your reference)

Input Text Files
Reference Output Text Files (i.e., your program must match them)
sp11
sp11_dijkstra_output
ha30
ha30_dijkstra_output
wg59
wg59_dijkstra_output
sgb128
sgb128_dijkstra_output




2
CPSC 319, Summer 2020    Asgmt #3 – Graphs    Page 3 of 3



HAND-IN


    1. Your code for Asgmt3.java, AdjacencyMatrixParser.java, FileIO.java

    2. README (w/ instructions on how to run and use/interact with your program)
    3. Please include all of the above items in a zipped folder titled (asgmt3-your LAST NAME-ID).zip and submit it to D2L dropbox.

LATE ASSIGNMENTS WILL NOT BE ACCEPTED – START WORKING IN YOUR ASSIGNMENT EARLY


MARKING


Source code that does not compile or produces run-time errors will receive a grade of 0%.


Item
Points
1
Request the user for the name of a text file
1 point
2
Correct output format and content for the 4 given input text files.
4 points

The corresponding output files are given for your reference.





Total
5 points


INDIVIDUAL WORK


    • The assignment must be done individually, so you must write up the solutions on your own in your own words.

    • Everything that you hand in must be your original work, except for the code copied from the textbook, lecture material (i.e., slides, notes), web, or that supplied by your TA. When someone else’s code is used like this, you must acknowledge the source explicitly, citing the sources in a scientific way (i.e., including author(s), title, page numbers, URLs, etc.).

    • Copying another student’s work constitutes academic misconduct, a severe offence that will be dealt with rigorously in all cases. Please read the sections of the University Calendar under the heading “Student Misconduct.”

    • If you are in doubt whether a specific form of aid is allowed, ask your instructor!

    • Contact your TA if you have problems getting your code to work.

    • Note that your code may be checked thoroughly for plagiarism by computer.




END OF THE ASSIGNMENT












3