Problem Set 2: Routing and Path Optimization

Objectives:

• Create data structure representations of directed graphs
• Use Dijkstra’s algorithm to find the best path between two nodes on a graph
• Apply computing and data analysis to an urban studies and planning problem

Collaboration:

• Students may work together, but students are not permitted to look at or copy each other’s code or code structure.
• Each student should write up and hand in their assignment separately.
• Include the names of your collaborators in a comment at the start of each file.
• Please refer to the collaboration policy in the Course Information for more details.

Introduction

MIT’s Urban Science Department has a project where they want students to help implement an algorithm to find the optimal path for traveling between two nodes on a graph. After learning about searching and pathfinding in 6.0002, you decide to take on the task. In this pset, you will find the “best” driving route from home (N0) to work (N9) given a set of conditions, and help other drivers find the “best” driving route between other nodes.

Here is the map of our road network. The map has 10 nodes (“N0”, “N1”, ... , “N8”, and “N9”) and has 13 roads of various types. The roads include some local roads that pass through the quiet little town of Smootsville, as well as interstate roads.

For this pset you will work with a simplified version of this road network in road_map.txt. You can assume that we will only have 4 road types, “local”, “bridge”, “interstate”, “arterial”.

We will be working with an undirected road network in this pset, i.e. each road can be traversed in both directions. For simplicity, we will represent roads as two directed roads. One for each direction that the road can be traversed.

Getting Started:

Download ps2.zip from the problem set website. This folder contains the following files:

• ps2.py​: code skeleton
• graph.py: a set of graph-related data structures (RoadMap, Node, and DirectedRoad) that you must use
• maps/road_map.txt​​: a data file holding information about the road network
• ps2_tester.py​: basic tests for your code

Make sure all these files are saved in the same directory.​ Please do not rename these files, change any of the provided helper functions, change function names, or delete docstrings.

Please review the Style Guide for good coding practices.

Problem 1: Creating the Data Structure Representation

In graph.py, you’ll find the Node class, which has already been implemented for you. You will also find skeletons of the DirectedRoad and RoadMap classes, which we will use in the rest of this problem set.

Complete the DirectedRoad and RoadMap classes as specified by the docstrings in graph.py.

Your DirectedRoad class will need to implement the __str__ method (which is called when we use print() on a DirectedRoad object) as follows:

Suppose we have a DirectedRoad object o containing the following information:

Source node name: 'N0' Destination node name: 'N1' Time in minutes along the road: 10 Type of road: 'interstate'

Then print(o) should return: N0 -> N1 takes 10 minute(s) via interstate road

For RoadMap, you will need to implement the get_roads_for_node, has_node, add_node, add_road methods.

Note 1: In the add_node() method, you have to add a node to the self.nodes attribute of RoadMap. Note that we initialize self.nodes as a set() object. In Python, a set is an unordered group of unique elements, meaning if you try to add an element that is already in the set, it will still only occur in the set once. Adding an element to a set can be done by using the set.add(element) method. (This is the only thing we will need sets for in this pset, but to read more about sets, you can look at this tutorial or the python set documentation.)

Note 2: All road travel times should be stored as integers.

You should now pass the test test_1_graph_add_existing_node_raises, test_1_graph_add_node, test_1_graph_add_road, test_1_graph_add_road_to_nonexistent_node_raises, test_1_graph_get_all_nodes, test_1_graph_str, test_1_graph_weighted_edge_dest, test_1_graph_weighted_edge_src, test_1_graph_weighted_edge_str, test_1_graph_weighted_edge_total_time, test_1_graph_weighted_edge_type in ps2_tester.py.

Problem 2: Building the Road Network

For this problem, you will implement the load_map(map_filename) function in ps2.py, which reads in data from a file and builds a directed graph to represent the road network. Think about how you will represent your graph before implementing load_map.

2A: Designing your graph

Decide how the road network problem can be modeled as a graph. What do the graph’s nodes represent in this problem? What do the graph’s edges represent in this problem? How are the travel times represented?

2B: Implementing load_map

Implement load_map according to the specifications provided in the docstring. You may find this link useful if you need help with reading files in Python (refer to section 7.2).

Road Network Text File Format:

Each line in road_map.txt has 4 pieces of data in the following order separated by a single space:

1. The start node
2. The destination node
3. The time in minutes to go between the two nodes
4. The type of road connecting these two nodes

For example:

N0 N1 15 interstate 
N1 N3 6 interstate 
N3 N6 5 local

The text file contains a line with this data for each pair of adjacent nodes in our network.

