Contents:

Introduction

It is sometimes difficult to navigate the 643 acres of the UW campus! To address this problem, UW Marketing has commissioned you to build a route-finding tool. It will take the names of two buildings and generate directions for the shortest walking route between them, using your graph ADT to represent buildings and pathways on campus.

In this assignment, you should continue to practice modular design and writing code for reuse. As before, you get to choose what classes to write and what data and methods each class should have. You will also get experience using the model-view-controller design pattern, and in later assignments you will reuse your model with a more sophisticated view and controller.

This assignment has four main parts. In the first part, you will make your graph class(es) generic. In the second part, you will implement a different pathfinding algorithm for graphs known as Dijkstra's algorithm. Third, you'll test your Dijkstra's algorithm implementation on some small graphs. Once you're satisifed with your Dijkstra's algorithm implementation, you'll link your graph class and Dijkstra's algorithm implementation to a text-user interface we've provided so you can see everything you've worked on so far in action!

By the end of this assignment, you'll have a fully-functional application for finding the shortest paths between buildings on campus! In future assignments, you'll be adding a graphical user interface to this application using Javascript.

Part 0: Understanding the provided code

Unlike the Graph and Marvel assignments, the Pathfinder assignment includes starter code provided by the staff. The provided files are as follows:

  1. pathfinder.ModelConnector
  2. pathfinder.datastructures
    1. pathfinder.datastructures.Path
    2. pathfinder.datastructures.Point
  3. pathfinder.parser
    1. pathfinder.parser.CampusBuilding
    2. pathfinder.parser.CampusPath
    3. pathfinder.parser.CampusPathsParser
  4. pathfinder.textInterface
    1. pathfinder.textInterface.CoordinateProperties
    2. pathfinder.textInterface.Direction
    3. pathfinder.textInterface.InputHandler
    4. pathfinder.textInterface.Pathfinder
    5. pathfinder.textInterface.TextInterfaceController
    6. pathfinder.textInterface.TextInterfaceView

To make progress in this assignment, you must understand the purpose of each of these classes and packages. To do this, run the javadoc task in Gradle and read all the provided documentation. This will help you as you work on this assignment.

Now read the entire assignment before you write any code. This will be beneficial when you start working on the assignment.

Part 1: Graph Modifications

Part 1: Make the Graph Generic

In Pathfinder, your mission is to find the shortest walking route between points on the UW campus. A graph is an excellent representation of a map, and luckily you have already specified and implemented a graph. Unfortunately, your graph stores only Strings, whereas Pathfinder needs to store other data in the nodes and edges, such as coordinate pairs and physical distances. More generally, your graph would be much more useful if the client could choose the data types stored in nodes and edges. Herein lies the power of generics!

Your task is to convert the graph ADT to a generic class. Rather than always storing the data in nodes and edge labels as Strings, it should have two type parameters representing the data types to be stored in nodes and edges. Directly modify your existing classes under the graph package — there is no need to copy or duplicate code. In fact, you should not copy or duplicate code.

