Discrete Math with SageMath: Learn math with open-source software

Now, let’s calculate the distances between campus locations. We will first create a dictionary to store the campus name, latitude, and longitude values.

Since the Earth is curved, we cannot use the Euclidean distance. We will use the Haversine formula instead. Note that the Haversine formula still produces an approximation because the Earth is not a perfect sphere. Here is a function to compute the Haversine formula.

Now we can make an edge list. We will represent each campus as a node with the initials of the college name. The weight of the edge will represent the Haversine value between the locations. For example, express the route between Harold Washington College and Harry S Truman College as ("HW", "HT", Haversine).

Swap \((Latitude, Longitude)\) coordinates for plotting with \((x,y)\) coordinates.

Create a Graph from the edge list:

So far, we have encountered various concepts for connecting a graph’s vertices, including the Hamilton path and the MST. Let’s consider what technique is best suited for solving the problem of constructing a railway that optimizes material costs.

The previous chapter used the traveling salesperson algorithm to optimize a delivery route. Since we aim to optimize material costs, you might think of following a similar approach: apply the traveling salesperson algorithm, eliminate the greatest edge from the Hamilton circuit, and design the railway with the minimum Hamilton path. If we take a Hamilton circuit and eliminate one edge, we obtain a spanning tree. While the Hamilton path optimizes graph traversal by visiting each vertex exactly once in a single path, it does not guarantee that all vertices are connected with the minimal total weight.

In a Hamilton path, the requirement to visit each vertex in a single path can force the inclusion of high-weight edges. Alternatively, the MST is not restricted by the requirement of connecting vertices with a path. The MST can avoid high-weight edges by connecting vertices without regard to forming a path as long as the graph remains connected and acyclic. Although the minimum Hamilton path is one of many possible spanning trees, it is not an MST. Prim’s Algorithm ensures the weight of the spanning tree is minimal because, at each iteration, it selects the smallest-weight edge.

Let’s find the MST edge list of the campus locations with the min_spanning_tree(by_weight=True) function.

Visualize the MST with the vertex positions mapped to the geographical coordinates of each campus location.

In this exercise, we only optimized construction material costs. In a real-world scenario, we may want to create a railway that optimizes both travel time and material costs. In the case of the Chicago L train system, the railway resembles a tree when ignoring the downtown Loop. The L receives criticism for its lack of interconnectivity. For example, finding an efficient route connecting the end of the Blue Line with the end of the Red Line is challenging because a traveler may need to commute all the way downtown from one end of the railway to reach another end. As an interesting challenge, you can optimize both travel time and construction costs.