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 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

Traffic = number of cars 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 .

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).

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.

- 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.

- Sample input
- Sample output (does not correspond to sample input, just tells you the syntax).
- Another sample input