summaryrefslogtreecommitdiff
path: root/ero1/src/drone
diff options
context:
space:
mode:
Diffstat (limited to 'ero1/src/drone')
-rw-r--r--ero1/src/drone/couverture_sommets.py59
-rw-r--r--ero1/src/drone/postier_chinoisV1.py209
-rw-r--r--ero1/src/drone/postier_chinoisV2.py258
-rw-r--r--ero1/src/drone/postier_chinoisV3.py253
-rw-r--r--ero1/src/drone/postier_chinois_Martial.py122
-rw-r--r--ero1/src/drone/postier_chinois_montreal.py89
6 files changed, 990 insertions, 0 deletions
diff --git a/ero1/src/drone/couverture_sommets.py b/ero1/src/drone/couverture_sommets.py
new file mode 100644
index 0000000..80a1fe6
--- /dev/null
+++ b/ero1/src/drone/couverture_sommets.py
@@ -0,0 +1,59 @@
+from src.helper.debug_printer import debug_print
+import parameters as params
+import networkx as nx
+
+def vertex_cover_glouton(graph):
+ """
+ Renvoie un ensemble de sommets couvrant toutes les arêtes du graphe.
+ Approche gloutonne.
+ """
+ G = graph.copy()
+ cover = set()
+
+ while G.number_of_edges() > 0:
+ u = max(G.degree, key=lambda x: x[1])[0] # Max degree
+ cover.add(u)
+ G.remove_node(u)
+
+ return cover
+
+def get_snowed_edges(graph, cover_nodes, snow_min, snow_max):
+ """
+ Retourne les arêtes enneigées couvertes par les sommets sélectionnés.
+ """
+ snowy_edges = []
+ no_snowy_edges = []
+
+ for u, v, key in graph.edges(keys=True): # toutes les arretes du graphe
+ if u in cover_nodes or v in cover_nodes:
+ data = graph.get_edge_data(u, v, key)
+ if 'snow' in data and snow_min <= data['snow'] <= snow_max:
+ snowy_edges.append((u, v, key))
+ else:
+ no_snowy_edges.append((u, v, key))
+
+ return (snowy_edges, no_snowy_edges)
+
+def vertex_cover(graph, debug_mode=False):
+ """
+ Stratégie :
+ Trouver un ensemble minimum de sommets pour couvrir toutes les arêtes.
+ """
+ debug_print(f"Passage du graphe en mode : undirected", debug_mode)
+ graph = nx.to_undirected(graph)
+
+ # debug_print(f"List Sommets total : {graph.nodes}", debug_mode)
+ # debug_print(f"List Routes total : {graph.edges}", debug_mode)
+ debug_print(f"Nombre de sommets total : {len(graph.nodes)}", debug_mode)
+ debug_print(f"Nombre de routes total : {len(graph.edges)}", debug_mode)
+
+ debug_print("Calcul de la couverture par sommet ...", debug_mode)
+ nodes = vertex_cover_glouton(graph)
+ debug_print(f"Nombre de sommets sélectionnés : {len(nodes)}", debug_mode)
+
+ snowy_edges = get_snowed_edges(graph,
+ nodes,
+ params.SNOW_THRESHOLD,
+ params.SNOW_MAX)
+
+ return snowy_edges
diff --git a/ero1/src/drone/postier_chinoisV1.py b/ero1/src/drone/postier_chinoisV1.py
new file mode 100644
index 0000000..6afe1a0
--- /dev/null
+++ b/ero1/src/drone/postier_chinoisV1.py
@@ -0,0 +1,209 @@
+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
diff --git a/ero1/src/drone/postier_chinoisV2.py b/ero1/src/drone/postier_chinoisV2.py
new file mode 100644
index 0000000..01f8643
--- /dev/null
+++ b/ero1/src/drone/postier_chinoisV2.py
@@ -0,0 +1,258 @@
+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_pairs_odd(G, odd_nodes):
+ """
+ L'objectif de cette fonction est de trouver des paires de nœuds de degré impair dans un graphe.
+ Cela, en les reliant via les plus courst chemins (avec "length" <=> distance réel).
+ """
+ pairs = []
+ used = set()
+ distances = {}
+ paths = {}
+ for u in odd_nodes:
+ dists, path = nx.single_source_dijkstra(G, u, weight='length')
+ distances[u] = dists
+ paths[u] = path
+
+ for u in odd_nodes:
+ if u in used:
+ continue
+ min_dist = float('inf')
+ best_v = None
+ for v in odd_nodes:
+ if v == u or v in used:
+ continue
+ if distances[u][v] < min_dist:
+ min_dist = distances[u][v]
+ best_v = v
+ if best_v is not None:
+ used.add(u)
+ used.add(best_v)
+ pairs.append((u, best_v, paths[u][best_v]))
+ return pairs
+
+def eulerization_maison(G):
+ """
+ L'objectif de cette fonction est de transformer un graphe non eulérien en un graphe eulérien.
+ La fonction rajoute des arretes dans le graphe. Les arretes sont ajouté entre les noeuds de degrée impaires.
+ Avec l'utilisation de find_pairs_odd, on trouve le chemin le plus cours (en distance réel) entre 2 sommets.
+ """
+ G_update = G.copy()
+ odd_nodes = [v for (v, d) in G.degree() if d % 2 == 1]
+ pairs = find_pairs_odd(G, odd_nodes)
+ for u, v, path in pairs:
+ for i in range(len(path) - 1):
+ edge_data = G.get_edge_data(path[i], path[i+1])
+ l = edge_data.get('length')
+ G_update.add_edge(path[i], path[i+1], length=l)
+ return G_update
+
+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_maison(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, _ = 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_v2(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-PostierChinoisV2.yml")
+
+ return paths, finalPath
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
diff --git a/ero1/src/drone/postier_chinois_Martial.py b/ero1/src/drone/postier_chinois_Martial.py
new file mode 100644
index 0000000..a0afb14
--- /dev/null
+++ b/ero1/src/drone/postier_chinois_Martial.py
@@ -0,0 +1,122 @@
+import parameters as params
+import itertools
+from src.helper.debug_printer import debug_print
+import networkx as nx
+import pandas as pd
+
+def postier_chinois(G, debug_mode=False):
+ """
+ Parcourt le graphe en résolvant le problème du postier chinois
+ Source: https://brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/#solving-the-chinese-postman-problem
+ Parameters:
+ G: Le graphe des routes
+ debug_mode: Logs de debug
+ Returns:
+ La liste des arêtes (routes) avec entre 2.5 et 15 cm de neige
+ """
+ gu = nx.to_undirected(G)
+ nodes_odd_degree = [v for v, d in gu.degree() if d % 2 == 1]
+ debug_print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)), debug_mode)
+ debug_print('Number of total nodes: {}'.format(len(gu.nodes())), debug_mode)
+
+ odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2))
+ debug_print('Number of odd degree node pairs: {}'.format(len(odd_node_pairs)), debug_mode)
+
+ def get_shortest_paths_distances(graph, pairs, edge_weight_name):
+ """
+ Compute shortest distance between each pair of nodes in a graph. Return a dictionary keyed on node pairs (tuples).
+ """
+ distances = {}
+ for pair in pairs:
+ distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name)
+ return distances
+ odd_node_pairs_shortest_paths = get_shortest_paths_distances(gu, odd_node_pairs, 'length')
+
+ def create_complete_graph(pair_weights, flip_weights=True):
+ """
+ Create a completely connected graph using a list of vertex pairs and the shortest path distances between them
+ Parameters:
+ pair_weights: list[tuple] from the output of get_shortest_paths_distances
+ flip_weights: Boolean. Should we negate the edge attribute in pair_weights?
+ """
+ g = nx.Graph()
+ for k, v in pair_weights.items():
+ wt_i = - v if flip_weights else v
+ # g.add_edge(k[0], k[1], {'distance': v, 'weight': wt_i}) # deprecated after NX 1.11
+ g.add_edge(k[0], k[1], **{'distance': v, 'weight': wt_i})
+ return g
+ g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True)
+ debug_print('Number of nodes in complete graph of odd nodes: {}'.format(len(g_odd_complete.nodes())), debug_mode)
+ debug_print('Number of edges in complete graph of odd nodes: {}'.format(len(g_odd_complete.edges())), debug_mode)
+
+ odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True)
+ odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes]))
+ debug_print('Number of edges in max weight matching: {}'.format(len(odd_matching)), debug_mode)
+
+ def add_augmenting_path_to_graph(graph, min_weight_pairs):
+ """
+ Add the min weight matching edges to the original graph
+ Parameters:
+ graph: NetworkX graph (original graph from trailmap)
+ min_weight_pairs: list[tuples] of node pairs from min weight matching
+ Returns:
+ augmented NetworkX graph
+ """
+
+ # We need to make the augmented graph a MultiGraph so we can add parallel edges
+ graph_aug = nx.MultiGraph(graph.copy())
+ for pair in min_weight_pairs:
+ graph_aug.add_edge(pair[0],
+ pair[1],
+ **{'length': nx.dijkstra_path_length(graph, pair[0], pair[1]), 'name': 'augmented'}
+ # attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]),
+ # 'trail': 'augmented'} # deprecated after 1.11
+ )
+ return graph_aug
+ g_aug = add_augmenting_path_to_graph(gu, odd_matching)
+
+ # Counts
+ debug_print('Number of edges in original graph: {}'.format(len(gu.edges())), debug_mode)
+ debug_print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())), debug_mode)
+
+ def create_eulerian_circuit(graph_augmented, graph_original):
+ """
+ Create the eulerian path using only edges from the original graph.
+ """
+ debug_print("Creating eulerian circuit", debug_mode)
+ euler_circuit = []
+ naive_circuit = list(nx.eulerian_circuit(graph_augmented))
+ dbg = False
+
+ for edge in naive_circuit:
+ edge_data = graph_augmented.get_edge_data(edge[0], edge[1])
+
+ if len(edge_data) == 1 and 'name' in edge_data[0] and edge_data[0]['name'] != 'augmented':
+ # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit.
+ edge_att = graph_original[edge[0]][edge[1]]
+ euler_circuit.append((edge[0], edge[1], edge_att))
+ else:
+ aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='length')
+ aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:]))
+
+ debug_print('Filling in edges for augmented edge: {}'.format(edge), dbg)
+ debug_print('Augmenting path: {}'.format(' => '.join(str(aug_path))), dbg)
+ debug_print('Augmenting path pairs: {}\n'.format(aug_path_pairs), dbg)
+
+ # If `edge` does not exist in original graph, find the shortest path between its nodes and
+ # add the edge attributes for each link in the shortest path.
+ for edge_aug in aug_path_pairs:
+ edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]]
+ euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att))
+
+ return euler_circuit
+ euler_circuit = create_eulerian_circuit(g_aug, gu)
+ debug_print('Length of Eulerian circuit: {}'.format(len(euler_circuit)), debug_mode)
+
+ debug_print("Extraction des la météo des neiges depuis le parcours eulérien...", debug_mode)
+
+ routes_enneigées = []
+ for edge in euler_circuit:
+ if params.SNOW_THRESHOLD <= edge[2][0]['snow'] <= params.SNOW_MAX:
+ routes_enneigées.append(edge)
+ return routes_enneigées \ No newline at end of file
diff --git a/ero1/src/drone/postier_chinois_montreal.py b/ero1/src/drone/postier_chinois_montreal.py
new file mode 100644
index 0000000..04ade41
--- /dev/null
+++ b/ero1/src/drone/postier_chinois_montreal.py
@@ -0,0 +1,89 @@
+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 process_graphs(Graphe_montreal, debug_mode):
+ """
+ Création des paths
+ """
+ paths = {}
+ debug_print(f"Génération : Montréal", debug_mode)
+ G_undirected = Graphe_montreal.to_undirected()
+ circuit, _ = find_circuit(G_undirected, debug_mode)
+ c = [edge for edge in circuit]
+ paths["Montréal"] = c
+ return paths
+
+def postier_chinois_process_montreal(Graphe_montreal, debug_mode):
+ paths = process_graphs(Graphe_montreal, debug_mode)
+
+ # Save Path with YML
+ save_paths_to_yaml(paths, "paths-PostierChinoisMontreal.yml")
+
+ return paths, finalPath
generated by cgit v1.2.3 (git 2.39.1) at 2026-03-14 17:05:47 +0000