Description

2      Assignment files

For this assignment you’ll be simulating traffic in city. Specifically you need to complete “trafficSimulator.c”, “trafficSimulator.h’, “road.c”, “road.h”, “car.h”, and “event.h”. You can change any of the other files or create new files but you will need to also submit them as well as your updated makefile. Here is brief description of the functionality of your simulation:

3        Intersections, Cars, and Traffic Lights

Intersections and Roads

• Intersections are the vertices of your graph.
• Each vertex is represented by a unique integer value.
• These range from 0 to size − 1 where size is the number of vertices.
• The roads connecting them are edges of graph.
• Each directed edge is represented by a triple of integers. · The first integer is the starting vertex.
• The second integer is the ending vertex.
• The third integer is the weight of the edge (i.e, the length of this road).
• Cars traverse the edge based on order of arrival (i.e., no passing). You should use an array to represents the current contents of the road. During each time step every car with an empty space in front of it moves forward one position. Example:

Suppose that − is an empty space on the road and the numbers represent 3 cars on the road.

After one time step only cars 1 and 2 are able to move forward. Car 3 is blocked from moving due to car 2.

Traffic Lights and Road Length

• An intersection permits cars from its adjacent roads to pass through at a time.
• Each road has traffic light associated with it. When the light is green, the car on the front of the road may attempt to pass through the intersection towards its destination.
• The times in which the light is green/red and allows traffic through is specified in the input (we omit yellow lights for the sake of simplicity). The light operates on a cycle and repeats the specified pattern for the duration of the simulation. This is specified with the following three int inputs (see also Section 6):
• <green on> – The cycle the light turns green (light starts as red)
• <green off> – The cycle the light turns back to red
• <cycle resets> – The cycle resets goes back to 0
• The order the roads should be processed in is same as the order in which they were added to the graph. Hint: It will be useful to store the roads in an array based on this order.
• The length of a road also denotes the maximum number of cars which can be on it (see Section 4 for an important addition to this).
• A car can only pass through the intersection if the next road on its shortest path has an empty space on the end of its array.

Cars

• The destination of each car is an intersection.
• A car is removed from the simulator once it moves off the front of the road at its destination.
• Cars always follow a shortest path to their destination.
• Note that this shortest path is based on the lengths of the roads and

not on how many cars are currently on the roads.

• You should call the graph.c function “getNextOnShortestPath” to find the next intersection on a shortest path.
• You will want to track the number of time cycles the car took to reach its destination in order to report your results at the end of the simulation.

4     Events

It is recommended that you store the events in a priority queue based on the time step it is supposed to occur on.

Event – Adding Cars

• The input file will also specify time steps in which more cars should enter the simulation.
• Print the following on the time step this event occurs:
• “CYCLE X – ADD CAR EVENT – Cars enqueued on road from Y to Z”
• X is the time step this event occurred on. The road of the event is from Y to Z.
• These cars should be added to the end of a queue associated with the specified edge (Hint: the merge function in queue.c may come in handy here). For each time step remove the first car in the queue and place it at the end of the road array of the edge if possible.

Event – Printing Road Contents

• The input file will also specify time steps in which the contents of all of your roads should be printed. See provided output for examples of what this will look like.
• Print the following on the time step this event occurs:
• “CYCLE X – PRINT ROADS EVENT – Current contents of the roads:”
• X is the time step this event occured on.

5      Output

• Once a car reaches its destination you should print the following:
• “CYCLE W – Car successfully traveled from X to Y in Z time steps.”
• W is the time step the car reached its destination. X and Y are respectively the starting intersection and destination of this car. Z is the number of time steps since the car was added to the simulation.
• The simulation ends once all of the cars reach their destination and there are no more events left to process. You should print the following:
• “Average number of time steps to the reach their destination is X.” · “Maximum number of time steps to the reach their destination is Y .”
• X is average number of time steps taken by the cars to reach their destination. Y is maximum timesteps taken by any car to reach its destination.
• Alternatively, if the simulation goes through a full cycle of every traffic lights with no car being able to move then the city is in gridlock and the simulation halts (Hint: to determine this it will helpful to track the longest traffic light cycle as well as when a car was last able to move).
• Output “CYCLE Z – Gridlock has been detected.” · Z is the current time step.

6      Input File Format

<# of vertices> <# of edges>

<TO: 1st vertex> <number of incoming roads>

<FROM: 1st vertex> <length>                                   <green on> <green off> <cycle resets>

<FROM: 2nd vertex> <length>                                 <green on> <green off> <cycle resets>

…

<FROM: last vertex> <length>                                  <green on> <green off> <cycle resets>

<2nd vertex> <number of incoming roads>

…

<last vertex> <number of incoming roads>

<# of “add car” commands>

//1st add car command

<“from” of starting edge> <“to” of starting edge> <timestep to perform “add car” on>

<number of cars to add to this edge>

<dest. vertex of 1st car> <dest. vertex of 2nd car> … <dest. vertex of last car> //2nd add car command

<“from” of starting edge> <“to” of starting edge> <timestep to perform “add car” on>

<number of cars to add to this edge>

<dest. vertex of 1st car> <dest. vertex of 2nd car> … <dest. vertex of last car> …

//last add car command

<“from” of starting edge> <“to” of starting edge> <timestep to perform “add car” on>

<number of cars to add to this edge>

<dest. vertex of 1st car> <dest. vertex of 2nd car> … <dest. vertex of last car>

<# of “print road” commands>

<cycle # to print roads on> <cycle # to print roads on> … <cycle # to print roads on>

7     Simulation

Below is the order of operations that your program should go through for each time step:

• Dequeue and execute any and all events associated with the current time step.
• For each road, attempt to move the first car on it through the intersection and to the end of the next road on its shortest path. Cars that have reached their destination intersection are removed from the simulation.
• For each road, cars which had empty spaces in front of them at the start of this time step move forward one space.
• For each road, Attempt to move a car from the add car queue for that road onto the last position on the road.

Repeat the above until all events have finished and either all cars have reached their destination or gridlock has occurred.

8     Deliverables:

Your solution should be submitted as “trafficSimulator.c”, “trafficSimulator.h’, “road.c”, “road.h”, “car.h”, and “event.h”. Also include any other files you’ve created to solve the problem (including possibly a new “makefile”).

Upload these file to Blackboard under Assignment 6. Do not zip your files.

To receive full credit, your code must compile and execute. You should use

valgrind to ensure that you do not have any memory leaks.