<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 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.
Step1:  How many nodes?
Step2:  Which means the node 0 leads to the node 1079 with cost 113 and so on.
Step3:  Geolocation using geopy
Step5:  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
Step6:  Visualization using Folium
Step7:  Pathfinding using tryalgo
Step8:  To finish, let's display the path.
<ASSISTANT_TASK:>
Python Code:
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
Explanation: 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.
End of explanation
len(paris)
paris[0]
Explanation: How many nodes?
End of explanation
%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)
Explanation: Which means the node 0 leads to the node 1079 with cost 113 and so on.
End of explanation
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
Explanation: Geolocation using geopy
End of explanation
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
Explanation: 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:
End of explanation
import folium
paris_viz = folium.Map(location=(48.8330293, 2.3618845), tiles='Stamen Watercolor', zoom_start=13)
paris_viz
Explanation: Visualization using Folium
End of explanation
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])
Explanation: Pathfinding using tryalgo
End of explanation
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)
Explanation: To finish, let's display the path.
End of explanation
<END_TASK>