Project 3: Discrete Event Simulator
You are a traffic engineer, and you want to study the traffic patterns in
a metro city. The city is a network of roads, represented as an
undirected graph with each edge representing a road, and each vertex
representing a station. For example, Chandigarh is connected to Ropar, and
Ropar to Nangal, and so on. The weight on an edge represents the time it would
take to traverse that road. In our example, the weight of the edge between
Chandigarh and Ropar would be around 60 (in minutes), and the weight of the
edge between Ropar and Nangal would be 120.
We model traffic as the number of cars moving on any road at any given time
in one direction. For example, there could be 50 cars moving from Ropar to
Chandigarh, and 100 cars moving from Chandigarh to Ropar at the same time.
A car may need to travel multiple roads to reach it's destination. In our
small example, for a car to travel from Chandigarh to Nangal, it would first
have to travel from Chandigarh to Ropar, and then from Ropar to Nangal.
You are required to write a program to simulate this traffic network. In
the input, you will be given a graph representing a network of roads using
an adjacency matrix. You will also be given the route-information in the form
of a next-hop matrix. A car trying to reach destination D from source S, will
consult the next-hop matrix to decide which road to take. For example if
NextHop[S][D] is node N, then the car would take the road S-N to reach D.
Once, it reaches N, it will again consult NextHop[N][D] to determine the
next station; and so on, until it reaches D. All cars start moving
at one of the stations and end at their destination (which is another station).
We will provide the start times of the cars, their starting stations and their
destination stations in the form of a vector (see sample input files).
You must use a priority queue ADT implemented using a binary heap to
implement this simulator.
You should assume a dynamic
traffic model. i.e., the time taken by a car on a road also depends on the
traffic on that road in that direction. The time it
would take for a car to travel on a road with traffic is given by the
following relation:
Wdynamic = Wstatic + &alpha * Traffic
Wstatic = the static edge weight.
Traffic = number of cars on that edge in that direction (2-lane road) when the car started moving on that edge.
&alpha = weighting factor.
Your program should be called TrafficSim and should take two arguments: a
filename which contains the adjacency matrix, the next-hop matrix and the
car-departure information; and the parameter &alpha .
TrafficSim <filename> <&alpha>
As an example, using &alpha = 0 would mean that we ignore the traffic
information completely while determining the travelling time. &alpha is
a floating point number (e.g., 0.5, 1.25, 2.0, etc..).
You are required to output the times at which each car reaches it's
destination in the form of a vector.
The arrival times of the cars should be printed on the standard
output. No other extraneous information should be printed on standard output.
(see sample output).
Input format:
num-nodes
Adjacency Matrix
num-nodes
Next-hop Matrix
Car departure information
The adjacency matrix and the next-hop matrix are in the standard representation.
The car departure information is given as (one per line):
time-epoch car-id departure-terminal destination-terminal
The output information should be in the form (one per line):
time-epoch car-id
signifying that the car "car-id" reached it's destination at time "time-epoch".
The output should be sorted by time-epoch.
Finer details
- Q: When a car starts on a road, is it to be counted in traffic to find
the time the car would take to reach the next node? In short, is a car
traffic for itself?
A: No. A car does not count as traffic for itself.
- Q: Can two cars start simultaneously on a road? If yes, will one be
counted as a part of the traffic for the other?
A: Yes, it is possible for two cars to start simultaneously (or near
simultaneously to be precise). In this case, resolve the conflict by
allowing the car with the lower
ID-number to logically start first. This means that the
the car with the lower ID number counts as traffic for the car with
the higher ID number, but not vice versa.
- Q: What if cars get off the road at one endpoint at the
same time as a car starts on that road at the other end point.
Should the car getting off the road be counted as traffic for the
car getting on the road at the same time?
A: No. The car getting off the road should not be counted as traffic
for cars getting on the road at exactly the same time. In other words
you should unload all cars from all edges before loading any new cars
on an edge at a given instant of time.
- Q: Will the input for the cars be sorted with respect to car number as
in sample input?
A: Not necessary.
Support files:
- Sample input
- Sample output (does not correspond to sample input, just tells you the syntax).
- Another sample input