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:
Adjacency Matrix
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
  1. 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.
  2. 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.
  3. 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.
  4. Q: Will the input for the cars be sorted with respect to car number as in sample input?
    A: Not necessary.
Support files:
  1. Sample input
  2. Sample output (does not correspond to sample input, just tells you the syntax).
  3. Another sample input