summaryrefslogtreecommitdiff
path: root/ero1/src/helper
diff options
context:
space:
mode:
Diffstat (limited to 'ero1/src/helper')
-rw-r--r--ero1/src/helper/check_eulerian.py77
-rw-r--r--ero1/src/helper/color_suburbs.py70
-rw-r--r--ero1/src/helper/debug_printer.py13
-rw-r--r--ero1/src/helper/display_graph.py116
-rw-r--r--ero1/src/helper/duplicate_removal.py16
-rw-r--r--ero1/src/helper/export_cost.py60
-rw-r--r--ero1/src/helper/export_import_yaml.py20
-rw-r--r--ero1/src/helper/export_to_kml.py95
-rw-r--r--ero1/src/helper/main_parcours.py137
-rw-r--r--ero1/src/helper/output_debug.py36
-rw-r--r--ero1/src/helper/partitions.py129
-rw-r--r--ero1/src/helper/prune_maps.py76
12 files changed, 845 insertions, 0 deletions
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<String, List<(int, int, data)>>: 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
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-14 17:05:03 +0000