1 files changed, 253 insertions, 0 deletions
diff --git a/ero1/src/drone/postier_chinoisV3.py b/ero1/src/drone/postier_chinoisV3.py
new file mode 100644
index 0000000..fc74a26
--- /dev/null
+++ b/ero1/src/drone/postier_chinoisV3.py
@@ -0,0 +1,253 @@
+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