However, the text file only includes each pair of adjacent nodes once. All roads can be traversed in both directions, so a DirectedRoad object will need to be created for each direction between two nodes.

2C: Testing load_map

Test whether your implementation of load_map is correct by creating a text file, test_load_map.txt, using the same format as ours (road_map.txt), loading your txt file using your load_map function, and checking to see if your directed graph has the correct nodes and edges. We have already implemented the __str__ method for RoadMap, so you can print a RoadMap object to see which roads it contains. You can add your call to load_map directly below where load_map is defined, and comment out the line when done. Your test case should have at least 3 nodes and 3 roads, and should be different than the example test_load_map.txt below.

For example, if your test_load_map.txt was:

a b 3 local
a c 2 interstate
b c 6 bridge

Then your load_map function would return a digraph with 6 edges (in any order):

a -> b takes 3 hours via local road
b -> a takes 3 hours via local road
a -> c takes 2 hours via interstate road
c -> a takes 2 hours via interstate road
b -> c takes 6 hours via bridge road
c -> b takes 6 hours via bridge road

Submit test_load_map.txt when you submit your pset. Also, include the lines used to test your test_load_map.txt at the location specified in ps2.py, but comment them out.

You should now pass the test test_2_ps2_load_map in ps2_tester.py.

Problem 3: Shortest Path Using Dijkstra’s Algorithm

We can define a valid path from a given start to end node in a graph as an ordered sequence of nodes [n_1, n_2, ... n_k] , where n_1 to n_k are existing nodes in the graph and there is an edge from n_i to n_i+1 for i=1 to k - 1. In Figure 2, each edge is unweighted, so you can assume that each edge has distance 1. Thus, the total distance traveled on the path is 4.

In our routing problem, the ​​total time traveled​​​ on a path is equal to the sum of the times traveled between adjacent nodes on this path. Note that there may be multiple valid paths from one node to another with different total times traveled. We define the ​​shortest path​​ between two nodes to be the path with the ​​least total time spent travelling​​​.

How do we find a path in the graph? Work off Dijkstra’s algorithm covered in lecture to discover each of the nodes and their children nodes to build up possible paths. Note that you’ll have to adapt the algorithm to fit this problem. You can read more about Dijkstra’s algorithm here.

3A: Objective function

What is the objective function for this problem?

3B: Implement get_optimal_path

Implement the function get_optimal_path. This function uses Dijkstra’s algorithm to find the shortest path in a directed graph from the start node to the end node under the following constraint: you do not pass on any roads from the types listed in restricted_roads. The function then returns the ​(shortest path​, shortest time) ​tuple.​ ​​Below is some pseudocode to help get you started:

function get_optimal_path(roadmap, start, end, restricted_roads):
   if either start or end is not a valid node:
       return None
   if start and end are the same node:
       return ([start], 0) # Empty path with 0 travel time
      
   Label every node as unvisited.
 
   Label every node with a shortest time value from the start
   node, with the start node being assigned a travel time of 0 and
   every other node assigned a travel time of ​∞​.
 
   # Repeat from here later on
   while there are unvisited nodes:
       Set unvisited node with least travel time as current node.
 
       For the current node: 
consider each of its unvisited neighbors with regards to the restrited_roads,
(if necessary) update the best time and best path from the start node to these neighbors.
 
       Mark the current node as visited.
 
   If there is no path between start and end:
       No path exists between start and end. Return None.
 
   return (best path, best time) from start to end

Note: because this is pseudocode, you will have to choose some concrete implementation details (e.g. data structures used, base cases) for yourself.

When you run ps2_tester.py, below the lines that say whether you failed or passed the tests, we also print more details about what paths we are testing and the expected vs your output for the paths. This may help you with debugging.

Notes:

1. You must use Dijkstra’s algorithm for get_optimal_path or an optimized version of DFS/BFS or your code will time out and fail our hidden tests.

If you would like, you can uncomment the lines at the bottom of ps2.py and change the values of start, end, restricted_roads in order to debug get_optimal_path and see what your get_optimal_path returns.

2. You may assume that there is only 1 road between two nodes.

3. Graphs can contain cycles. A cycle occurs in a graph if the path of nodes leads you back to a node that was already visited in the path. When building up possible paths, if you reach a cycle without knowing it, you could create an infinite loop by including a node more than once in a path. Make sure your code avoids exploring paths containing such cycles. This hint is only relevant if you are implementing an optimized version of DFS/BFS. You do not need to explicitly address cycles with Dijkstra’s algorithm. Can you think of why that is, feel free to come to office hours to discuss why this is with an LA/TA.

