Operating Systems

DM510, Spring 2015

Daniel Merkle

DM510 Required Assignment 1: C-programming Travel Planning

Download project skeleton here.

Download a train schedule for your test here. It should go in the tests folder.


The goal of this assignment is to teach you to do c-programming, using a real world problem and solving this using algorithms and datastructures you should be familiar with.

This is an individual assignmment, but you are allowed to discuss the overall solution with your peers, and you are allowed to help each other debugging problems in your programs. You will need your c-programming skills later in the course!

The deadline for the 1st mandatory assignment is March 5rd, 11:00. Note, thast the 2nd mandatory assignment will have it's deadline approx. 20 March.

The Problem

This task is to create a program from a train schedule, which finds the best route between two cities. We are of course interested in the journey that takes as little time as possible, but also to change train as few times as possible. We are willing to extend the trip up to 15 minutes if it saves us a change of trains. That is, if we can choose between two routes r1 and r2 of duration t1 and t2, having respectively n1 and n2 changes from one train to another, we will choose r1 if t1 + 15 * n1 < t2 +15*n2. If t1 +15*n1 > t2 +15*n2, we will choose r2, and if t1+15*n1 = t2 +15*n2, the two routes equally good.

Input is a train schedule, a start- and an end-station. The output must be the duration and the number of times you must change trains for the best route from the start to the end station. When there are two routes r1 and r2 of duration t1 and t2 with n1 and n2 changes, and t1+15*n1 = t2 +15*n2 holds, then both t1 n1 and t2 n2 are a correct answer.

The table in the Figure below shows an example of a schedule. If you ask for the best route from Lunderskov to Middelfart, the correct answer would be 42 1.

For your convenience, we pretend in this task that the arrival and departure time is the same at each station and talk only about departure times (in fact, there are typically a few minutes difference of arrival and departure - ie. this simplification means that the calculated travel time may be a few minutes longer than the actual).

Overall procedure

A weighted directed graph must be made, representing the train schedule. For each train line, do the following: (let s1, s2,..., sk be the stations on the line, representing the order they appear on the line)

  • For each station si create a node v(si,a) for each departure a. For 1,2,..., k-1 add an edge from v(si,a) to v(si+1,a). These edges are called external edges.
  • When all trainlines are represented in the graph, including their external edges, do the following for each station s. From each node v(s,a1) add an edge to each node v(s,a2) representing a departure from s, if the departure time for a2 is at least 5 minutes later than the departure time of a1 (i.e. we assume that we need at least 5 minutes to change from one train to another). These edges are called internal edges.

The weight of an external edge is the difference in minutes of the departure times from the nodes of the edge. The weight of an internal edge is the difference in minutes of the departure times from the nodes of the edge plus 15 minutes. Besides the weight information, an edge needs to have an attribute that indicates if the edge is an internal or an external edge, i.e. if it represents a change of trains or not.

The Figure below show the graph (right) representing the train schedule (left). For clarity, not all of the weights are present in the figure. Note that the circles represent nodes in your graph, and the ovals only are depicted for clarity, describing which station the nodes represent.

Århus H, 11:02 Skanderborg, 11:16 Horsens, 11:31 Vejle, 11:48 Fredericia, 12:09 Middelfart, 12:17 Odense, 12:45 Århus H, 12:02 Skanderborg, 12:16 Horsens, 12:31 Vejle, 12:48 Fredericia, 13:09 Middelfart, 13:17 Odense, 13:45 Esbjerg, 10:56 Bramming, 11:07 Vejen, 11:28 Lunderskov, 11:35 Kolding, 11:44 Fredericia, 11:58 Esbjerg, 11:56 Bramming, 12:07 Vejen, 12:28 Lunderskov, 12:35 Kolding, 12:44 Fredericia, 12:58 Esbjerg, 11:48 Vejen, 12:15 Kolding, 12:30 Middelfart, 12:45 Odense, 13:10

The program

Your program should be well structured and commented appropriately.

Running the program

Use the folder assignment1 as your project folder, i.e., use the following directory structure:

assignment1/
assignment1/tests

Your program must compile on a machine in the IMADA terminal room. Extend the Makefile, if you add more files, so it produces a fully functional executable file called travelplanning.

The Makefile has 3 targets:

make
Compiles and generates an executable file
make clean
Removes all generated files
make test
Runs the testsuite

In order to be able to run the testsuite your executable program needs to handle three arguments, namely the file containing the schedule, the departure station, and the arrival station. The output should be exaclty two numbers (formated as shown below), the travel time, and the number of changes. Here are two examples:

user@somemachine:~/assignment1$ ./travelplanning tests/esbjKbh1.in Esbjerg Odense
86 0

user@somemachine:~/assignment1$ ./travelplanning tests/all.in Frederikshavn Køge
416 2

Running time

Let n represent the total number of departures from all stations in total, and let s be the number of stations. Let a be the biggest number of departures from any station. Make sure you can build the graph in time O(max{n log(n), s*a^2}). Hint: make an array of nodes, and sort them by station name and departure time. Iterate the sorted array, when you add internal edges.

When the graph is build, the program must in time O(s*a^2 * log(n) ) compute the duration and the number of changes for a specific route. To reach this running time, you must use Dijkstras algorithm with a priority queue implemented with a binary heap. Use you knowledge from Algorithms and Datastructure :) Check out the section later in the assignment for hints on the binary heap.

Hints

  • There will typically be several nodes that represent the starting station. This can be handled easily by inserting these in the priority queue with weight 0. This is the same as adding an additional node s, and edges from s to each node representing the starting station with weight 0.
  • If you find edges with negative weights, you may have forgotten to handle edges "crossing midnight". You can solve this by adding 1440 to the weight. (There are 1440 minutes on a full day).
  • The Heap from introduction to algorithms does not have anything at location 0 in the array. You can leave this empty, in order for the code to be more like in the book.

Testing your program

Consider which special cases you can encounter, and which errors may occur.

It is a great idea to test the separate components in the program, as you make them.

Report

The primary objective of this project is to program a lot of c-code. You do not have to write a report, but should include a README file in your project, shortly describing the status of your implementation. Is there corner-cases you do not handle, did you not complete the final part, etc.

Submitting your solution

For submitting the sources proceed as follows: Use exactly the following directory structure:

assignment1/
assignment1/tests

You must make sure the program works on an IMADA machine in the terminal room, and you have a file called README in your source folder (assignment1/README). In your project source folder there needs to be an executable called assignment1/travelplanning. In the source folder you need to have the file assignment1/Makefile, which creates the executable by the command make. Running the command make test needs to execute the tests.

To submit your solution change to the directory assignment1 and type aflever DM510 your@mail.com.

Make sure you hand in the project, even if you did not complete it. (Projects may be approved if they indicate a large enough efford to learn c-programming, even if the project does not pass all tests)

The deadline for the 1st mandatory assignment is March 5rd, 11:00 . But please note that it is quite likely the second manadtory assignment will be announced before that day.

Extra challenges

The following are suggestions for extra challenges, that are not required for succesfull completion of the project

  • Remove memory leaks/clean up your memory. This requires to free alle malloc'ed memory, typically in the backwards order.

F.A.Q.

No questions yet :)



Thanks to Lene for the original assignment used in Algorithms and Datastructures.

Design by 1234.info | Modified by Daniel Merkle | CSS 2.0