| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Using the code provided in /classes/cs327/skio, implement the ski-o route finding problem from homework 13 as discussed below.
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. Review homework 13 for more specifics on the problem.
The program should be run as follows:
java SkiO mapfile coursefile
The main program class should be named SkiO and the names of the map and course files should be specified on the commandline — don't prompt the user for the filenames!
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).
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.
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.
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 (you can also try to find some counterexamples to boost your confidence, though a lack of counterexamples does not by itself prove correctness), and reason about your program to verify that it correctly carries out your algorithm.
A second tactic is to solve the problem yourself. This is difficult for large inputs (such as the sprint map for the ski-o problem), so an option is to create your own small graph and run your program on that.
You are encouraged to use Eclipse, though it is not required. It is recommended that you use Java 17 though probably everything will be fine with an older version. This software is available on the lab computers in Rosenberg 009 and Lansing 310, or you can set up your own computer. Note that you do not need JavaFX for this assignment so you can skip that part for now.
Commandline parameters in Eclipse: 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:
java SkiO WSOC15-sprint.map WSOC15-sprint.courseenter WSOC15-sprint.map WSOC15-sprint.course for the program arguments. Note that if you keep the directory structure of the provided code (with the data files in a data subdirectory of your project), you will need to specify the pathnames as data/WSOC15-sprint.map data/WSOC15-sprint.course — they are relative to the top level of the project.
Hand in your code by copying your Java files into a folder called skio within your handin directory (/classes/cs327/handin/username).