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

import osmnx as ox
import networkx as nx
import parameters as params
import yaml
import itertools
 
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
from itertools import combinations

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 eulerization(G):
    """
    Eulérise le graphe G (non orienté) en dupliquant des arêtes existantes.
    Retourne un MultiGraph eulérien.
    """

    if not nx.is_connected(G):
        return None

    odd_nodes = [v for v in G.nodes if G.degree(v) % 2 == 1]

    all_pairs = {}
    for u in odd_nodes:
        dist, path = nx.single_source_dijkstra(G, u, weight="length")
        all_pairs[u] = (dist, path)

    H = nx.Graph()
    for u, v in itertools.combinations(odd_nodes, 2):
        if v in all_pairs[u][0]: 
            length = all_pairs[u][0][v]
            H.add_edge(u, v, length=length)
        else:
            return None
    
    pairs = sorted(H.edges(data=True), key=lambda e: e[2]['length'])
    matched = set()
    min_matching = []
    for u, v, d in pairs:
        if u not in matched and v not in matched:
            matched.update([u, v])
            min_matching.append((u, v))

    MG = nx.MultiGraph(G)
    for u, v in min_matching:
        path = all_pairs[u][1][v]
        for i in range(len(path) - 1):
             MG.add_edge(path[i], path[i+1])

    return MG

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(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, G_eulerian = 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")

        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_v3(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-PostierChinoisV3.yml")

    return paths, finalPath