path: root/ero1/src/drone/postier_chinoisV2.py

import osmnx as ox
import networkx as nx
import parameters as params

from src.helper.debug_printer import debug_print
from src.helper.display_graph import display_graph
from src.helper.duplicate_removal import remove_duplicates
from src.helper.export_import_yaml import save_paths_to_yaml

arrondissements = [
    'Ahuntsic-Cartierville',    
    'Anjou',
    'Côte-des-Neiges–Notre-Dame-de-Grâce',
    'Lachine',
    'LaSalle',
    'Le Plateau-Mont-Royal',
    'Le Sud-Ouest',
    'L\'Île-Bizard–Sainte-Geneviève',
    'Mercier–Hochelaga-Maisonneuve',
    'Montréal-Nord',
    'Outremont',
    'Pierrefonds-Roxboro',
    'Rivière-des-Prairies–Pointe-aux-Trembles',
    'Rosemont–La Petite-Patrie',
    'Saint-Laurent',
    'Saint-Léonard',
    'Verdun',
    'Ville-Marie',
    'Villeray–Saint-Michel–Parc-Extension'
]  # first list, we changed its order manually to make a "smart path" for the drone

connection_order = [
    'Rivière-des-Prairies–Pointe-aux-Trembles',
    'Montréal-Nord',
    'Saint-Léonard',
    'Anjou',
    'Mercier–Hochelaga-Maisonneuve',
    'Rosemont–La Petite-Patrie',
    'Villeray–Saint-Michel–Parc-Extension',
    'Outremont',
    'Le Sud-Ouest',
    'Ville-Marie',
    'L\'Île-Bizard–Sainte-Geneviève',
    'Verdun',
    'LaSalle',
    'Côte-des-Neiges–Notre-Dame-de-Grâce',
    'Le Plateau-Mont-Royal',
    'Saint-Laurent',
    'Ahuntsic-Cartierville',
    'Pierrefonds-Roxboro',
    'Lachine'
]

def find_pairs_odd(G, odd_nodes):
    """
    L'objectif de cette fonction est de trouver des paires de nœuds de degré impair dans un graphe.
    Cela, en les reliant via les plus courst chemins (avec "length" <=> distance réel).
    """
    pairs = []
    used = set()
    distances = {}
    paths = {}
    for u in odd_nodes:
        dists, path = nx.single_source_dijkstra(G, u, weight='length')
        distances[u] = dists
        paths[u] = path

    for u in odd_nodes:
        if u in used:
            continue
        min_dist = float('inf')
        best_v = None
        for v in odd_nodes:
            if v == u or v in used:
                continue
            if distances[u][v] < min_dist:
                min_dist = distances[u][v]
                best_v = v
        if best_v is not None:
            used.add(u)
            used.add(best_v)
            pairs.append((u, best_v, paths[u][best_v]))
    return pairs

def eulerization_maison(G):
    """
    L'objectif de cette fonction est de transformer un graphe non eulérien en un graphe eulérien.
    La fonction rajoute des arretes dans le graphe. Les arretes sont ajouté entre les noeuds de degrée impaires.
    Avec l'utilisation de find_pairs_odd, on trouve le chemin le plus cours (en distance réel) entre 2 sommets.
    """
    G_update = G.copy()
    odd_nodes = [v for (v, d) in G.degree() if d % 2 == 1]
    pairs = find_pairs_odd(G, odd_nodes)
    for u, v, path in pairs:
        for i in range(len(path) - 1):
            edge_data = G.get_edge_data(path[i], path[i+1])
            l = edge_data.get('length')
            G_update.add_edge(path[i], path[i+1], length=l)
    return G_update

def find_circuit(G_undirected, debug_mode):
    # debug_print(f"Avant eulérisation : {len(G_undirected.edges)} arêtes", debug_mode)
    if nx.is_eulerian(G_undirected):
        G_eulerian = G_undirected
    else:
        G_eulerian = eulerization_maison(G_undirected)
    # debug_print(f"Apres eulérisation : {len(G_eulerian.edges)} arêtes", debug_mode)
    return list(nx.eulerian_circuit(G_eulerian)), G_eulerian

def generate_graph(name, debug_mode=False):
    """
    permet de charger un graphe
    d'une localisation a partir du nom de cette derniere.
    """
    G = ox.graph_from_place(name, network_type='drive')
    G = remove_duplicates(G, False)
    G = ox.project_graph(G)
    return G

