# TryAlgo Maps 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.

In [1]:
with open('paris.txt') as f:
N, M, T, C, S = map(int, lines[0].split())
paris_coords = []
for i in range(1, N + 1):
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?

In [2]:
len(paris)

Out[2]:
11348
In [3]:
paris[0]

Out[3]:
{4942: 277, 1079: 113, 2912: 178}

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

In [4]:
%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)

Out[4]:
<matplotlib.collections.PathCollection at 0x7fd2ee8a6f10>

## Geolocation using geopy¶

In [5]:
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

Out[5]:
(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:

In [6]:
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¶

In [7]:
import folium
paris_viz = folium.Map(location=(48.8330293, 2.3618845), tiles='Stamen Watercolor', zoom_start=13)
paris_viz

Out[7]:

## Pathfinding using tryalgo¶

In [8]:
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.

In [9]:
from folium.features import PolyLine

# We can also save it to a file