Note: Click on "Kernel" > "Restart Kernel and Run All" in JupyterLab after finishing the exercises to ensure that your solution runs top to bottom without any errors. If you cannot run this file on your machine, you may want to open it in the cloud .

Chapter 11: Classes & Instances (Coding Exercises)¶

The exercises below assume that you have read the first part of Chapter 11.

The ...'s in the code cells indicate where you need to fill in code snippets. The number of ...'s within a code cell give you a rough idea of how many lines of code are needed to solve the task. You should not need to create any additional code cells for your final solution. However, you may want to use temporary code cells to try out some ideas.

Berlin Tourist Guide: A Traveling Salesman Problem¶

This notebook is a hands-on and tutorial-like application to show how to load data from web services like Google Maps and use them to solve a logistics problem, namely a Traveling Salesman Problem .

Imagine that a tourist lands at Berlin's Tegel Airport in the morning and has his "connecting" flight from Schönefeld Airport in the evening. By the time, the flights were scheduled, the airline thought that there would be only one airport in Berlin.

Having never been in Berlin before, the tourist wants to come up with a plan of sights that he can visit with a rental car on his way from Tegel to Schönefeld.

With a bit of research, he creates a list of sights like below.

With just the street addresses, however, he cannot calculate a route. He needs latitude-longitude coordinates instead. While he could just open a site like Google Maps in a web browser, he wonders if he can download the data with a bit of Python code using a web API offered by Google.

So, in this notebook, we solve the entire problem with code.

Geocoding¶

In order to obtain coordinates for the given street addresses above, a process called geocoding, we use the Google Maps Geocoding API.

Q1: Familiarize yourself with this documentation, register a developer account, create a project, and create an API key that is necessary for everything to work! Then, enable the Geocoding API and link a billing account!

Info: The first 200 Dollars per month are not charged (cf., pricing page), so no costs will incur for this tutorial. You must sign up because Google simply wants to know the people using its services.

Q2: Assign the API key as a str object to the key variable!

To use external web services, our application needs to make HTTP requests just like web browsers do when surfing the web.

We do not have to implement this on our own. Instead, we use the official Python Client for the Google Maps Services provided by Google in one of its corporate GitHub repositories .

Q3: Familiarize yourself with the googlemaps package! Then, install it with the pip command line tool!

Q4: Finish the following code cells and instantiate a Client object named api! Use the key from above. api provides us with a lot of methods to talk to the API.

Q5: Execute the next code cell to list the methods and attributes on the api object!

To obtain all kinds of information associated with a street address, we call the geocode() method with the address as the sole argument.

For example, let's search for Brandenburg Gate. Its street address is "Brandenburger Tor, Pariser Platz, Berlin".

Q6: Execute the next code cell!

Hint: If you get an error message, follow the instructions in it to debug it.

If everything works, we receive a list with a single dict in it. That means the Google Maps Geocoding API only knows about one place at the address. Unfortunately, the dict is pretty dense and hard to read.

Q7: Capture the first and only search result in the brandenburg_gate variable and "pretty print" it with the help of the pprint() function in the pprint module in the standard library !

The dict has several keys that are of use for us: "formatted_address" is a cleanly formatted version of the address. "geometry" is a nested dict with several lat-lng coordinates representing the place where "location" is the one we need for our calculations. Lastly, "place_id" is a unique identifier that allows us to obtain further information about the address from other Google APIs.

The Place Class¶

To keep our code readable and maintainable, we create a Place class to manage the API results in a clean way.

The .__init__() method takes a street_address (e.g., an element of sights) and a client argument (e.g., an object like api) and stores them on self. The place's .name is parsed out of the street_address as well: It is the part before the first comma. Also, the instance attributes .latitude, .longitude, and .place_id are initialized to None.

Q8: Finish the .__init__() method according to the description!

The .sync_from_google() method uses the internally kept client and synchronizes the place's state with the Google Maps Geocoding API. In particular, it updates the .address with the formatted_address and stores the values for .latitude, .longitude, and .place_id. It enables method chaining.

Q9: Implement the .sync_from_google() method according to the description!

Q10: Add a read-only .location property on the Place class that returns the .latitude and .longitude as a tuple!

Q11: Verify that the instantiating a Place object works!

