| CPSC 327 | Data Structures and Algorithms | Spring 2025 |
Using the code provided in /classes/cs327/skio/, implement the ski-o route finding problem as discussed below.
Ski orienteering is the sport of cross-country navigation on skis — competitors must navigate to a series of checkpoints (called controls) using a map and compass. An orange-and-white flag marks the location in the terrain. Controls typically must be visited in a particular order, and the goal is to navigate to a certain sequence of controls as quickly as possible.
Maps for ski-o (click for a larger version) show the track network, terrain, vegetation, and the course:
Tracks are shown with green lines. The symbol indicates the size of the trail — dashed lines are the narrowest and typically slowest, thick solid lines are the widest and typically fastest.
Contour lines are in brown.
Vegetation is shown with shades of yellow and green.
The course is in purple — a triangle for the start, circles for the controls, and a double circle for the finish. Straight lines between control circles and the first part of the number labelling each circle indicate the order in which the controls must be visited. (The second part of the number is the control code, which lets you verify that the flag you've found is the correct one.) Dashed purple lines indicate a marked (and mandatory) route.
It is OK to visit a control more than once (or visit controls not on your course) as long as there is a subsequence of controls visited that contains the right controls in the right order.
You can make the following assumptions for this problem:
The start and finish are at track junctions.
All other controls are along tracks rather than at track junctions. They can be treated as being in the middle of the track segment (halfway between junctions).
It is possible to change directions at controls and return the way you came without continuing on to the next junction. It is not possible to change direction in the middle of any other track segment.
No shortcuts — you must stay on a track and not cut between tracks.
There aren't any mandatory routes that must be followed.
There are no one-way trails, but note that the speed of travel in one direction may be very different from the other direction. (e.g. going in the uphill direction vs the downhill direction)
Write a program which, given a map with information about the tracks and a course consisting of a start, a finish, and a sequence of control locations (identified by the track segment containing the control), finds the fastest route from the start to the finish that visits all of the controls in the specified order.
The main program class should be named SkiO and the names of the map and course files should be specified (in that order) as commandline arguments — don't prompt the user for the filenames! See the Technical Notes section below if you are not familiar with commandline arguments.
The program should output the total distance traveled followed by a list of all the junctions visited (in order), one per line. The output should go to the console (not written to a file).
Model the problem as a graph problem as discussed in class: vertices correspond to track junctions and control locations, edges correspond to track segments, and the solution in the graph is a series of shortest paths from the start to control 1, from control 1 to control 2, from control 2 to control 3, and so on until the finish is reached. Is the graph directed or undirected? Is it weighted or unweighted?
Choose appropriate data structures and efficient implementations for those data structures. This includes choosing between the adjacency list and adjaceny matrix representation for the graph. Also make use of Java Collections classes where appropriate. You should use the provided code as-is — don't bring in your own versions of the Graph ADT or Dijkstra's algorithm so that you can make changes, instead design your solution to be able to use the provided elements as black boxes.
/classes/cs327/skio/lib/skio-graph.jar contains (partial) adjacency list and adjacency matrix implementations of the Graph ADT discussed in class. There are two packages, graph and directedgraph, for undirected and directed graphs, respectively. Graph, DirectedGraph, Edge, and Vertex are the top-level types to use; AdjacencyListGraph, AdjacencyListDirectedGraph, AdjacencyMatrixGraph, and AdjacencyMatrixDirectedGraph are the concrete classes you can instantiate. Most of the graph operations have been implemented with the exception of removeVertex(v), removeEdge(e), and the directed graph methods to change directions or the directed/undirected status of edges. You shouldn't need to use these methods as there shouldn't be any need to modify the graph structure once built.
/classes/cs327/skio/lib/dijkstra.jar contains implementations of Dijkstra's algorithm for both undirected and directed graphs. These are in the algs package.
To use the provided code, import both jar files (skio-graph.jar and dijkstra.jar) into your Eclipse project (make sure they go into the top-level project folder or some folder other than src), then right-click on the jar files in the Package Explorer and choose Build Path → Add to Build Path. You should see them appear under "Referenced Libraries".
Sample data files are provided in /classes/cs327/skio/data. Map files have the extension .map and course files have the extension .course.
Import the ones you want to use into your Eclipse project; it is recommended that you create a data subdirectory within the top level of the project (not within src) for the data files. Don't put them into src!
The ski-o map file contains information about the individual track segments, one track per line. Each line has the following format:
trackid srcid dstid type length revlength
Each track segment is only listed once e.g. if (J35,J34) is listed, (J34,J35) will not be listed because the (J35,J34) entry includes information about the length of the (J34,J35) segment (as revlength).
A partial example:
T0 J35 J34 dashed 138.0 138.0 T1 J34 J36 dashed 35.0 35.0 T2 J36 J44 dashed 57.0 57.0 T3 J43 J45 dashed 81.0 81.0 T4 J67 J46 dashed 51.0 51.0 T5 J67 J47 dashed 70.0 70.0 T6 J66 J67 dashed 14.0 14.0 T7 J65 J66 dashed 18.0 18.0 T8 J64 J65 dashed 9.0 9.0 T9 J65 J50 dashed 68.0 68.0 T10 J66 J48 dashed 72.0 72.0 T11 J51 J64 dashed 58.0 58.0 T12 J63 J64 dashed 18.0 18.0
The ski-o course file contains information about a specific course. It consists of three lines:
start startid finish finishid controls numcontrols id1 id2 id3 ...
The first line contains the word start followed by the ID of the start junction. The second line contains the word finish followed by the ID of the finish junction. The third line contains the word controls followed by the number of controls and then a list of the IDs for the track segment where each control is located, in order.
An example:
start J183 finish J389 controls 14 T214 T254 T414 T395 T297 T369 T601 T146 T153 T77 T552 T22 T9 T555
Is the answer your program produces correct? That is always the question, and it is more challenging to address when you don't know the answer in advance.
One tactic is to reason carefully — provide a convincing argument why your algorithm is correct and reason about your program to verify that it correctly carries out your algorithm.
A second tactic is to try a small enough input that you can solve the problem yourself to determine the correct answer. The provided files are too big, but you can create your own small graph and run your program on that.
Commandline arguments: Your program should take its input from commandline arguments rather than reading input from the user. Within the program, access commandline arguments using the args array passed to main — don't prompt the user for anything. To specify the commandline arguments for when the program is run in Eclipse:
data/WSOC15-sprint.map data/WSOC15-sprint.course.
Hand in your code by copying your Java files into a folder called skio within your handin directory (/classes/cs327/handin/username).