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_circuit(G_undirected, debug_mode): if nx.is_eulerian(G_undirected): G_eulerian = G_undirected else: G_eulerian = nx.eulerize(G_undirected) return 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_v1(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-PostierChinoisV1.yml") return paths, finalPath