When you are done, your previously-written graph and marvel tests and test drivers and MarvelPaths will no longer compile. Modify these classes to construct and use graph objects where the type parameters are instantiated with String. All code must compile and all tests must pass when you submit your homework. In particular, your test drivers for both the marvel and graph homeworks must work correctly so we can test your code. Depending on your changes, some of your implementation tests may no longer be valid. Try to adapt your implementation tests to your new implementation, or discard them and write new ones: they should help you build confidence in your implementation. But, don't overdo it: as with any testing, stop when you feel that the additional effort is not being repaid in terms of increased confidence in your implementation. Learning when to stop working on a given task is an important skill. Be sure to briefly document any changes you made to your HW5 and HW6 code outside of making your existing implementation generic in answers.txt. If you didn't make any changes, then say so (you don't need to justify why).

While changing your graph and marvel code, you may find it helpful to only run your HW5 and/or HW6 tests when you run the test gradle task. We normally prohibit you from modifying the build.gradle file, but we'll make an exception here. If you go the test {...} task in build.gradle, you will see multiple "exclude 'hwName/**'" lines. If you comment the line for a particular assignment, that assignment's tests will be run when you run the test task. So, for example, if you only wanted to run the HW6 tests, you would comment out every exclude line in the test task except for "exclude 'marvel/**'". If you do make any changes to your build.gradle file, you must undo those changes after you finish this part. If you fail to do this, then you will have problems later on when the staff push you future homework assignments. Similarly, you will probably find it helpful to use the compileGraphOnly gradle task to compile the Graph class (and any other classes it depends on).

Making the Path Class Generic

We've provided some utility classes in pathfinder.datastructures, including a Path class and a Point class that the Path class uses. The Path class currently represents a sequence of edges between nodes that contain Point data. As you'll see later in this assignment, this behavior works well for the campus paths dataset that we'll be working with in the next few assignments. However, the test driver still uses Strings for the node data, like when you use the AddNode command. Rather than modify the test driver to make it more specialized, you should use your new generics skills to modify the Path class so that it can use any kind of node data that a client of the Path class might want.

When you're done, you should be able to create a new Path<Point> and have it work just like the original implementation of the Path class, but you should also be able to create a new Path<String> and have it work well for when you're writing code for the test driver. Remember to update the documentation of the Path class so it doesn't specifically mention points. You're responsible for making sure the entire Path class makes sense with the modifications. You also may need to make a few small changes to code in ModelConnector, the showPath method of TextInterfaceView, and some other files so that they correctly parameterizes the now-generic Path type.

You may have noticed that if you declare a type parameter for an outer class like Path, you can use it directly in an inner class like Path.Segment, without declaring its own type parameter. The inner class is actually getting the same type parameter as in the outer class. So if you parameterize Path, your code inside Segment could use this parameter directly. Note that this means that you need to be careful about how you write variables of type Path.Segment. For example, when writing a variable declaration like Path.Segement segment = ..., you're actually doing something similar to writing List list = ..., it's missing the type parameter! Since the type parameter is part of the Path class declaration in this example, the parameter is written as Path<SomeType>.Segment when you need to declare a Segment variable.

Build Tools and Generic Code

Double-check that you have configured IntelliJ to issue errors for improper use of generic types.

IntelliJ's built-in compiler sometimes handles generics differently from javac, the standard Java compiler. This means code that compiles in IntelliJ might not compile when we run our grading scripts, leaving us unable to test your code and significantly affecting your grade. Fortunately, we have Gradle configured to use the correct compiler for this course, so make sure you always use the provided gradle tasks when you want to build and test your code. If Gradle reports that the build succeeded, all is well: your code compiles with javac. This is a great place to commit and push your code. The staff strongly recommends you do so before moving onto the next problem.

Parts 2-3: Dijkstra's Algorithm

Part 2: Using Dijkstra's Algorithm

In a weighted graph, the label on each edge is a weight (also known as a cost) representing the cost of traversing that edge. Depending on the application, the cost may be measured in time, money, physical distance (length), etc. The total cost of a path is the sum of the costs of all edges in that path, and the minimum-cost path between two nodes is the path with the lowest total cost between those nodes.

In this assignment, you will build an edge-weighted graph where nodes represent locations on campus and edges represent straight-line walking segments connecting two locations. The cost of an edge is the physical length of that straight-line segment. Finding the shortest walking route between two locations is a matter of finding the minimum-cost path between them.

Dijkstra's Algorithm

You will implement Dijkstra's algorithm, which finds a minimum-cost path between two given nodes in a graph with all nonnegative edge weights. (This restriction is important, Dijkstra's algorithm can fail if there are negative edge weights. In this assignment, since all edge weights represent physical distances, all our edge weights are nonnegative and Dijkstra's algorithm will work well.) Below is a pseudocode algorithm that you may use in your implementation. You are free to modify it as long as you are essentially still implementing Dijkstra's algorithm.

The algorithm uses a data structure known as a priority queue. A priority queue stores elements that can be compared to one another, such as numbers. A priority queue has two main operations:

For example, if you inserted the integers 1, 8, 5, 0 into a priority queue, they would be removed in the order 0, 1, 5, 8. It is permitted to interleave adding and removing. The standard Java libraries include a PriorityQueue implementation that you should use. 

// Dijkstra's algorithm assumes a graph with nonnegative edge weights.

start = starting node
dest = destination node
active = priority queue.  
// Each element is a path from start to a given node. 
// A path's “priority” in the queue is the total cost of that path. 
// Nodes for which no path is known yet are not in the queue.
finished = set of nodes for which we know the minimum-cost path from start.

// Initially we only know of the path from start to itself, which has
// a cost of zero because it contains no edges.
Add a path from start to itself to active

while active is non-empty:
  // minPath is the lowest-cost path in active and,
  // if minDest isn't already 'finished,' is the
  // minimum-cost path to the node minDest
  minPath = active.removeMin()
  minDest = destination node in minPath

  if minDest is dest:
    return minPath

  if minDest is in finished:
    continue

  for each edge e = ⟨minDest, child⟩: // For all children of minDest
    // If we don't know the minimum-cost path from start to child,
    // examine the path we've just found
    if child is not in finished:
      newPath = minPath + e
      add newPath to active

  add minDest to finished

// If the loop terminates, then no path exists from start to dest.
// The implementation should indicate this to the client.

Implementing Dijkstra's Algorithm

Write an implementation of Dijkstra's algorithm that can work with a graph that has Doubles as the edge data. You're free to choose where you place this implementation, but think about where it makes the most sense. For example, is your graph always going to have Double edge data?

This assignment does not reuse your breadth-first search algorithm. A breadth-first search between two nodes finds the path with the fewest number of edges. In a weighted graph, that is not sufficient to find the minimum-cost path. In the example below, a breadth-first search from A to B would find the path {⟨A,B⟩} with total cost 10. But the alternative path {⟨A,C⟩,⟨C,D⟩,⟨D,B⟩} has a total cost of 3, making it a lower-cost path even though it has more edges.

A graph with a minimum-cost path of 3
A graph whose minimum-cost path is not found by BFS.

Breadth-first search gives the same results as Dijkstra's algorithm when all edge weights are equal.

Part 3: Testing Dijkstra's Algorithm

The format for writing tests follows the usual specification/implementation structure, but with some details changed to accomodate changes to the graph and the data stored in it. You should write the majority of your tests as specification tests according to the test script format defined below, specifying the test commands and expected output in *.test, *.expected files, respectively. As before, you should write a class PathfinderTestDriver to run your specification tests. We provide a starter file for the test driver which you are free to modify or replace. Do not modify ScriptFileTests.java.

If your solution has additional implementation-specific behavior to test, write these tests in a regular JUnit test class or classes and add them to src/test/java/pathfinder/implTest as usual.

The specification tests do not directly test the property that your graph is generic. However, the graph and marvel homework test scripts use String edge labels, while this assignment uses numeric values. Supporting all three test drivers implicitly tests the generic behavior of your graph.

When this assignment is tested we will also rerun the graph and marvel homework test scripts to verify that those parts of the project continue to work as expected. You should be sure that you have fixed any problems that were discovered previously so they don't occur when the tests are run again.

Dijkstras Test Script Format

The test script file format for this assignment uses the same commands and format as the marvel homework, but with a few differences in arguments and output. Be sure to read this section carefully.

You should put all of your specification tests for your Dijkstra's algorithm implementation in the folder src/test/java/pathfinder/specTest/. To illustrate the use of the above format changes, there is a sample test included that demonstrates Dijkstra's algorithm correctly finding the minimum cost path on the example graph used above. Remember to use what you've learned in this class about designing a quality test suite. Once again, this is a good place to commit what you already have, and the staff recommends you do so before starting the next part.

Take a Break

Congratulations on successfully implementing and testing Dijkstra's algorithm on your shiny new generic graph! You'll be using that algorithm in the next part on a dataset containing information about paths to and from different locations on campus in order to find the shortest path between any two places!

Part 4: Pathfinder and a Text User Interface

Model-View-Controller

The Pathfinder application makes use of the Model, View, Controller design pattern to factor out logical portions of the code and reduce coupling, thus making the code much more maintainable. In this homework assignment, you'll be creating a Model that will work with a View and Controller that we're providing (the text user interface). In future assignments, you'll be using said Model with a new View and Controller that you get to design and create yourself. Specifically, you'll be using web technologies like Javascript to design a graphical user interface for your applications that users can use to find the shortest path between two points on a map of campus. That's the power of Model-View-Controller design - you can have the same code handle all of the work regarding parsing and representing the campus data and finding paths within it (the Model) and just swap out a View and Controller for something entirely different later! If your code didn't make use of the Model-View-Controller pattern and had a lot of coupling between different parts, it would be a lot harder to make that change later.

Below, you'll find a description of the different parts of a Model-View-Controller system, and how they're intended to work together. For a text user interface, it's very difficult to completely separate the view and controller, so you'll see in our provided code that it's might be a little harder to tell the difference between the two parts. In general, the TextInterfaceController class handles most of the work of the controller, while the TextInterfaceView class does most of the work of the view. The difference between the Model and the View/Controller, however, should be very clear. Your job, in part 4, will be to implement the model class ModelConnector.

The Three Pieces: Model, View, Controller

The Campus Dataset

We're providing a dataset containing information about a large network of pathways between many different locations on and around campus. You'll use this dataset to construct a graph representation of the campus map, which you can then use your implementation of Dijkstra's algorithm on to determine the shortest path between any two points.

In the src/main/resources/pathfinder/data directory, we have provided four files related to this dataset. Two are tab-separated-value (tsv) files, similar to the ones you used in the marvel assignment: campus_buildings.tsv and campus_paths.tsv. The other two are image files: campus_map.jpg which is a standard map of campus, and campus_routes.jpg, which is a graphical representation of the data contained in campus_paths.tsv. You will not use either of the image files for this assignment, they're included just for your reference to help you understand the data included in the tsv files.

Just as in the marvel assignment, you can open the tsv files with any standard text editor to view them. Their formats are described below for your reference. In this assignment, we are providing an implementation of a parser for you that can read the campus_buidings.tsv and campus_paths.tsv files and return Java objects representing the data contained in them. The provided parser works similarly to the parser you wrote in the marvel assignment. You are free to modify or completely remove/replace the provided parser, if you would like. The provided parser already works correctly with this file format, and the information included in the next section is included for your reference.

The Campus Dataset Format

campus_buildings.tsv contains information about all buildings on campus, based on the time the file was created. (This is a little out of date, the dataset we're working with is based on a map of campus from 2006, so you'll notice some minor differences from what campus looks like now.) The file often contains the locations of multiple entrances for the larger buildings, such as Mary Gates Hall. Each line in the file is of the form: 

shortName     longName     x     y

Each of the fields are separated by tabs. In the above, shortName is a short nickname for the building/entrance being described by the line. You'll use this short name to refer to buildings in your user interface, so your users don't have to type out the full name of buildings. longName is the full name of the building/entrance, and is useful when displaying information to your user. An example shortName/longName pair is "MGH (E)" and "Mary Gates Hall (East Entrance)". There may be spaces in the long or short names of a building, as seen in the example. You may assume that both short and long names are unique; that is, no two entries have the same short or same long names. The x and y fields make up a coordinate pair (x,y) that represent the location of that building/entrance (in pixels) on campus_map.jpg.

campus_paths.tsv contains information about a large number of straight-line paths between two points on campus (there are over 5500!). These points may be buildings, as defined in campus_buildings.tsv, or just additional points throughout campus, such as the corner of a sidewalk. The vast majority of the points in this file do not correspond to particular buildings, and instead make up parts of larger multi-segment pathways between buildings. See campus_routes.jpg for an image of what the data in this file looks like. Each line in campus_paths.tsv is of the form: 

x1     y1     x2     y2    distance

(x1,y1) and (x2,y2) are two coordinate pairs representing points (measured in pixels) on campus_map.jpg. distance is the distance of the straight-line path between those two points, measured in feet. You should not attempt to calculate the distance between two points in this assignment by using the pythagorean theorem (or any other math). Instead, just use the provided distance in this file wherever you need the distance between two points. You may assume that there are no duplicates in this dataset. Some of these points are exactly the same as points found in campus_buildings.tsv, and represent paths that begin/end at those building entrances.

The information here is included for your reference so you can understand the data. Remember that you can use the provided parser, CampusPathsParser, in the pathfinder.parser package, which will return lists of CampusBuilding and CampusPath objects that contain all the data described above, for you to use as you please. See the documentation in the classes in the pathfinder.parser package for more information on how this works.

Part 4: The Pathfinder Text User Interface

You will make use of provided View and Controller classes for a text user interface, and connect them with your model (your graph and supporting classes) to create a fully-functional application that you can interact with! You're encouraged to take a moment to explore the provided code in the pathfinder.textInterface and pathfinder.datastructures packages, which implement a view and controller for the text user interface in addition to a number of supporting classes used by the view and controller.

See the Pathfinder class in pathfinder.textInterface for the main method that will be run when your application is started. It creates objects for the model, view, and controller, and properly links them together. The ModelConnector class is a class that contains only stubs right now - you'll implement that later in this part. The TextInterfaceView class implements a "view" for command-line interaction that determines how things are printed out to the user. The view class is provided with a reference to the controller class (using setInputHandler) so it can pass input events to the controller for it to handle. The TextInterfaceController class implements most of the controller for this application, and needs a reference to the model so it can query the model for data and computations, and a reference to the view so it can call view methods to respond to the user input events it recieves as an InputHandler. Once all this is set up, the main method calls the controller's launchApplication method to tell the controller it's time to prompt the user for input and start responding to it.

Since we are providing an implementation of the text user interface to you, you do not need to worry about the specifics of the interface being described. However, you are encouraged to explore the codebase provided and understand how and why the view, controller, and supporting classes work the way they do. Provided at the end of this spec is an additional section that describes the specification of the text user interface, so you can see why certain descisions were made. It is not required that you understand all these specifics, but it is useful to look at and good preparation to do so before you implement your own view and controller in a later assignment.

Implementing your Model

The existing controller makes calls to a ModelConnector object which it expects to return data from the model or request that the model do some computation. Right now, all the methods in ModelConnector are stubs - they have signatures and specifications, but do nothing but throw an exception. It's your job to implement the methods according to their provided specifications, using things like your generic graph implementation, dijkstra's algorithm implementation, and the provided parser. You should implement the method stubs exactly as specified and not change the specifications, as the provided code is using those methods according to their provided specifications. (This is a good example of how important specification decisions can be - once other code has come to rely on specifications, it can be difficult or impossible to change them later).

You are free to add any other methods or classes as part of your model if doing so makes sense for your design. You should continue to practice good design principles throughout this assignment. Once you've finished your implementation of ModelConnector and any supporting classes, the Pathfinder application should be ready to run! Use the runPathfinder gradle task to run your finished application and iteract with it in the command line. Have some fun with it - you've worked hard over the last few weeks to get to a fully-functional application that uses your generic graph to do something really interesting!

Testing your Application

The behavior of the provided methods (that used to be stubs) in the ModelConnector class are based primarily on the dataset used and are implicitly tested as part of the final functionality of the text user interface of your application. For the purposes of this assignment, you don't need to write JUnit tests for those methods. You should, however, test any additional methods that you write as part of your model or any supporting classes. Write these tests as JUnit test cases and place them in test/java/pathfinder/implTest or test/java/pathfinder/specTest based on whether your tests are spec tests or implementation tests.

Collaboration

Please answer the following questions the file named src/main/java/pathfinder/collaboration.txt. The standard collaboration policy applies to this assignment. State whether or not you collaborated with other students. If you did collaborate with other students, state their names and a brief description of how you collaborated.

Hints

Documentation

When you add generic type parameters to a class, be sure to describe these type parameters in the class's Javadoc comments so the client understands their purpose.

As usual, write inline comments to clarify complicated blocks of code when necessary and document the loop invariants for nontrivial loops. Be sure to include an abstraction function, representation invariant, and checkRep in all classes that represent a data abstraction (ADT). If a class does not represent an ADT, place a comment that explicitly says so where the AF and RI would normally go. (For example, classes that contain only static methods and are never constructed usually do not represent an ADT.) Please come to office hours if you feel unsure about what counts as an ADT and what doesn't.

Make sure you remember what you learned from the earlier assignments - design and document your solutions to these problems before jumping straight in and writing code. You'll have a much better structured application if you put some thought into the design first. Think about how different parts of your application will work together.

Code Organization

When implementing the model for your text user interface, it's easy to write a lot of duplicate code. Remember your training in code organization and resuability, and make sure you design your text user interface with good practices in mind. In particular, you should think about whether parts of your code should be factored out into separate methods or classes - there is no reason why you should write your entire application in a single main method in a single class. In fact, it would be bad style to attempt to implement a large application like this in a single gigantic method, as your code would become hard to change, hard to read, and hard to reuse.

What to Turn In

You should add, commit, and push the following files to your GitLab repository:

Additionally, be sure to commit and push all updates you make to the following files:

When you have committed and pushed all of your changes and are done with the assignment, you should create a git tag in your repository and push that tag to your repository. Once you have committed and pushed that tag, your assignment has been submitted and the staff will grade the files in your repository that are labeled with that tag.

Refer to the assignment submission handout for complete turnin instructions.

Optional Additional Information: Text User Interface Specification

These are the requirements for the text user interface. It has already been implemented and supplied for you with the starter code, so you will not have to create it. The requirements are given here to help you understand what it does and how to use it.

Your program should begin each prompt with a blank line followed by the line: 

Enter an option ('m' to see the menu):

Each prompt should end with a single space and no newline, so the user enters their input on the same line as the prompt. Each line of user input that your program reads from the standard input should be one of the following:

If the input does not match any of the above cases, your program should print the line: 

Unknown option

Route Format

There are a few parts to printing out the route that your algorithm finds between two paths. When the r command is received, your program should prompt the user for the short names of two buildings in the dataset, as described above. If one or both of the buildings is not in the dataset, your program should output the following: 

Unknown building: SHORT_NAME

Where SHORT_NAME is replaced with the short name of the building that could not be found. If both buildings could not be found, two of these messages should be printed, in the order that the buildings were input by the user. These messages should not be printed until both buildings have been entered by the user, even if the first building is unknown.

You may assume that, if both buildings exist in the dataset, that there will be a path between them. When your program finds a path between two known buildings, it should print that path as follows. First, it begins with a line: 

Path from START_LONG to END_LONG:

Where START_LONG is the long name of the building at the beginning of the path, and END_LONG is the long name of the building at the end of the path. This should be followed by a sequence of lines of the form: 

    Walk DISTANCE feet DIRECTION to (X, Y)

In the above DISTANCE should be replaced by the length (in feet) of that segment of the path, and X and Y should by replaced by the x and y pixel coordinates of the point at the end of that segment of the path. All three of those numerical values should be rounded (not truncated) to the nearest integer. Each line should be indented with a single tab (\t) character.

DIRECTION should be one of the eight compass directions N, E, S, W, NE, NW, SE, SW. You can determine the direction of each segment by comparing the start and end points of the segment and doing some math. The method Math.atan2 and constant Math.PI may be helpful to you in doing this. Remember that the image coordinates (and therefore your pixel coordinates) begin in the top left of the image, while standard cartesian coordinates (like those used with Math.atan2) begin in the bottom left. Think very carefully about how you should which direction the coordinate should be used. It may be helpful to sketch some examples out on paper first.

Use the following image to determine which angles correspond to which compass direction that should be printed. If a segment angle exactly lines up with the border between two compass directions, you can select either one.

A compass rose with eight sectors
The eight sectors for classifying directions.

Finally, you should print the line: 

Total distance: DISTANCE feet

In the above, DISTANCE should be replaced with the total distance of the path. It should also be rounded to the nearest integer, but only once the final sum of all the segments are calculated. You should not add up the rounded distances of each path segment. The above line is not indented at all.

The menu printed should be identical to the following, where the last three lines are indented by a single tab. 

Menu:
  r to find a route
  b to see a list of all buildings
  q to quit