You should now pass the test test_3_impossible_path_no_interstate, test_3_impossible_path_no_interstate_no_local, test_3_ps2_map1_path_one_step, test_3_ps2_map2_path_limited_time, test_3_ps2_map3_path_restricted_path, test_3_ps2_map_path_same_length_different_time, test_3_ps2_map_path_start_end_same, test_3_ps2_path_multiple_roads_not_allowed in ps2_tester.py.

Problem 4: Using the best path algorithm

Now that you have a working get_optimal_path algorithm, let’s call it to answer some questions:

4A: Shortest Path With No Traffic

Implement ​​optimal_path_no_traffic​​, which calculates the shortest path from ​start​ to end ​during ​normal ​traffic conditions. Your function should return a list of the nodes of the best route.

4B: Shortest Path With Restricted Roads

The town of Smootsville, drowning in congestion, has decided to impose a ban on non-resident commuters passing through their town (this actually happens). Implement optimal_path_restricted, which calculates the new shortest path from start to end that does not use local roads. Assume that there is no traffic in this case.

4C: Shortest path with high traffic

Despite the efforts made by the city of Smoothsville, there is still rush hour traffic during the beginning and the end of the work day. In this section your task is to find the best time from start to end in high traffic conditions.

1. Modify your implementation of ​get_optimal_path​ to make use of the ​in_traffic parameter while calculating the shortest path. That is, in the case that ​in_traffic=True​, your function should return the shortest path from ​start​ to ​the ​end in high traffic conditions. This may require minor refactoring of the code that you wrote in ​Part 3B​.

   Note: in_traffic​ is a parameter with a default value of ​False​, which means that it is automatically assigned a value of ​False​ if it is not specified during a call to get_optimal_path​; if you are confused about this syntax, read more​ ​here​.

2. Implement ​optimal_path_heavy_traffic, which calculates the new shortest path from ​start​ to ​​end in high traffic conditions.

You should now pass the test test_4a_optimal_path_no_traffic, test_4b_optimal_path_restricted, test_4c_optimal_path_heavy_traffic in ps2_tester.py.

Further Considerations:

Think about the following questions, which you might naturally ask while completing this PSET:

• Do you think it is fair to prohibit non-resident commuters from driving through the local town streets? If so, under what conditions should this be implemented? What about the fairness of charging tolls on one or more of the roads?
• How might you use your graph to test other interventions that might help various parties? Note also that travel times will depend on road congestion, so more modeling and analysis is needed to evaluate the equilibrium conditions that would result if each traveler chose their best path to work based on the congestion created by other travelers.
• If a fraction of commuters used the city streets and the rest took the highway, the total travel time for all commuters might in fact be less than if all commuters took—or avoided—the local streets. Is it okay to give realtime ‘shortcut’ information only to subscribers who pay for premium services such as Waze? Which policies and regulations might lead to a reasonably efficient situation and while still being considered fair by all parties?

MIT Course 11+6 (Urban Science and Planning with Computer Science)

This problem set was made in partnership with Course 11, Urban Studies and Planning.

Do you like these sorts of problems that can involve both significant knowledge of computing and data analysis, and a deeper understanding of social choice, governance, urban planning, and regulation?

Visit MIT Course 11-6: Urban Science and Planning with Computer Science or email urban-science@mit.edu to speak to an advisor.

Hand-In Procedure

1. Save

Make sure to save your solutions.

2. Time and Collaboration Info

At the start of ps2.py, in a comment, write down the number of hours (roughly) you spent on the problems in that part, and the names of the people you collaborated with. For example:

    # Problem Set 2
    # Name: Jane Lee
    # Collaborators: John Doe
    # Time: X hours
    #
    ... your code goes here ...

3. Sanity checks

After you are done with the problem set, do sanity checks​. ​Be sure to run ps2_tester.py and make sure all the tests pass.

Note: Passing all of the tests in test_ps2.py does not necessarily mean you will receive a perfect score. The staff will run additional tests on your code to check for correctness.

4. Submit

Upload graph.py, ps2.py, and test_load_map.txt in their correct submission places! Look at the header above each file upload area. If there is an error uploading, attach your files to a private Piazza post. DO NOT upload any other files other than the three listed.

You may upload new versions of each file until the 9PM deadline, but anything uploaded after that will get a score of 0, unless you have enough late days left.

After you submit, please make sure the files you have submitted show up on the problem set submission page.​ When you upload a new file with the same name, your old one will be overwritten.

Upload graph.py

Select File No file selected

Upload test_load_map.txt

Select File No file selected

Upload ps2.py

Select File No file selected