Q12: What do the angle brackets < and > mean in the text representation?

< your answer >

Now, we can obtain the geo-data from the Google Maps Geocoding API in a clean way. As we enabled method chaining for .sync_from_google(), we get back the instance after calling the method.

Q13: Verify that the .sync_from_google() method works!

The Place Class (continued): Batch Synchronization¶

Q14: Add an alternative constructor method named .from_addresses() that takes an addresses, a client, and a sync argument! addresses is a finite iterable of str objects (e.g., like sights). The method returns a list of Places, one for each str in addresses. All Places are initialized with the same client. sync is a flag and defaults to False. If it is set to True, the alternative constructor invokes the .sync_from_google() method on the Places before returning them.

Q15: Verify that the alternative constructor works with and without the sync flag!

Visualization¶

For geo-data it always makes sense to plot them on a map. We use the third-party library folium to achieve that.

Q16: Familiarize yourself with folium and install it with the pip command line tool!

Q17: Execute the code cells below to create an empty map of Berlin!

folium.Map instances are shown as interactive maps in Jupyter notebooks whenever they are the last expression in a code cell.

In order to put something on the map, folium works with so-called Marker objects.

Q18: Review its docstring and then create a marker m with the location data of Brandenburg Gate! Use the brandenburg_gate object from above!

Hint: You may want to use HTML tags for the popup argument to format the text output on the map in a nicer way. So, instead of just passing "Brandenburger Tor" as the popup argument, you could use, for example, "<b>Brandenburger Tor</b><br/>(Pariser Platz, 10117 Berlin, Germany)". Then, the name appears in bold and the street address is put on the next line. You could use an f-string to parametrize the argument.

Q19: Execute the next code cells that add m to the berlin map!

The Place Class (continued): Marker Representation¶

Q20: Finish the .as_marker() method that returns a Marker instance when invoked on a Place instance! The method takes an optional color argument that uses folium 's Icon type to control the color of the marker.

Q21: Execute the next code cells that create a new Place and obtain a Marker for it!

Notes: Without synchronization, we get a RuntimeError. .as_marker() can be chained right after .sync_from_google()

Q22: Use the alternative .from_addresses() constructor to create a list named places with already synced Places!

The Map Class¶

To make folium 's Map class work even better with our Place instances, we write our own Map class wrapping folium 's. Then, we add further functionality to the class throughout this tutorial.

The .__init__() method takes mandatory name, center, start, end, and places arguments. name is there for convenience, center is the map's initial center, start and end are Place instances, and places is a finite iterable of Place instances. Also, .__init__() accepts an optional initial_zoom argument defaulting to 12.

Upon initialization, a folium.Map instance is created and stored as an implementation detail _map. Also, .__init__() puts markers for each place on the _map object: "green" and "red" markers for the start and end locations and "blue" ones for the places to be visited. To do that, .__init__() invokes another .add_marker() method on the Map class, once for every Place object. .add_marker() itself invokes the .add_to() method on the folium.Marker representation of a Place instance and enables method chaining.

To keep the state in a Map instance consistent, all passed in arguments except name are treated as implementation details. Otherwise, a user of the Map class could, for example, change the start attribute, which would not be reflected in the internally kept folium.Map object.

Q23: Implement the .__init__() and .add_marker() methods on the Map class as described!

Q24: Add a .show() method on the Map class that simply returns the internal folium.Map object!

Let's put all the sights, the two airports, and three more places, the Bundeskanzleramt , the Olympic Stadium , and the East Side Gallery , on the map.

Q25: Execute the next code cells to create a map of Berlin with all the places on it!

Note: Because we implemented method chaining everywhere, the code below is only one expression written over several lines. It almost looks like a self-explanatory and compact "language" on its own.

Distance Matrix¶

Before we can find out the best order in which to visit all the sights, we must calculate the pairwise distances between all points. While Google also offers a Directions API and a Distance Matrix API, we choose to calculate the air distances using the third-party library geopy .

Q26: Familiarize yourself with the documentation and install geopy with the pip command line tool!

We use geopy primarily for converting the latitude-longitude coordinates into a distance matrix .

Because the earth is not flat , geopy provides a great_circle() function that calculates the so-called orthodromic distance between two places on a sphere.

