ECS 60 Programming Assignment #4 (50 points) Summer Session II
This assignment must be done in pairs. You should only submit one solution per pair. Be sure to put both people’s names on all files.
What to submit: a Makefile, executable called “taxi.out” and all the code files needed to build your solution on the CSIF linux machines. Do not submit object files. Use handin to turn in your files to cs60 p4.
Overview
For this assignment, you will create a simulation of a taxi company operating in a small town. You will use a graph to represent a map of the town. Each intersection will be given a unique number. Clients will call the dispatch centre and ask for a taxi to pick them up at a particular location and take them to a requested destination. The dispatcher must decide which taxi to assign to each incoming request. It will also determine the route the taxi would take, being as efficient as possible. The program will simulate the progress of the taxis over time as they drive around town, picking up passengers and dropping them off.
This is a discrete time simulation, meaning that events will be simulated by sequentially advancing time a set amount (a “time step”) and updating the progress of all the “actors” in the system for that time step. In this case, the “actors” are the taxis and the update involves moving them around the map an appropriate amount. Note, taxis are only moved when they are on a call. Otherwise, they remain at the same intersection until they are dispatched.
Various events can occur during the simulation, and these can be divided into two categories, internal and external, as summarized below. Study the output files from the sample run to make sure you are clear on what should be displayed with each event. You will be marked largely based on this output.
External Events
“call”:
A person calls the taxi company and requests a pickup for a certain location. When this event happens, the dispatcher must:
a) decide which available taxi (one that is not currently on a call) is closest to the client
b) assign that taxi to the client
c) calculate the most efficient route to reach the client (this can be done by the taxi or the dispatcher)
d) print out which taxi is being dispatched, the customers starting location and destination and the route the taxi will take to get to the passenger.
Format: c <start location> <destination> e.g. c 4 17
“time step”:
A time step is an increment of your simulation. You should move every taxi that is on a call along its route. I’ve made a couple of simplifications here. The time step will always be 1. The edge weights will represent the number of time steps required to transverse the corresponding edge. Edge weights will be integers greater than or equal to 1. So for example, if an edge has weight 4 it will take four time steps for a taxi to drive across the edge.
Format: t <amount of time>
e.g. t 1
“map”:
The map event specifies the road map (i.e. graph) that represents the possible routes for the taxis.
Format: m <# of vertices> <v_startOfEdge> <v_endOfEdge> <edge weight> (the last three entries can be repeated for each edge)
e.g. m 35 0 1 5 1 0 5 1 2 2 2 1 5
Note that the map is directed. This is a partial specification. It says there are 35 vertices (numbered 0 to 34), and specifies the following edges: (0,1), weight 5; (1,0), weight 5; (1,2) weight 2; (2,1) weight 5.
“reset”:
Sets the location of each taxi to a specified vertex and sets the taxis status to available. There are five taxis in the simulation, R, B, G, Y, P (the letters stand for Red, Blue, Green, Yellow and Pink)
Format: r <taxi name> <vertex> <taxi name> <vertex> … e.g. r R 1 B 3
Internal Events
Internal events reflect something occurring within the simulation that is not triggered by an external call.
“taxi arrives at client’s start location”:
Once dispatched, the taxi must travel to the location of the client. When the taxi arrives, it must do the following:
a) plan a route to the passenger’s requested destination.
b) print out a message indicating that the passenger has been picked up and the taxi name. Print out the route the taxi will take to drop off the passenger.
“taxi arrives at passenger’s destination”:
Once the taxi arrives at the destination of the passenger, it must do the following:
a) Print out a message indicating the taxi’s name and that it has reached the destination. b) Make itself available to pick up other passengers.
Simulation Run
All the external events are specified in a data file “test.dat”. You will be provided with code that reads this file and triggers the associated events. You will need to implement the code that handles the events. Look through the sample file and associated output to see how the process works. We will use a different “event file” when testing your code, but it will be similar in nature.
Assumptions, Directions and Hints
You can assume that the input data for external events is correct.
You can assume that there will always be a taxi available when a customer calls.
Use Dijktra’s algorithm to calculate the routes and distances. You may find that you don’t need to call it every time you need to check a distance, but be sure that you are using data that is current for the given check
You can use the following line as part of code that will go from a taxi index to a taxi name:
string taxiNames[]={“RED”,”BLUE”,”GREEN”,”YELLOW”,”PINK”}; You should use an adjacency list to represent your graph.
The included header files are a big hint (see below).
Sample code
In the CSIF Linux directory ~neff/60/p4 you are given code for TaxiMain.cpp, Dispatcher.h, Taxi.h and Graph.h
The file TaxiMain.cpp contains the driver that runs the simulation. For every event, it makes a call to the Dispatcher which implements the associated functionality. Graph implements the graph ADT that you will use to represent your map. Taxi contains methods used to track and update each taxi.
TaxiMain.cpp is the file we will use when testing your code. You must NOT change this file. You must implement the functions in the CDispatcher class which are called in TaxiMain.cpp. You can change the other header files as needed. They are from my solution. They give you a lot of hints as to how you could solve this problem. There are other solutions, though, so you are free to make adjustments as you like. Aim for a clean, efficient solution. Be sure to comment your code.
You can make use of the STL to make your job easier. “string” and associated stream classes are quite useful. I also made use of the list class. You should write your own CGraph class.
The following example shows how I pulled the data I needed out of the parameter string:
//"teleport" the taxis to given locations and set their status to be available
void CDispatcher::SetTaxiLocations(string buf)
{
istringstream tBuf(buf);
//dump command from buffer
char command, taxi;
tBuf>>command;
int location;
//position all the taxis
while(!tBuf.eof())
{
tBuf>>taxi;
tBuf>>location;
int index;
switch (taxi)
{
case 'R':
index = RED;
break;
case 'G':
index = GREEN;
break;
case 'B':
index = BLUE;
break;
case 'Y':
index = YELLOW;
break;
case 'P':
index = PINK;
break;
default:
assert(false);
}
m_taxis[index].SetLocation(location);
}
There are two additional files:
test.dat : This file contains test events to exercise your code. Feel free to modify it as you like to test your own code.
output.txt : This file contains the results of running the code on test.dat.
}