Programming question for Homework 3: Graphs and shortest paths

Part A

Design and implement Java classes for representing and manipulating directed multigraphs. A (multi)graph is determined by whether it is directed or undirected, by the number of its nodes/vertices, and by the (multi)set of its weighted edges. For this assignment, we only consider directed multigraphs and the number of nodes are determined when the graph is instantiated, and do not change during the lifetime of the graph. The nodes of the graph are labeled by integers 0,1,..,(n-1), where n is the number of nodes. The set of edges of a graph is not fixed. Initially, a graph contains no edges at all. A graph implementation should support methods for inserting and removing (weighted) edges. Multiple edges from the same source to the same target node are allowed.

You should implement (parts of) two different representations: one that uses an adjacency matrix to store edges, and one that uses adjacency lists.

Part B

Implement a Java method that implements Dijkstra's single-source shortest path algorithm of a given directed multigraph using a priority queue. Your algorithm should be very similar to that described on page 595 of your CLRS textbook. The priority queue data structure you should use is the one provided in the MinPriorityQueue.jar classes (the heap you implemented in Assignment 1 lacks the Update operation required by Dijkstra). We have provided the JavaDoc documentation.

To mark your assignment, we will test your code using our own secret tester routine. Successfully running the GraphTester class we provide does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own test cases. Your code may be tested with an auto-marker routine and/or by TA inspection to check that your routines are implemented correctly.

Note that you will be extending your solution for this assignment for Assignment 4, so it will be beneficial to follow good programming practices.

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the AdjMatrixGraph, AdjListsGraph and Dijkstra classes, where indicated by comments that start with: "// TODO:". You may also add appropriate private instance variables or helper methods.

Starter code:

Since we are providing some starter code in the form of a .jar file, you'll need either to add this file to your classpath (i.e., use a command like "javac -cp .:MinPriorityQueue.jar *.java" to compile and give the same option to java to run) or unpack the .jar using the "jar xf MinPriorityQueue.jar" command.

Submission Instructions

  1. Submit your code using the "submit" mechanism on CDF (by 5:30pm on Thursday, July 19). The CDF FAQ contains general instructions for submitting your code electronically (under the "Submitting Work" section).

  2. Submit only three .java files AdjMatrixGraph.java, AdjListsGraph.java and Dijkstra.java (after you have implemented the missing parts) to the directory called PGM3. All the code that you implement should be inside these files.

  3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.

  4. Do not submit any printout of the code.

  5. Do not rename the files, or any of the methods and variables found in our starter code.

  6. Write your name, student number and CDF username in a comment at the top of the  Dijkstra.java file. If you have a partner, you should also write the corresponding information about your partner.

  7. We will compile your code and test it using our own secret tester code (which is similar to, but more thorough than, the tester code that we provide as part of the starter code).

  8. Your code must compile and run on the CDF Unix/Linux system. Test it there! Programs that do not compile and run get 0 marks.