1 Purpose

The primary purpose of this assignment is to help you review (and demonstrate that you have acquired) the knowledge and skills required to calculate shortest paths on a network using a variety of different algorithms and data structures.

2 Overview

Nearby is a (fictitious) company that develops personal navigation systems, en-route and mobile commerce systems, location-based services, and geographic tracking/location services. They are in the process of developing a personal navigation system called Way. They have hired you to construct several interfaces/classes that can be used to represent and solve graph-theoretic problems (like the shortest path problem).

3 Design Document

Nearby has provided you with the following design document:

(They have also provided you with an SVG version of the engineering design which can be enlarged in most browsers. It is named design.svg.)

4 Tasks

Note that you do not have to implement all of the concrete LabelManager classes. You need only implement one class that implements the CandidateLabelManager interface and one class that implements the PermanentLabelManager interface. In other words, you must implement one that will work with a LabelCorrectingAlgorithm and one that will work with a LabelSettingAlgorithm.

5 Testing

You should write unit tests for the graph package, but you are not required to do so.

You must perform system testing on all of the components you write. Nearby has provided you with the following classes that you can use for this purpose.

The last three are used by the first two, and provide the ability to run the shortest path calculation in a background thread (i.e., using a SwingWorker).

If you would prefer to debug with a simpler setup, you can use the following driver:

and change the hard-coded "options" (i.e., the algorithm, data structure, network, origin, and destination).

6 Submission

You must submit (to the PA5_Java assignment on Gradescope) a .zip file named pa5.zip that contains all of the code necessary to run PA5Driver.java and test you code (packaged appropriately). It must not contain any data files. There is no limit on the number of submissions and no penalty for excessive submissions.

You must submit (to the PA5_Screenshot assignment on Gradescope) a .pdf file that contains two screenshots for the Rockingham County data files, one with the shortest path from "400 Paul St" to "7000 Jess & Mary Ln" using a label setting algorithm and one from "400 Paul St" to "6500 Mount Clinton Pike" using a label correcting algorithm.

7 Grading

You will receive one of four grades on this assignment -- 100, 75, 50, or 0. You will receive a grade of 100 if your code is essentially correct (i.e., there are a small number of defects). You will receive a grade of 75 if you appear to have devoted significant effort to the assignment but your code has significant defects. You will receive a grade of 50 if you devoted a reasonable amount of effort to the assignment but your code has doesn't really work. You will receive a grade of 0 otherwise and/or if the code you submit to Gradescope contains any style defects.

The Gradescope autograder will assign a maximum grade of 25 (based solely on style). Points will then be awarded manually based on the criteria discussed in the previous paragraph.