<jupyter_start><jupyter_text>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.<jupyter_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<jupyter_output><empty_output><jupyter_text>How many nodes?<jupyter_code>len(paris)
paris[0]<jupyter_output><empty_output><jupyter_text>Which means the node 0 leads to the node 1079 with cost 113 and so on.<jupyter_code>%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)<jupyter_output><empty_output><jupyter_text>Geolocation using geopy<jupyter_code>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<jupyter_output><empty_output><jupyter_text>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:<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Visualization using Folium<jupyter_code>import folium
paris_viz = folium.Map(location=(48.8330293, 2.3618845), tiles='Stamen Watercolor', zoom_start=13)
paris_viz<jupyter_output><empty_output><jupyter_text>Pathfinding using tryalgo<jupyter_code>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])<jupyter_output>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]<jupyter_text>To finish, let's display the path.<jupyter_code>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)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12086258776328987, 'fraction_numerical': 0.07998996990972919, 'mean_word_length': 4.586834733893557, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '234193', 'license': 'MIT', 'n_tokens_mistral': 1706, 'n_tokens_neox': 1466, 'n_words': 420, 'path': 'examples/TryAlgo Maps in Paris.ipynb', 'repo_name': 'fuez/tryalgo', 'size': '3988'}