Demo: shortest paths in Paris

Here is a demo of the tryalgo package over Paris’ graph.
We are going to display a shortest path from Gare de Lyon to Place d’Italie.

Let’s first store the graph in an adjacency list.

with open('paris.txt') as f:
    lines = f.read().splitlines()
    N, M, T, C, S = map(int, lines[0].split())
    paris_coords = []
    for i in range(1, N + 1):
        paris_coords.append(list(map(float, lines[i].split())))  # Read coords
    paris = {node: {} for node in range(N)}
    for i in range(N + 1, N + M + 1):
        start, end, nb_directions, duration, length = map(int, lines[i].split())
        paris[start][end] = length
        if nb_directions == 2:
            paris[end][start] = length

How many nodes?

len(paris)

paris[0]

{4942: 277, 1079: 113, 2912: 178}

Which means the node 0 leads to the node 1079 with cost 113 and so on.

%matplotlib inline
from matplotlib import pyplot as plt

x = [point[0] for point in paris_coords]
y = [point[1] for point in paris_coords]
plt.scatter(x, y, marker='.', s=1)

<matplotlib.collections.PathCollection at 0x7fd2ee8a6f10>

png

Geolocation using geopy

from geopy.geocoders import Nominatim

geocoder = Nominatim(user_agent='tryalgo')
start = geocoder.geocode("Gare de Lyon, Paris")
end = geocoder.geocode("Porte d'Italie, Paris")
start.longitude, start.latitude

(2.3734794, 48.8448057)

We need a function that provides the index of the closest node in the graph of Paris. The distance between two pairs of latitude and longitude is given by the following haversine function:

from math import radians, cos, sin, asin, sqrt

def haversine(lon1, lat1, lon2, lat2):
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    """
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    # haversine formula 
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) 
    r = 6371 # Radius of earth in kilometers. Use 3956 for miles
    return c * r

def closest_node(coords, location):
    dmin = float('inf')
    closest = None
    for i in range(len(coords)):
        d = haversine(coords[i][1], coords[i][0], location.longitude, location.latitude)
        if d < dmin:
            closest = i
            dmin = d
    return closest

Visualization using Folium

import folium
paris_viz = folium.Map(location=(48.8330293, 2.3618845), tiles='Stamen Watercolor', zoom_start=13)
paris_viz

Pathfinding using tryalgo

from tryalgo.dijkstra import dijkstra

source = closest_node(paris_coords, start)
target = closest_node(paris_coords, end)
dist, prec = dijkstra(paris, paris, source, target)

# Let's build the path
path = [target]
node = target
while prec[node] is not None:
    node = prec[node]
    path.append(node)
print('Path found with', len(path), 'nodes:', path[::-1])

Path found with 61 nodes: [2223, 8790, 4442, 3365, 2029, 4937, 10195, 913, 5207, 1477, 2909, 250, 32, 806, 4494, 3959, 8878, 1732, 5055, 2605, 9019, 3432, 5217, 74, 9125, 6839, 5905, 274, 9382, 10585, 5847, 5287, 10853, 9136, 1, 9572, 9776, 2709, 10826, 1427, 794, 1143, 3830, 6562, 11181, 729, 10703, 3493, 10217, 2069, 9762, 3921, 10139, 10815, 3867, 9627, 4897, 6027, 7527, 4554, 3325]

To finish, let’s display the path.

from folium.features import PolyLine
paris_viz.add_child(PolyLine(map(lambda node: paris_coords[node], path)))
paris_viz

# We can also save it to a file
# paris_viz.save('pathfinding_in_paris.html')
# from IPython.display import IFrame
# IFrame('pathfinding_in_paris.html', width='100%', height=510)

Did you like this demo? If so, please let us know on the GitHub project! https://github.com/jilljenn/tryalgo