From 967be9e750221ab2ab783f95df79bb26d290a45e Mon Sep 17 00:00:00 2001 From: Martial Simon Date: Mon, 15 Sep 2025 01:07:58 +0200 Subject: add: added projects --- ero1/src/helper/check_eulerian.py | 77 +++++++++++++++++++ ero1/src/helper/color_suburbs.py | 70 +++++++++++++++++ ero1/src/helper/debug_printer.py | 13 ++++ ero1/src/helper/display_graph.py | 116 ++++++++++++++++++++++++++++ ero1/src/helper/duplicate_removal.py | 16 ++++ ero1/src/helper/export_cost.py | 60 +++++++++++++++ ero1/src/helper/export_import_yaml.py | 20 +++++ ero1/src/helper/export_to_kml.py | 95 +++++++++++++++++++++++ ero1/src/helper/main_parcours.py | 137 ++++++++++++++++++++++++++++++++++ ero1/src/helper/output_debug.py | 36 +++++++++ ero1/src/helper/partitions.py | 129 ++++++++++++++++++++++++++++++++ ero1/src/helper/prune_maps.py | 76 +++++++++++++++++++ 12 files changed, 845 insertions(+) create mode 100644 ero1/src/helper/check_eulerian.py create mode 100644 ero1/src/helper/color_suburbs.py create mode 100644 ero1/src/helper/debug_printer.py create mode 100644 ero1/src/helper/display_graph.py create mode 100644 ero1/src/helper/duplicate_removal.py create mode 100644 ero1/src/helper/export_cost.py create mode 100644 ero1/src/helper/export_import_yaml.py create mode 100644 ero1/src/helper/export_to_kml.py create mode 100644 ero1/src/helper/main_parcours.py create mode 100644 ero1/src/helper/output_debug.py create mode 100644 ero1/src/helper/partitions.py create mode 100644 ero1/src/helper/prune_maps.py (limited to 'ero1/src/helper') diff --git a/ero1/src/helper/check_eulerian.py b/ero1/src/helper/check_eulerian.py new file mode 100644 index 0000000..31a5db4 --- /dev/null +++ b/ero1/src/helper/check_eulerian.py @@ -0,0 +1,77 @@ +import parameters as params +import networkx as nx +import osmnx as ox + +def check_directed_eulerian(G): + """ + Check si le graph ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est + renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none. + None = non eulérien + (None, None) = eulérien mais pas de sommets de degrée impair + (V1, V2) = eulérien et possède 2 sommets de degrée impaires + Parameters: + G: Graph à tester + """ + V = list(G.nodes) + odd_start = None + odd_end = None + for node in V: + # This is the implementation used when you want to play with a directed graph + # Sadly NetworkX cannor eulerize directed graph + # Eulerzing a directed graph is... NP-Hard + if (G.in_degree(node) + 1 == G.out_degree(node)): + # We have one more edge exitting than entering + # This is the potential start of an eulerian path + if (odd_start != None): + # We already found a node that could make a staring point ? + # We have too much odd degree vertices in this graph + return None + odd_start = node + elif (G.in_degree(node) == G.out_degree(node) + 1): + # We have one more edge entering than exitting + # This is the potential end of an eulerian path + if (odd_end != None): + # We already found a node that could make an ending point ? + # We have too much odd degree vertices in this graph + return None + odd_end = node + elif (G.in_degree(node) != G.out_degree(node)): + # Something's wrong, this is not at all an eulerian graph + return None + + # There is no clean XOR in python... + # Sad... + if (bool(odd_start) != bool(odd_end)): + # We only have one vertice with and odd degree + return None + return (odd_start, odd_end) + +def check_non_directed_eulerian(G): + """ + Check si le graph NON ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est + renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none. + None = non eulérien + (None, None) = eulérien mais pas de sommets de degrée impair + (V1, V2) = eulérien et possède 2 sommets de degrée impaires + Parameters: + G: Graph à tester + """ + V = list(G.nodes) + odd_start = None + odd_end = None + + for node in V: + if (G.degree(node) % 2 == 1): + if (odd_start == None): + odd_start = node + elif (odd_end == None): + odd_end = node + else: + return None + + # There is no clean XOR in python... + # Sad... + if (bool(odd_start) != bool(odd_end)): + # We only have one vertice with and odd degree + return None + return (odd_start, odd_end) \ No newline at end of file diff --git a/ero1/src/helper/color_suburbs.py b/ero1/src/helper/color_suburbs.py new file mode 100644 index 0000000..7668999 --- /dev/null +++ b/ero1/src/helper/color_suburbs.py @@ -0,0 +1,70 @@ +import osmnx as ox + +colors = [ + "#e6194b", # rouge vif 1 + "#3cb44b", # vert vif 2 + "#ffe119", # jaune 3 + "#4363d8", # bleu 4 + "#f58231", # orange 5 + "#911eb4", # violet 6 + "#46f0f0", # cyan clair 7 + "#f032e6", # rose 8 + "#bcf60c", # vert citron 9 + "#fabebe", # rose pâle 10 + "#008080", # turquoise foncé 11 + "#e6beff", # lavande 12 + "#9a6324", # brun 13 + "#fffac8", # crème 14 + "#800000", # bordeaux 15 + "#aaffc3", # vert menthe 16 + "#808000", # olive 17 + "#ffd8b1", # pêche 18 + "#000075", # bleu marine 19 +] + + +def display_suburbs_with_colors(G, path, connections=None): + """ + Colorie chaque quartier d'une couleur différente + Parameter: + path (map>: resultat du postier chinois, + G (DiGraph): graph de montreal + Result: + void + """ + + associated_color = {} + connection_color = "#FFFFFF" # noir + + i = 0 + for suburb in path: + for u, v in path[suburb]: + if (v,u) in G.edges(keys=False): + associated_color[(v, u)] = colors[i] + associated_color[(u, v)] = colors[i] + + i += 1 + + if connections: + for _, _, conn_path in connections: + if conn_path is None or len(conn_path) < 2: + continue + for i in range(len(conn_path) - 1): + u, v = conn_path[i], conn_path[i + 1] + if (v, u) in G.edges(keys=False): + associated_color[(v, u)] = connection_color + associated_color[(u, v)] = connection_color + + count = 0 + edge_colors = [] + for u, v in G.edges(keys=False): + if (u,v) in associated_color: + edge_colors.append(associated_color[(u, v)]) + count += 1 + else: + edge_colors.append("grey") + + # print(f"{count} arêtes colorées (quartiers + connexions)") + + fig, ax = ox.plot_graph(G, edge_color=edge_colors, + node_size=0, edge_linewidth=1) diff --git a/ero1/src/helper/debug_printer.py b/ero1/src/helper/debug_printer.py new file mode 100644 index 0000000..b276630 --- /dev/null +++ b/ero1/src/helper/debug_printer.py @@ -0,0 +1,13 @@ +from datetime import datetime + +def debug_print(message, started): + """ + Affiche dans la console un message de débug s'il est activé avec un timestamp. + Parameters: + message : Le message à afficher. + started : Indique si le debug est activé ou non. + """ + if started: + # Récupérer le timestamp actuel en format string + str_time = datetime.now().strftime('%H:%M:%S.%f')[:-3] + print(f"[{str_time}] [DEBUG] {message}") diff --git a/ero1/src/helper/display_graph.py b/ero1/src/helper/display_graph.py new file mode 100644 index 0000000..693d6e1 --- /dev/null +++ b/ero1/src/helper/display_graph.py @@ -0,0 +1,116 @@ +import matplotlib +matplotlib.use('TkAgg') # KEEP - Eviter erreur avc WSL +import osmnx as ox +import matplotlib.patches as mpatches +import matplotlib.pyplot as plt + +# Variables globales pour stocker la graphique et son état +fig = None +ax = None + +def init_display(): + global fig, ax + if fig is None and ax is None: + plt.ion() # Création du graphique par défaut s'il n'existe pas + fig = plt.figure(figsize=(12, 8)) + ax = fig.add_subplot(111) + plt.show(block=False) + +def edge_in_list(edge, edge_list): + if edge_list is None: + return False + for e in edge_list: + if (e[0] == edge[0] and e[1] == edge[1]) or \ + (e[0] == edge[1] and e[1] == edge[0]): + return True + return False + +def display_graph(G, place_name, reversed_legend, highlight_edges=None, current_edges=None, last_call=False, double_sens=False): + """ + Affiche le graphe G avec la quantité de neige sur chaque arête et les habitations. + Parameters: + G : Le graphe à afficher. + place_name : Nom du lieu + reversed_legend : Si True, la légende est à droite + highlight_edges : Liste des arêtes à mettre en surbrillance + current_edges : Liste des arêtes visitées + last_call : Si True, le graphique est affiché indéfiniment + """ + global fig, ax + + # Initialisation du graphique si premier appel + init_display() + + # Suppression du graphique actuel + ax.clear() + + # Récupérer les quantités de neige sur les arêtes + snow_quantities = [] + for u, v, k, data in G.edges(keys=True, data=True): + snow_quantities.append(data.get('snow', 0)) + + # Affecter une couleur à chaque arête en fonction de la quantité de neige et habitation + legend_labels = ['<2.5cm', '<5cm', '<10cm', '+10cm']#, 'Habitations'] + legend_colors = ['red', 'deepskyblue', 'dodgerblue', 'navy']#, 'green'] + if double_sens: + legend_labels= ["double sens", "une direction"] + legend_colors= ['green', 'black'] + snow_colors = [] + if snow_quantities: + for i, (u, v, k) in enumerate(G.edges(keys=True)): + snow = snow_quantities[i] + edge = (u, v, k) + if double_sens: + if any((v, u, k) == edge for edge in G.edges(keys=True)): + snow_colors.append('green') + else: + snow_colors.append('black') + continue + + # Déterminer la couleur de l'arête + elif current_edges and edge in current_edges: + # Si c'est la dernière arête visitée + snow_colors.append("purple") + elif last_call or (highlight_edges and edge_in_list(edge, highlight_edges)): + # Si c'est une arête enneigée + if snow < 2.5: + snow_colors.append('red') + elif snow < 5: + snow_colors.append('deepskyblue') + elif snow < 10: + snow_colors.append('dodgerblue') + else: + snow_colors.append('navy') + else: + # Couleur normale basée sur la neige + snow_colors.append("white") + else: + snow_colors = 'b' + + # Tracer toutes les arêtes sur le graphique + ox.plot_graph(G, edge_color=snow_colors, edge_linewidth=2, ax=ax, show=False, close=False) + + # Configurer le titre et la légende + ax.set_title('Graphe | ' + place_name) + + # Mise à jour de la légende & ajout des couleurs + for i in range(len(legend_colors)): + ax.plot([], [], color=legend_colors[i], linewidth=4, label=legend_labels[i]) + if highlight_edges: + if current_edges: + ax.plot([], [], color="purple", linewidth=4, label='Chemin actuel') + if double_sens: + ax.legend(title='Sens de circulation', loc='lower ' + ("right" if reversed_legend else "left")) + else: + ax.legend(title='Quantité de neige', loc='lower ' + ("right" if reversed_legend else "left")) + + # Sauvegarder l'image pour le debug + plt.savefig('temp/debug_graph.png', dpi=300) + + # Mettre à jour l'affichage + fig.canvas.draw() + fig.canvas.flush_events() + if not last_call: + plt.pause(0.01) # Délai pour pas tout exploser + else: + plt.pause(120) # Temporaire pour dernier affichage car destruction massive si pas de pause longue \ No newline at end of file diff --git a/ero1/src/helper/duplicate_removal.py b/ero1/src/helper/duplicate_removal.py new file mode 100644 index 0000000..4138bb8 --- /dev/null +++ b/ero1/src/helper/duplicate_removal.py @@ -0,0 +1,16 @@ +from src.helper.debug_printer import debug_print + +def remove_duplicates(graph, debug_mode=False): + """ + Supprime les noeuds dupliqués du graphe. + Parameters: + graph : Le graphe à nettoyer. + debug_mode : Indique si le mode debug est activé ou non. + """ + + removed = [(u, v, k) for u, v, k in graph.edges(keys=True) if k > 0] + graph.remove_edges_from(removed) + + debug_print(f"Nombre d'arêtes dupliquées supprimées : {len(removed)}", debug_mode) + + return graph diff --git a/ero1/src/helper/export_cost.py b/ero1/src/helper/export_cost.py new file mode 100644 index 0000000..d3d9ede --- /dev/null +++ b/ero1/src/helper/export_cost.py @@ -0,0 +1,60 @@ +# - Distance Parcourus +# - Nombre de déneigeuses +# - Coût en fonction de la déneigeuse choisie +# - Coût du drone +# - Distance parcourus par déneigeuse +# - Temps "réel" passé +# - Temps d'exécution (Indicatif uniquement) + +from src.helper.debug_printer import debug_print +import math +import parameters as params + +def export_cost(parcours_drone, parcours_deneigeuses, graph, debug_mode, temps_execution_deneigeuse, temps_execution_drone): + """ + Exporte le coût du parcours. + Parameters: + parcours_drone : Les routes à exporter. + parcours_deneigeuses : Les routes à exporter. + graph : Le graphe à exporter. + debug_mode : Indique si le mode debug est activé ou non. + temps_execution_deneigeuse : Le temps d'exécution des déneigeuses. + temps_execution_drone : Le temps d'exécution du drone. + """ + + debug_print(f"======== EXPORT COST ==========", debug_mode) + debug_print(f"Exportation du coût du parcours.", debug_mode) + + + def get_edge_length(u, v): + try: + return graph[u][v][0]['length'] + except KeyError: + try: + return graph[v][u][0]['length'] + except KeyError: + return 0 + + distance_parcourue_deneigeuses = math.ceil(sum(sum(get_edge_length(u, v) for u, v in parcours) for parcours in parcours_deneigeuses)) + distance_parcourue_drone = math.ceil(sum(get_edge_length(u, v) for u, v in parcours_drone)) + nombre_de_de_neigeuses = len(parcours_deneigeuses) + + debug_print(f"Distance parcourue - Drone : {distance_parcourue_drone}m", debug_mode) + debug_print(f"Distance parcourue - Déneigeuses : {distance_parcourue_deneigeuses}m", debug_mode) + debug_print(f"Nombre de déneigeuses : {nombre_de_de_neigeuses}", debug_mode) + debug_print(f"Temps d'exécution - Drone : {temps_execution_drone} secondes", debug_mode) + + i = 1 + for parcours in parcours_deneigeuses: + distance_parcourue_deneigeuse = math.ceil(sum(get_edge_length(u, v) for u, v in parcours)) + debug_print(f" Distance parcourue - Déneigeuse {i} : {distance_parcourue_deneigeuse}m", debug_mode) + i += 1 + + debug_print(f"======== EXPORT COST ==========", debug_mode) + + # Exportation du coût du parcours dans un fichier texte + with open("temp/export_cost.txt", "w") as f: + f.write(f"{params.ALGORITHM_NAME}|{distance_parcourue_drone}|{distance_parcourue_deneigeuses}|{nombre_de_de_neigeuses}|{temps_execution_deneigeuse}|{temps_execution_drone}\n") + for parcours in parcours_deneigeuses: + distance_parcourue_deneigeuse = math.ceil(sum(get_edge_length(u, v) for u, v in parcours)) + f.write(f"{distance_parcourue_deneigeuse}\n") diff --git a/ero1/src/helper/export_import_yaml.py b/ero1/src/helper/export_import_yaml.py new file mode 100644 index 0000000..1cafb8d --- /dev/null +++ b/ero1/src/helper/export_import_yaml.py @@ -0,0 +1,20 @@ +import yaml + +def save_paths_to_yaml(paths, filename="paths.yml"): + # to facilitate testing for snowplow (do not have to redo the drone part each time) + serializable_paths = { + k: [[u, v] for (u, v) in v] for k, v in paths.items() + } + with open(f"paths/{filename}", 'w') as f: + yaml.dump(serializable_paths, f) + +def load_paths_from_yaml(graph, filename="paths.yml"): + with open(filename, 'r') as f: + raw_paths = yaml.safe_load(f) + + # Reconstruit le format avec des tuples (u, v) + paths = { + k: [tuple(edge) for edge in v] for k, v in raw_paths.items() + } + + return paths diff --git a/ero1/src/helper/export_to_kml.py b/ero1/src/helper/export_to_kml.py new file mode 100644 index 0000000..37f123b --- /dev/null +++ b/ero1/src/helper/export_to_kml.py @@ -0,0 +1,95 @@ +from src.helper.debug_printer import debug_print +import simplekml +import random +import math + +def export_to_kml(parcours_deneigeuses, parcours_drone, graph, debug_mode, name="parcours_deneigeuses"): + """ + Exporte les parcours des déneigeuses dans un fichier KML. + Parameters: + parcours_deneigeuses : Les parcours des déneigeuses. + parcours_drone : Le parcours du drone. + graph : Le graphe à exporter. + debug_mode : Indique si le mode debug est activé ou non. + """ + + debug_print(f"Exportation des parcours des déneigeuses dans un fichier KML.", debug_mode) + + # Création d'un nouveau fichier KML + kml = simplekml.Kml() + + # Récupération d'une couleur aléatoire pour chaque déneigeuse + colors = [] + parcours_deneigeuses.insert(0, parcours_drone) + + for _ in range(len(parcours_deneigeuses)): + r = random.randint(0, 255) + g = random.randint(0, 255) + b = random.randint(0, 255) + colors.append(simplekml.Color.rgb(r, g, b)) + + # Traitement du parcours de chaque déneigeuse + for i, path in enumerate(parcours_deneigeuses): + # Création d'un itinéraire pour chaque déneigeuse + nom = f"Déneigeuse {i}" if i != 0 else "Drone" + folder = kml.newfolder(name=nom) + + coordonnées = [] + profondeurs_neige = [] + distance_parcourue = 0 + + # Ajout des coordonnées pour chaque arête du parcours + for u, v in path: + try: + c_u = (graph.nodes[u]['x'], graph.nodes[u]['y']) + c_v = (graph.nodes[v]['x'], graph.nodes[v]['y']) + + coordonnées.append(c_u) + coordonnées.append(c_v) + + # Récupération de la profondeur de neige et de la distance + try: + profondeur_neige = graph[u][v][0].get('snow', 0) + distance_parcourue += graph[u][v][0]["length"] + except KeyError: + try: + profondeur_neige = graph[v][u][0].get('snow', 0) + distance_parcourue += graph[v][u][0]["length"] + except KeyError: + profondeur_neige = 0 + + profondeurs_neige.append(profondeur_neige) + except KeyError: + continue + + moyenne_neige = sum(profondeurs_neige) / len(profondeurs_neige) if profondeurs_neige else 0 + + # Création du point de départ/arrivée + start_point = folder.newpoint(name=f"Départ {nom}") + start_point.coords = [coordonnées[0]] + start_point.style.iconstyle.icon.href = 'http://maps.google.com/mapfiles/kml/shapes/placemark_circle.png' + start_point.style.iconstyle.scale = 0.5 + start_point.style.iconstyle.color = simplekml.Color.red + + + start_point = folder.newpoint(name=f"Fin {nom}") + start_point.coords = [coordonnées[-1]] + start_point.style.iconstyle.icon.href = 'http://maps.google.com/mapfiles/kml/shapes/placemark_circle.png' + start_point.style.iconstyle.scale = 0.5 + start_point.style.iconstyle.color = simplekml.Color.red + + # Création de l'itinéraire + route = folder.newlinestring(name=f"Itinéraire {nom}") + route.coords = coordonnées + route.altitudemode = simplekml.AltitudeMode.clamptoground # Afficher correctement la route + + route.style.linestyle.color = colors[i] + route.style.linestyle.width = 5 + + route.description = f"Itinéraire {nom}\nDistance parcourue: {math.ceil(distance_parcourue/1000)} km" + + # Sauvegarde du fichier KML + kml.save(f"temp/{name}.kml") + debug_print(f"Fichier KML créé avec succès: temp/{name}.kml", debug_mode) + + return True \ No newline at end of file diff --git a/ero1/src/helper/main_parcours.py b/ero1/src/helper/main_parcours.py new file mode 100644 index 0000000..02b92de --- /dev/null +++ b/ero1/src/helper/main_parcours.py @@ -0,0 +1,137 @@ +import time +from src.helper.debug_printer import debug_print +from src.helper.export_cost import export_cost +from src.helper.export_to_kml import export_to_kml +from src.deneigeuses.hierholzer import process_hierholzer +from src.deneigeuses.directed_cpp import oriented_cpt +from src.helper.display_graph import display_graph +from src.helper.output_debug import output_debug +from src.generation.graph_generation import generate_graph +from src.helper.color_suburbs import display_suburbs_with_colors +from src.helper.prune_maps import prune_verdun +import networkx as nx + + +# IMPORT FOR YAML +from src.helper.export_import_yaml import load_paths_from_yaml +from src.helper.partitions import partition +from src.generation.suburb_snowplow_generation import generate_quartiers_from_path + +# IMPORT FOR DRONE +from src.drone.postier_chinoisV2 import final_path +# from src.drone.postier_chinoisV2 import postier_chinois_process + +def main_parcours(debug_mode=False, place_name=None, reversed_legend=None): + """ + Fonction principale pour le parcours du graphe. + Parameters: + debug_mode : Indique si le mode debug est activé ou non. + place_name : Le nom de la place à parcourir. + reversed_legend : Si la légende est inversée. + """ + + #output_debug(None, None, None, debug_mode) + + parcours_deneigeuses = [] + # ---------------------- GENERATION DU GRAPHE --------------------------- + + debug_print("Génération du graph de Montréal en cours...", debug_mode) + graph = generate_graph("Montréal, Québec, Canada", debug_mode) + debug_print("Graph généré avec succès.", debug_mode) + + # ---------------------- GENERATION DU GRAPHE --------------------------- + + # ---------------------- PARCOURS - DRONE --------------------------- + + start_time_drone = time.time() + + #debug_print("Parcours du drone dans chaque arrondissement", debug_mode) + # - Load from the saved file directly + parcours_drone = load_paths_from_yaml(graph, filename="paths/paths-PostierChinoisV1.yml") # Nom à rajouter du coup + finalPath = final_path(graph, parcours_drone) + + # - Postier Chinois V{?} + # parcours_drone, finalPath = postier_chinois_process(graph, debug_mode) + + end_time_drone = time.time() + + # ---------------------- PARCOURS - DRONE --------------------------- + + # display_suburbs_with_colors(graph, parcours_drone, connections) + + # ---------------------- RECUPERATION DU PARCOURS DU DRONE --------------------------- + temp = [] + # if place_name in parcours_drone: + # debug_print("Parcours du drone dans l'arrondissement de " + place_name, debug_mode) + # for elt in ["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"] : + # if elt in parcours_drone: + # print(elt, len(parcours_drone[elt])) + # temp.extend(parcours_drone[elt]) + # else: + # print("Arrondissement non trouvé:", elt) + # print("Total", len(temp)) + # parcours_drone = temp + # else: + # debug_print("Parcours du drone dans l'arrondissement de " + place_name + " non trouvé", debug_mode) + + # ---------------------- RECUPERATION DU PARCOURS DU DRONE --------------------------- + + #debug_print("Etablissement de connections entre arrondissement :", debug_mode) + #connections = connect_circuits(graph, parcours_drone) + + #output_debug(graph, parcours_drone, connections, debug_mode) + + # ---------------------- PARCOURS - DENEIGEUSE --------------------------- + + # G_partition = generate_quartiers_from_path(parcours_drone, graph, suburb_list=["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"], debug_mode=True) + # partitions = partition(G_partition, 5, debug_mode=True) + + # display_graph(graph, "Test 1", reversed_legend, parcours_drone, None, False) + + start_time_deneigeuse = time.time() + + # TEMP FIX + # parcours_deneigeuse = parcours_drone + + ## Postier chinois qui fonctionne que sur un graph fortement connexe + + verdun = generate_graph("Verdun, Montreal, Canada", debug_mode=debug_mode) + # verdun = prune_verdun(verdun) + parcours_deneigeuse = oriented_cpt(verdun, graph, debug_mode) + + # for elt in partitions: + # drone_edges = [(u, v) for u, v in elt.edges()] + # parcours_deneigeuses.append(process_hierholzer(graph, drone_edges, debug_mode)) + # parcours_deneigeuse = process_hierholzer(graph, parcours_drone, debug_mode) + end_time_deneigeuse = time.time() + + # ---------------------- PARCOURS - DENEIGEUSE --------------------------- + + #display_graph(graph, "Test 2", reversed_legend, parcours_deneigeuse, None, False) + + # ---------------------- EXPORT COST --------------------------- + + # parcours_deneigeuses.append(parcours_deneigeuse) + for elt in ["Outremont", "Verdun", "Anjou", "Rivière-des-Prairies–Pointe-aux-Trembles", "Le Plateau-Mont-Royal"] : + if elt in parcours_drone: + print(elt, len(parcours_drone[elt])) + temp.extend(parcours_drone[elt]) + else: + print("Arrondissement non trouvé:", elt) + print("Total", len(temp)) + parcours_drone = temp + + if "verdun" in place_name.lower(): + export_cost(parcours_drone, parcours_deneigeuses, graph, debug_mode, end_time_deneigeuse - start_time_deneigeuse, end_time_drone - start_time_drone) + else: + print("/!\\ Exportation du coût du parcours désactivée : Seul Verdun est supporté") + + # ---------------------- EXPORT COST --------------------------- + + # ---------------------- EXPORT TO KML --------------------------- + + export_to_kml(parcours_deneigeuses, finalPath, graph, debug_mode) + + # ---------------------- EXPORT TO KML --------------------------- + + return True diff --git a/ero1/src/helper/output_debug.py b/ero1/src/helper/output_debug.py new file mode 100644 index 0000000..bcc521f --- /dev/null +++ b/ero1/src/helper/output_debug.py @@ -0,0 +1,36 @@ +import networkx as nx +import osmnx as ox +from src.generation.graph_generation import generate_graph +from src.helper.prune_maps import prune_verdun +from src.helper.display_graph import display_graph +from src.deneigeuses.directed_cpp import oriented_cpt, chinese_postman_greedy +from src.helper.export_to_kml import export_to_kml + +def output_debug(G, paths, connections, debug_mode): + # debug_print("Calcule de la distance total :", debug_mode) + # distance_drone, unused_distance = distance_total(G, paths, connections) + # debug_print(f"Distance total du drone en kilometre = {distance_drone}", debug_mode) + # debug_print(f"Distance Manqué (routes hors arrondissement) du drone en kilometre = {unused_distance}", debug_mode) + + # distance_opti = 4025.2333363147495 # distance_optimal(G) + # debug_print(f"Distance Optimal du drone en kilometre = {distance_opti}", debug_mode) + + # G_undirected = G.to_undirected() + # distance_ref = 0 + # for u, v, data in G_undirected.edges(data=True): + # distance_ref += data["length"] + # distance_ref /= 1000 + # debug_print(f"Distance total de Montréal en kilomètres = {distance_ref}", debug_mode) + tmp = generate_graph("Verdun, Montréal, Québec, Canada", debug_mode) + print("Graph généré") + tmp = prune_verdun(tmp, debug_mode) + print("Verdun pruné, nb_nodes : ", len(tmp.nodes), ", nb_edges : ", len(tmp.edges())) + print("cpt") + path = chinese_postman_greedy(tmp, debug=True) + print("cpt fini") + display_graph(tmp, "Verdun, Québec, Canada", False, last_call=True, double_sens=True) + export_to_kml(path, [], tmp, debug_mode) + #for edg in tmp.edges: + #print(edg, " ", tmp.get_edge_data(edg[0], edg[1])) + + return True \ No newline at end of file diff --git a/ero1/src/helper/partitions.py b/ero1/src/helper/partitions.py new file mode 100644 index 0000000..94e0739 --- /dev/null +++ b/ero1/src/helper/partitions.py @@ -0,0 +1,129 @@ +import networkx as nx +import osmnx as ox +from src.helper.debug_printer import debug_print +from sklearn.cluster import KMeans, BisectingKMeans + +# j'adore la duplication de code + +# TODO : à commenter et debug, pour l'instant go dodo + + +def display_partitions(G, partitions): + """ + Affiche sur les graphe 'G' (souvent Montreal), chaque partitions d'une couleur unique + Parameters: + G (nx.DiGraph ou MultiDiGraph) : le graphe qui contient les partitions + partitions (list[nx.DiGraph]) : des sous graphes incluent dans 'G' + Return: + void + """ + if len(partitions) > 50: + raise ValueError( + "src/helper/partitions; display_partition: ne peux pas afficher plus de 50 couleurs différentes, la partition est probablement valide mais inaffichable") + + colors = [ + "#e6194b", "#3cb44b", "#ffe119", "#0082c8", "#f58231", "#911eb4", "#46f0f0", "#f032e6", + "#d2f53c", "#fabebe", "#008080", "#e6beff", "#aa6e28", "#fffac8", "#800000", "#aaffc3", + "#808000", "#ffd8b1", "#000080", "#808080", "#FFFFFF", "#000000", "#e41a1c", "#377eb8", + "#4daf4a", "#984ea3", "#ff7f00", "#ffff33", "#a65628", "#f781bf", "#999999", "#66c2a5", + "#fc8d62", "#8da0cb", "#e78ac3", "#a6d854", "#ffd92f", "#e5c494", "#b3b3b3", "#1b9e77", + "#d95f02", "#7570b3", "#e7298a", "#66a61e", "#e6ab02", "#a6761d", "#666666", "#7fc97f", + "#beaed4", "#fdc086" + ] + + associated_color = {} + + i = 0 + for subg in partitions: + for u, v in subg.edges: + if (v, u) in G.edges(keys=False): + associated_color[(v, u)] = colors[i] + associated_color[(u, v)] = colors[i] + + i += 1 + + count = 0 + edge_colors = [] + for u, v in G.edges(keys=False): + if (u, v) in associated_color: + edge_colors.append(associated_color[(u, v)]) + count += 1 + else: + edge_colors.append("grey") + + print(f"{count} arêtes colorées (quartiers + connexions)") + + fig, ax = ox.plot_graph(G, edge_color=edge_colors, + node_size=0, edge_linewidth=1) + + +def partition(G, K, method="KMeans", debug_mode=True): + """ + Partitionne le graphe 'G', en 'K' partitions, selon la méthode 'method', par zone géographique, + G pour le cas des déneigeuses est l'union des graphes de chaque quartiers + Parameters: + G (nx.DiGraph ou MultiDiGraph) : le graphe qui contient les partitions + K (int) : le nombre de partitions voulues + method (string: default = "KMeans") : choix de méthode de partitions, soit "KMeans" soit "BisectingKMeans" + debug_mode (bool: default = True) : activation du mode debug ou pas + Return: + list(nx.DiGraph) : des sous graphes incluent dans 'G', + """ + + # WARNING : G à très certainement été créé à partir de generate_quartier, qui crée un graphe à partir de l'output du drone qui NE contient PAS la data initiale du graphe (length, gps et autre) + + debug_print("debut de l'étape de partitionnement", debug_mode) + + centroids = [] + edges = [] + for u, v, data in G.edges(data=True): + x1, y1 = G.nodes[u]["x"], G.nodes[u]["y"] + x2, y2 = G.nodes[v]["x"], G.nodes[v]["y"] + cx, cy = (x1 + x2)/2, (y1 + y2)/2 + centroids.append([cx, cy]) + edges.append((u, v, data)) + + part = None + if (method == "KMeans"): + part = KMeans(n_clusters=K, random_state=0).fit(centroids) + elif (method == "BisectingKMeans"): + part = BisectingKMeans(n_clusters=K, random_state=0).fit(centroids) + else: + raise ValueError( + "src/helper/partitions; partition: method invalide, choisir entre 'KMeans' et 'BisectingKMeans'") + + labels = part.labels_ + + partitioned_subgraphs = [nx.DiGraph() for _ in range(K)] + for (u, v, data), label in zip(edges, labels): + partitioned_subgraphs[label].add_edge(u, v, **data) + partitioned_subgraphs[label].add_node(u, **G.nodes[u]) + partitioned_subgraphs[label].add_node(v, **G.nodes[v]) + + debug_print("fin de l'étape de partitionnement", debug_mode) + + if (debug_mode): + tot_edges = 0 + tot_weight = 0 + lst_edges = [] + lst_weight = [] + + for partitioned in partitioned_subgraphs: + tot_edges += len(partitioned.edges) + lst_edges.append(len(partitioned.edges)) + tmp_w = 0 + for u, v, data in partitioned.edges(data=True): + tot_weight += data["length"] + tmp_w += data["length"] + lst_weight.append(tmp_w) + + debug_print("List du nb d'edges", debug_mode) + print(lst_edges) + debug_print("List des poids", debug_mode) + print(lst_weight) + debug_print("Nombre total d'edges", debug_mode) + print(tot_edges) + debug_print("Poids total", debug_mode) + print(tot_weight) + + return partitioned_subgraphs diff --git a/ero1/src/helper/prune_maps.py b/ero1/src/helper/prune_maps.py new file mode 100644 index 0000000..6559a77 --- /dev/null +++ b/ero1/src/helper/prune_maps.py @@ -0,0 +1,76 @@ +import networkx as nx +import osmnx as ox +from src.helper.debug_printer import debug_print +from src.helper.display_graph import display_graph + +def prune_verdun(G, debug_mode=False): + """ + Nettoie le graph en retirant les arrêtes problématiques + afin que le graph soit orienté et fortement connexe. + Les Retraits sont pour la plupart minimes et concernent + des routes à sens unique qui vont vers d'autre quartiers. + (Impossibles à parcourir dans le cadre d'un quartier à moins de sortir) + Retourne le graph nettoyé. + Parameters: + G: Graph du quartier de Verdun + debug_mode: [OPTIONEL | DEFAUT = False] + """ + debug_print("Nettoyage du graph Verdun", debug_mode) + + G.remove_edge(32764413, 248511841) + G.remove_edge(615028247, 615028248) + G.remove_edge(615028248, 4503982628) + G.remove_edge(615035051, 615028249) + G.remove_edge(4503982628, 615035051) + G.remove_edge(5342978418, 615028328) + + G.remove_node(8640521401) + G.remove_node(32764413) + G.remove_node(248511841) + G.remove_node(615028247) + G.remove_node(615028248) + G.remove_node(4503982628) + G.remove_node(615035051) + G.remove_node(615028328) + + debug_print("Verdun nettoyé! Supprimé 8 arcs et 8 noeuds", debug_mode) + + return G + +def prune_outremont(G, debug_mode=False): + """ + Nettoie le graph en retirant les arrêtes problématiques + afin que le graph soit orienté et fortement connexe. + Les Retraits sont pour la plupart minimes et concernent + des routes à sens unique qui vont vers d'autre quartiers. + (Impossibles à parcourir dans le cadre d'un quartier à moins de sortir) + Retourne le graph nettoyé. + Parameters: + G: Graph du quartier d'Outremont + debug_mode: [OPTIONEL | DEFAUT = False] + """ + debug_print("Nettoyage du graph Outremont...", debug_mode) + + # Avenue Willowdale + G.remove_node(209387127) + G.remove_node(3165394666) + G.remove_node(209387136) + G.remove_node(209387140) + G.remove_node(209387103) + G.remove_node(209387147) + + # Avenue Gare de Triage + G.remove_node(5412399376) + + # Avenue Durocher/Atlantic + G.remove_node(437865622) + G.remove_node(12844070435) + G.remove_node(5412399379) + + # Sortie autoroute Avenue Davaar et Rockland + G.remove_node(213955306) + G.remove_node(213955379) + + return G + +# TESTINGGGGGG -- cgit v1.2.3