| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Things graded:
Use the provided Graph (DirectedGraph) and Dijkstra (DirectedDijkstra) implementations rather than some other data structure or writing your own. This is an exercise in graph modeling — designing the graph rather than the algorithm — and also an opportunity to become more familiar with using a graph data structure. The API for the provided code is linked in the project handout.
The graph (and the corresponding Dijkstra's implementation) need to be directed — the speed of travel (and thus the "length" of the track) depends on the direction traveled along the track. It happens to be the same in the particular map file provided, but that isn't necessarily the case and shouldn't be assumed. Also make sure that you add edges in both directions for each entry in the map file — a given track segment is only listed once, not once for each direction.
When building the graph from the map file, only create a new vertex if the vertex hasn't already been created — each track segment is only listed once but each junction can involve multiple tracks so the same junction can come up multiple times (but you only want one vertex for it).
Consider efficiency: you may need to find the Vertex object corresponding to a particular vertex name (like J197). How can you avoid searching through all of the vertices in the graph to find the right one?
Handling controls: Control locations are specified by the track segment the control is on, but Dijkstra's algorithm finds the shortest path between vertices, not edges. The problem states that you can assume that the control is in the middle of that track segment, and controls are also the only place where you can turn around in the middle of a track. These things suggest what to do: for each control, add new vertex in the graph for that control and split the edges for that track segment. In other words, if a control is on a track segment connecting junction 1 and junction 2, create a new vertex for the control and add edges (in both directions) connecting the control to junction 1 and the control to junction 2 with lengths that are half the length of the original track segment.
To visit the controls in order, run Dijkstra's for each consecutive pair of controls — start to control 1, control 1 to control 2, control 2 to control 3, etc. Make sure you initialize the algorithm with the starting vertex for each leg using init before using run to find the shortest path to the next control.
Things not graded, but worth paying attention to:
Code to the interface — concrete types like HashMap, AdjacencyListDirectedGraph, or AdjacencyListDirectedVertex should (generally) only be used when creating a new object (with new). For variables, parameters, and return types, use the highest-level type that has the right methods — in this case, Map, DirectedGraph, and Vertex, respectively. This saves a lot of casting in the case of DirectedGraph methods and makes it easier to change to a different implementation later should that be needed.
javafx.util.Pair is intended for name-value pairs, not a pair of two vertices. You can make it work for a pair of two objects, but it's not elegant and can lead to confusion.