def total_length_of_circuit(G, circuit):
    return sum(G[u][v][0]['length'] for u, v in circuit) / 1000

def total_length_of_arrondissement(G):
    distance = 0
    for u, v, data in G.edges(data=True):
        distance += data["length"]
    return distance / 1000

def process_graphs(name, debug_mode):
    """
    Création des paths
    """
    paths = {}
    for i in arrondissements:
        sub_name = i + ", Montréal, Québec, Canada"
        debug_print(f"Génération : {sub_name}", debug_mode)
        sub_graph = generate_graph(sub_name, debug_mode)
        G_undirected = sub_graph.to_undirected()

        circuit, _ = find_circuit(G_undirected, debug_mode)
        c = [edge for edge in circuit]
        # print(f"distance kilometre du quartier = {total_length_of_arrondissement(G_undirected):.2f}km")
        # print(f"distance kilometre du drone = {total_length_of_circuit(G_eulerian, circuit):.2f}km")
        # debug_print(f"Nombre de Route du Path : {len(c)}", debug_mode)

        paths[i] = c

        del sub_graph  # to save as much memory as possible
        del circuit
    return paths

def connect_circuits(G, path_dict, arrondissement_order=connection_order):
    """
    La fonction trouve le chemin le plus cours entre 2 arrondissements
    """
    connections = []
    for i in range(len(arrondissement_order) - 1):
        from_name = arrondissement_order[i]
        to_name = arrondissement_order[i + 1]

        from_path = path_dict[from_name]
        to_path = path_dict[to_name]

        start_node = from_path[0][0]
        end_node = from_path[-1][1]

        next_start_node = to_path[0][0]

        try:
            path = nx.shortest_path(G, source=end_node, target=next_start_node, weight='length')
            connections.append((from_name, to_name, path))
        except nx.NetworkXNoPath:
            print(f"Aucun chemin trouvé entre {from_name} et {to_name}")
            connections.append((from_name, to_name, None))
    return connections

def final_path(graph, paths, connection_order=connection_order):
    full_path = []
    
    connections = connect_circuits(graph, paths)

    for i, arr_name in enumerate(connection_order):
        full_path.extend(paths[arr_name])
        
        if i < len(connection_order) - 1:
            next_arr = connection_order[i+1]
            
            for conn in connections:
                if conn[0] == arr_name and conn[1] == next_arr:
                    node_path = conn[2]
                    for j in range(len(node_path) - 1):
                        full_path.append((node_path[j], node_path[j+1]))
                    break
    
    return full_path

def distance_total(G, paths, connections):
    G_undir = G.to_undirected()
    total_distance = 0.0 
    used_edges = set()

    for arrondissement, edges in paths.items():
        for u, v in edges:
            key = (min(u, v), max(u, v)) 
            used_edges.add(key)
            total_distance += G_undir[u][v][0]['length']
    
    for from_arr, to_arr, node_path in connections:
        for i in range(len(node_path) - 1):
            u = node_path[i]
            v = node_path[i+1]
            key = (min(u, v), max(u, v)) 
            used_edges.add(key)
            total_distance += G_undir[u][v][0]['length']
    
    unused_distance = 0.0
    for u, v, data in G_undir.edges(data=True):
        key = (min(u, v), max(u, v)) 
        if key not in used_edges:
            unused_distance += data['length']

    total_distance /= 1000
    unused_distance /= 1000
    return total_distance, unused_distance

def distance_optimal(G):
    """
    Calcule la somme des longueurs de toutes les routes dans les arrondissements
    """
    covered_edges = set()
    for i in arrondissements:
        sub_name = i + ", Montréal, Québec, Canada"
        sub_graph = generate_graph(sub_name)
        for u, v, data in sub_graph.edges(data=True):
            covered_edges.add((min(u, v), max(u, v)))
        del sub_graph
    
    G_undir = G.to_undirected()
    total = 0.0
    for u, v in covered_edges:
        total += G_undir[u][v][0]['length']

    
    return total / 1000 

def postier_chinois_process_v2(G, debug_mode):
    name = "Montréal, Québec, Canada"
    # initially, we ran find circuit on the whole graph
    # => processes all suburbs instead of the whole graph
    paths = process_graphs(name, debug_mode)
    # it was our closest attempt to get an optimal answer but way to long (ran for more than 12h and did not finish)

    finalPath = final_path(G, paths)

    # Save Path with YML
    save_paths_to_yaml(paths, "paths-PostierChinoisV2.yml")

    return paths, finalPath