Q27: For quick reference, read the docstring of great_circle() and execute the code cells below to calculate the distance between the arrival and the departure!

The Place Class (continued): Distance to another Place¶

Q28: Finish the distance_to() method in the Place class that takes a other argument and returns the distance in meters! Adhere to the given docstring!

Q29: Execute the code cells below to test the new feature!

Note: If done right, object-oriented code reads almost like plain English.

Q30: Execute the next code cell to instantiate the Places in sights again!

The Map Class (continued): Pairwise Distances¶

Now, we add a read-only distances property on our Map class. As we are working with air distances, these are symmetric which reduces the number of distances we must calculate.

To do so, we use the combinations() generator function in the itertools module in the standard library . That produces all possible r-tuples from an iterable argument. r is 2 in our case as we are looking at origin-destination pairs.

Let's first look at an easy example of combinations() to understand how it works: It gives us all the 2-tuples from a list of five numbers disregarding the order of the tuples' elements.

distances uses the internal ._start, ._end, and ._places attributes and creates a dict with the keys consisting of all pairs of Places and the values being their distances in meters. As this operation is rather costly, we cache the distances the first time we calculate them into a hidden instance attribute ._distances, which must be initialized with None in the .__init__() method.

Q31: Finish the .distances property as described!

We pretty print the total distance matrix.

How can we be sure the matrix contains all possible pairs? As we have 9 sights plus the start and the end of the tour, we conclude that there must be 11 * 10 = 110 distances excluding the 0 distances of a Place to itself that are not in the distance matrix.

Route Optimization¶

Let us find the cost minimal order of traveling from the arrival airport to the departure airport while visiting all the sights.

This problem can be expressed as finding the shortest so-called Hamiltonian path from the start to end on the Map (i.e., a path that visits each intermediate node exactly once). With the "hack" of assuming the distance of traveling from the end to the start to be 0 and thereby effectively merging the two airports into a single node, the problem can be viewed as a so-called traveling salesman problem (TSP).

The TSP is a hard problem to solve but also well studied in the literature. Assuming symmetric distances, a TSP with $n$ nodes has $\frac{(n-1)!}{2}$ possible routes. $(n-1)$ because any node can be the start / end and divided by $2$ as the problem is symmetric.

Starting with about $n = 20$, the TSP is almost impossible to solve exactly in a reasonable amount of time. Luckily, we do not have that many sights to visit, and so we use a brute force approach and simply loop over all possible routes to find the shortest.

In the case of our tourist, we "only" need to try out 181_440 possible routes because the two airports are effectively one node and $n$ becomes $10$.

Analyzing the problem a bit further, all we need is a list of permutations of the sights as the two airports are always the first and last location.

The permutations() generator function in the itertools module in the standard library helps us with the task. Let's see an example to understand how it works.

However, if we use permutations() as is, we try out redundant routes. For example, transferred to our case, the tuples (1, 2, 3) and (3, 2, 1) represent the same route as the distances are symmetric and the tourist could be going in either direction. To obtain the unique routes, we use an if-clause in a "hacky" way by only accepting routes where the first node has a smaller value than the last. Thus, we keep, for example, (1, 2, 3) and discard (3, 2, 1).

In order to compare Places as numbers, we would have to implement, among others, the .__eq__() special method. Otherwise, we get a TypeError.

As a quick and dirty solution, we use the .location property on a Place to do the comparison.

As the code cell below shows, combining permutations() with an if-clause results in the correct number of routes to be looped over.

To implement the brute force algorithm, we split the logic into two methods.

First, we create an .evaluate() method that takes a route argument that is a sequence of Places and returns the total distance of the route. Internally, this method uses the .distances property repeatedly, which is why we built in caching above.

Q32: Finish the .evaluate() method as described!

Second, we create a .brute_force() method that needs no arguments. It loops over all possible routes to find the shortest. As the start and end of a route are fixed, we only need to look at permutations of inner nodes. Each permutation can then be traversed in a forward and a backward order. .brute_force() enables method chaining as well.

Q33: Finish the .brute_force() method as described!

The Map Class (continued): Brute Forcing the TSP¶

Q34: Find the best route for our tourist by executing the code cells below!