(Solved): The road network A road network can be modelled as a graph. Nodes in the graph represent intersec ...

The road network A road network can be modelled as a graph. Nodes in the graph represent intersections and locations. Each node is assigned an ID number for ease of identification. Edges between nodes represent roads. The graph is directed, as it is possible for roads to allow travel in one direction but not the other (e.g. one-way streets). One sample road network is 5 4 6 The Second Lock shown below: 2 0 3 1 Note in this sample network the yellow squares represent intersections while the blue circles represent locations. A vehicle will leave one location node, potentially travel through a number of intersections, then arrive at another location node. Note also that not every route through an intersection can be traversed simultaneously. For example, intersection 0 in the diagram above would not likely allow a car to travel from 2 to 3 at the same time as another car is travelling from 1 to 4 as this would result in a collision. To describe this behavior, we can consider a particular traffic signal which identifies which paths through the intersection can be traversed at any point in time. This can be modelled as a list of (source, destination) pairs. For example, [(5,6), (6,5)] is a traffic signal for intersection 4 that indicates that cars can travel from node 5 to node 6 or from node 6 to node 5. We can then describe the intersection as a list of traffic signals, each of which is active for one timestep and cycle back to the first traffic signal after the final signal has completed. For example, [[(5,6), (6,5)], [(0, 6), (6, 0), (5,0), (0, 5)]] indicates: • At timestep 0 cars can travel from 5 to 6 or from 6 to 5 • At timestep 1 cars can travel from 0 to 6, 6 to 0, 5 to 0 or 0 to 5 • At timestep 2 cars can travel from 5 to 6 or from 6 to 5 etc... To simplify our model, we will assume that an intersection allows at most one vehicle through in each permitted direction at each timestep. For example, at timestep 0 one vehicle may travel from 5 to 6 and one vehicle may travel from 6 to 5. All other vehicles must wait at the intersection. Once a vehicle has exited the intersection it will be placed on the road taking it towards the next intersection or location node. For simplicity, we assume it will take a fixed number of timesteps to traverse the road. Each car will begin its journey at one of the location nodes and potentially travel through one or more intersections until it reaches its final destination node. Question 1 Write a function load_road_network(filename) that parses a file with the structure described below and returns a tuple containing two dictionaries. The first dictionary should represent the intersections. The keys of this dictionary should be the ID numbers of each intersection and the values should be the corresponding list of traffic signals. The second dictionary should represent the roads. The keys of this dictionary should be tuples containing the source and destination nodes of the road, and the values should be the number of timesteps required to traverse the corresponding road. The structure of the file is as follows: • The text '#Intersection: followed by the ID number (a positive integer or zero) of an intersection • An arbitrary number of lines each corresponding to a traffic signal for that intersection. The traffic signals are expressed as a sequence of source, destination pairs. Each source, destination pair is encased by brackets and separated from the next pair by a semicolon (;). The source and destination are both integers >= 0, and there must be at least one pair per traffic signal in the text file. The points above are repeated for each intersection in the road network After the intersections have been specified, the text #Roads" is used to indicate that the remainder of the file will specify road traversal times Each subsequent line describes a road, using the format (source, destination):time There may be an arbitrary number of blank lines following the definition of each intersection. Below is a sample function call: >>> intersections_list, roads_cost = load_road_network ('road_sample.txt') >>> print (intersections_list, '\n', roads_cost) {0: [[(4, 1), (1, 4)], [(2, 3), (3, 2)], [(4, 2), (2, 4), (1, 3), (3, 1)], [(1, 2), (2, 1), (4, 3), (3, 4)]], 4: [[(5, 6), (6, 5)], [(0, 6), (6, 0), {(0, 1): 1, (1, 0): 1, (0, 2): 1, (2, 0): 1, (0, 3): 1, (3, 0): 1, (0, 4): 3, (4, 0): 3, (4, 5): 2, (5, 4): 2, (4, 6): 2, (6, 4): 2) 1 # DO NOT DELETE/EDIT THIS LINE OF CODE, AS IT IS USED TO PROVIDE ACCESS TO 2 # A WORKING IMPLEMENTATION OF THE FUNCTION FROM Q1 Question 2 3 from hidden import load_road_network 4 A path through the road network can be described by listing each node the vehicle will travel through. For example, the path [2,0,4,6] would indicate that the vehicle starts at node 2, travels through nodes 0 and 4 then arrives at node 6. Recall that the first and last nodes must be location nodes, while all other nodes must be intersections. In this task we wish to understand: 5 def path_cost(path, intersections, road_times): #TODO: Write your function here 6 • Whether a vehicle starting its journey at timestep 0 is able to traverse the path without being stopped at any intersection, assuming there are no other vehicles on the road network • How long that journey would take Write a function path_cost(path, intersections, road_times). If it is possible to traverse the path starting at timestep 0 without being stopped at any intersections then the function should return the total number of timesteps taken. If not, it should return None. You may assume that the path is a valid, traversable path. Your function should take the following arguments: . path is a list representing the nodes through which the vehicle will traverse • intersections and road_times are the dictionaries that represent the road network, as described in Question 1. A working implementation of the load_road_network function has been made available, you may make calls to this function if you wish. You may assume that a vehicle moves in the timestep during which it enters the road network. For example, if a vehicle enters the network at node 1 at timestep 0 travelling towards node 2 and the distance between nodes 1 and 2 is 1 timestep, then the vehicle would arrive at node 2 at timestep 1. You may further assume that it takes O time to cross an intersection with a favourable traffic signal. A vehicle may cross an intersection and drive along a road during the same timestep only if the vehicle crosses the intersection before driving along the road. For example, consider the following function call: >> simple intersections = {0: [[],[(1,2), (2,1)]]} >> simple_roads = {(0,1):1, (1,0):1, (0,2):1, (2,0):1} >> path_cost([1,0,2], simple intersections, simple_roads) The vehicle's journey will be as follows: • Timestep 0: Depart node 1 heading towards intersection 0 • Timestep 1: Arrive at node 0 and pass through the intersection unimpeded • Timestep 2: Arrive at final location node 2 path_cost([1,0,2], simple intersections, simple_roads) should therefore return a value of 2. Below are some sample function calls: >> simple intersections = {0: [[],[(1,2), (2,1)]]} >> simple_roads = {(0,1):1, (1,0):1, (0,2):1, (2,0):1} >> print (path_cost([1,0,2], simple intersections, simple_roads)) 2 >> simple intersections = {0: [[(1,2), (2,1)], [1]} >> simple_roads = {(0,1):1, (1,0):1, (0,2):1, (2,0):1} >> print (path_cost([1,0,2], simple_intersections, simple_roads)) None >> intersections, road_times = load_road_network( 'road_sample.txt') >>print(path_cost([2,0,4,6], intersections, road_times)) None - land and naturale/Leand cala ++11 A intarenctione Submissions Autosaved <> Output # DO NOT DELETE/EDIT THIS LINE OF CODE, AS IT IS USED SED TO PROVIDE ACCESS 2 # WORKING IMPLEMENTATIONS OF THE FUNCTIONS FROM Q1 & 2 Question 3 3 from hidden import load_road_network, path_cost 4 We now wish to consider a road network with multiple cars traversing it. In order to do that, we need to be able to identify which vehicles will be able to pass through a crowded intersection at any given time. We can represent each car currently waiting at an intersection by a tuple (car_id, path, arrival time): 5. def intersection_step(intersections, road_times, intersection_id, 6 cars_at_intersection, timestep): 7 • car_id is an integer that uniquely identifies a particular car. #TODO: Write your function here • path is a list representing the path that the car will take through the network. • arrival time is an integer representing the timestep in which the car arrived at the intersection. In this task, we will write function to process a single step through time at a given intersection. Write a function intersection_step(intersections, road_times, intersection_id, cars_at_intersection, timestep). This function should return a list containing the car_id of each car that will be allowed to proceed through intersection intersection_id at the current timestep, sorted by car_id. Recall that in our representation, only one vehicle can travel through in each permitted direction at any given timestep. If multiple vehicles are waiting to move through in the same direction, the vehicle that arrived at the intersection first should be given priority. Note that it is not necessary to track a vehicle's path through the network determine when it arrived at the intersection, you may rely on the specified arrival time. If two vehicles arrive at the same timestep, you may pass the one with the lower car_id. You may assume that each car will only visit intersection once as part of its path, and that a car's final destination will never be an intersection. The function will take the following arguments: • intersections and road_times are the dictionaries representing the road network, as imported in Question 1 intersection_id represents the ID of the intersection we are considering cars_at_intersection is a list of cars present at the intersection represented by intersection_id at the current timestep. Each car is described by the 3-tuple above. . timestep is an integer representing the current timestep Below are some example function calls: >> simple intersections = {0: [[], [(1,2), (2,1)]] } >> simple_roads = {(0,1):1, (1,0):1, (0,2):1, (2,0):1} >> cars_at_intersection = [(0,[1,0,2], 1), (1, [2,0,1], 1)] >> intersection_step(simple_intersections, simple_roads, 0, cars_at_intersection, 1) [0, 1] >> simple intersections = {0: [[], [(1,2), (2,1)]] } >> simple_roads = {(0,1):1, (1,0):1, (0,2):1, (2,0):1} >> cars_at_intersection = [(0,[1,0,2], 1), (1, [2,0,1], 1)] >> intersection_step(simple_intersections, simple_roads, 0, cars_at_intersection, 2) [] >> intersections, road_times = load_road_network( 'road_sample.txt') >> cars_at_intersection = [(0, [2,0,4,6], 1), (1, [3,0,4,6], 1), (2, [1,0,4,6], 1), (3, [2,0,4,6], 2)] >> intorcortinn ston/intercortinne road timac A rare at intercortion 21 Working implementations of the load_road_network and path_cost functions have been made available, you may make calls to these functions if you wish. Submissions Autosaved <> Output 2 # WORKING IMPLEMENTATIONS OF THE FUNCTIONS FROM Q1, 2 & 3 Question 4 from hidden import load_road_network, path_cost, intersection_step 4 5 def simulate (intersections, road_times, cars_to_add): We now wish to simulate the running of the entire road network. The simulation will involve cars entering the road network, proceeding through the network to their destination, and leaving the road network at different times. Write a function simulate(intersections, road_times, cars_to_add). Your function should track the position of each vehicle in the road network at each timestep, starting from timestep 0. Your function should return a list of actions specifying what each car currently in the road network is doing at each timestep. Valid actions are: 6 #TODO: Write your function here • drive(timestep, car_id, source_node, destination_node) - This represents a car identified by car_id that is traversing the road between source_node and destination_node at timestep • wait(timestep, car_id, intersection_id) - This represents a car identified by car_id that is waiting at intersection intersection_id at timestep • arrive(timestep, car_id, destination) - This represents a car identified by car_id having arrived at destination at timestep Each action should be represented as a string. The list of actions should be sorted first by timestep and then by car_id. Your function should take the following arguments: • intersections and road_times are the dictionaries representing the road network, as imported in Question 1 • cars_to_add is a list that represents the cars that will be added to the road network as part of the simulation. Each car is described as a tuple (car_id, path, timestep). This tuple represents a unique car_id for each car that will be added, the path that car will take through the network, and the timestep in which the car should begin its journey. A car may be removed from the simulation after it has arrived at its destination. Your simulation should continue until all cars currently in the road network have reached their destination, and there are no additional cars waiting to be added to the simulation. Below are some sample function calls: >> simple intersections = {0: [[(1,2), (2,1)]]} >> simple_roads = {(0,1):1, (0,2):1, (1,0):1, (2,0):2} >> simple_cars_to_add = [(0, [1,0,2], 0)] >> simulate (simple_intersections, simple_roads, simple_cars_to_add) ['drive (0, 0, 1, 0)', 'drive(1, 0, 0, 2)', 'arrive (2, 0, 2)¹] >> intersections, roads_cost = load_road_network ('road_sample.txt') >> cars_to_add = [(0, [2,0,3], 3), (1, [3,0,2],3)] >> simulate (intersections, roads_cost, cars_to_add) ['drive (3, 0, 2, 0)', 'drive(3, 1, 3, 0)', 'wait(4, 0, 0)', 'wait(4, 1, 0)', 'drive(5, 0, 0, 3)', 'drive(5, 1, 0, 2)', 'arrive (6, 0, 3)', 'arrive (6, Working implementations of the load_road_network, path_cost and intersection_step functions have been made available, you may make calls to these functions if you wish. Submissions Autosaved <> Output Question 5 In addition to implementing your solutions, you are also required to submit a set of test cases that can be used to test your Question 4 simulate function. You should aim to make your test cases as complete as possible. That is, they should be sufficient to pick up incorrect implementations of the simulation. Your set of test cases may assume that the input passed to your function will be of the correct types and will be well-formed. Your test cases suite will be evaluated by running it on several known incorrect implementations, in which it should detect incorrect behaviour, ie, returning an incorrect list of actions. You should specify your test cases as a series of calls to the function test simulate(input_args, expected_return_value), where the first argument input_args contains a tuple of (intersections, road_times, cars_to_add) representing the call to simulate (described in Question 4) and expected return value is the expected return value from the function simulate, namely a list of actions that occurred within the simulation (as in Question 4). That is, you must specify both the arguments and return value for simulate as arguments to test simulate. For example, using the first example in Q4: test_simulate (({0: [[(1,2), (2,1)]]}, {(0,1):1, (0,2):1, (1,0):1, (2,0):2}, [(0, [1,0,2], 0)]), ['drive(0, 0, 1, 0)', 'drive (1, 0, 0, 2)', 'arrive (2, ?