add: added projectsHEADmain

7 files changed, 733 insertions, 0 deletions

diff --git a/ero1/src/deneigeuses/basic_euler.py b/ero1/src/deneigeuses/basic_euler.py
new file mode 100644
index 0000000..117fed0
--- /dev/null
+++ b/ero1/src/deneigeuses/basic_euler.py
@@ -0,0 +1,48 @@
+from src.helper.debug_printer import debug_print

+from src.helper.check_eulerian import check_directed_eulerian, check_non_directed_eulerian

+import networkx as nx

+import osmnx as ox

+

+def find_eulerian(G, debug_mode, path=False, start=None, directed=False):

+    """

+    Trouve et renvoit un chemin ou un cycle eulérien du graph G.

+    Il est possible de spécifier le point de départ du cycle/chemin.

+    Renvoie le chemin/cycle crée ou None si la demande n'est pas possible

+    Parameters:

+        G: Graph duquel on souhaite obtenir le chemin/cycle eulérien

+        debug_mode: Indique si le debug est actif

+        path: [OPTIONNEL | DEFAUT = False] True si on souhaite avoir

+            un chemin eulérien. Faux pour avoir un cycle

+        start: [OPTIONNEL | DEFAUT = None] Noeud NetworkX de départ

+            du chemin/cycle. Un check est effectué si on souhaite un chemin

+    """

+    if (G == None):

+        debug_print("[BASIC_EULER] Cannot procede: The graph is null")

+

+    spots = None

+

+    if (directed):

+        spots = check_directed_eulerian(G)

+    else:

+        spots = check_non_directed_eulerian(G)

+

+    if (spots == None):

+        debug_print("[BASIC_EULER] This is not an Eulerian graph: Cannot create path or cycle", debug_mode)

+        return None

+

+    if (path):

+        if (start != spots[0] and start != spots[1]):

+            # We just want to warn the user that the start position is invalid for this graph

+            debug_print("[BASIC_EULER] The starting position inputted is not a suitable start for an eulerian path", debug_mode)

+            start = spots[0]

+        

+        # We return a list and not an iterator

+        return [u for u, _ in nx.eulerian_path(G, source=start)]

+    else:

+        # This condition is a bit overkill but you never know

+        if (spots[0] != None or spots[1] != None):

+            debug_print("[BASIC_EULER] Cannot create cycle on this eulerian graph", debug_mode)

+            return None

+

+        # We return a list and not an iterator

+        return [u for u, _ in nx.eulerian_circuit(G, source=start)]
\ No newline at end of file
diff --git a/ero1/src/deneigeuses/directed_cpp.py b/ero1/src/deneigeuses/directed_cpp.py
new file mode 100644
index 0000000..552c4d9
--- /dev/null
+++ b/ero1/src/deneigeuses/directed_cpp.py
@@ -0,0 +1,294 @@
+from src.helper.debug_printer import debug_print
+import networkx as nx
+from copy import deepcopy
+import heapq
+
+def split_into_strongly_connected(G):
+    """
+    Renvoie la liste des composantes fortement connexes de G
+
+    Params :
+    - G : Le graph à split
+
+    Returns :
+    - composantes (list) : la liste des sous-graphes (composantes) fortement connexes de G
+    """
+    return [G.subgraph(c) for c in nx.strongly_connected_components(G)]
+
+def chinese_postman_greedy(G, debug_mode=False):
+    if not nx.is_strongly_connected(G):
+        raise ValueError("Le graphe doit être fortement connexe")
+    
+    G = nx.DiGraph(G)
+    shortest_lengths = dict(nx.all_pairs_dijkstra_path_length(G, weight='length'))
+    shortest_paths = dict(nx.all_pairs_dijkstra_path(G, weight='length'))
+
+    delta = {v: G.out_degree(v) - G.in_degree(v) for v in G.nodes()}
+    surplus = [v for v in G.nodes() if delta[v] > 0]
+    deficit = [v for v in G.nodes() if delta[v] < 0]
+
+    debug_print(f"Déficitaires: {len(deficit)}, Excédentaires: {len(surplus)}", debug_mode)
+
+    for u in deficit:
+        while delta[u] < 0:
+            heap = []
+            for v in surplus:
+                if delta[v] <= 0:
+                    continue
+                if v in shortest_lengths[u]:
+                    heapq.heappush(heap, (shortest_lengths[u][v], v))
+            if not heap:
+                raise RuntimeError("Aucun noeud excédentaire atteignable depuis", u)
+            _, v = heapq.heappop(heap)
+
+            flow = min(-delta[u], delta[v])
+            delta[u] += flow
+            delta[v] -= flow
+
+            path = shortest_paths[u][v]
+            for i in range(len(path) - 1):
+                a, b = path[i], path[i + 1]
+                if not G.has_edge(a, b):
+                    raise ValueError(f"Chemin invalide : arête manquante ({a} → {b})")
+                G[a][b]['duplicate'] = G[a][b].get('duplicate', 0) + flow
+                debug_print(f"Arête ({a} → {b}) dupliquée {flow} fois", debug_mode)
+
+    MG = nx.MultiDiGraph()
+    for u, v, data in G.edges(data=True):
+        weight = data.get('length', 1)
+        MG.add_edge(u, v, length=weight)
+        for _ in range(data.get('duplicate', 0)):
+            MG.add_edge(u, v, length=weight)
+
+    return list(nx.eulerian_circuit(MG))
+
+def link_components(global_graph, path1, path2):
+    """
+    Fusionne les 2 chemins en les reliant par leur plus court chemin
+
+    Params :
+    - global_graph : Graphe de toute la ville pour avoir les données des arcs
+    - path1 : chemin de départ
+    - path2 : chemin d'arrivée
+
+    Returns :
+    - fused_path : fusion des 2 chemins
+    """
+    
+    fused_path = []
+    if path1[0][0] != None:
+        fused_path = path1
+    start = path1[-1][1]
+    end = path2[0][0]
+    invert = False
+    # print(start, end, nx.has_path(global_graph,start,end))
+    if not nx.has_path(global_graph, start, end):
+        start,end = end, start
+        fused_path = path2
+        invert = True
+    
+    shortest_path = [start,end]
+    if nx.has_path(global_graph, start, end):
+        shortest_path = nx.shortest_path(global_graph, source=start, target=end, weight='length')
+    for i in range(len(shortest_path) - 1):
+        fused_path.append((shortest_path[i], shortest_path[i + 1]))
+    if path2[0][1] != None:
+        if invert:
+            if path1[0][0] != None:
+                fused_path.extend(path1)
+        else:
+            fused_path.extend(path2)
+    return fused_path
+
+def oriented_cpt(local_graph, global_graph, debug_mode=False):
+    """
+    Détermine le parcours de la déneigeuse sur local_graph en résolvant le problème du postier chinois orienté.
+
+    Params :
+    - local_graph : le graph à parcourir
+    - global_graph : le graph global de référence
+    - debug_mode : active/désactive les logs de debug
+
+    Returns :
+    - parcours : le parcours de la déneigeuse
+    """
+
+    components = split_into_strongly_connected(local_graph)
+    parcours = []
+    if len(components[0].edges) > 0:
+        parcours = chinese_postman_greedy(components[0], debug_mode=debug_mode)
+    else:
+        parcours = [(None, list(components[0])[0])]
+    for component in components[1:]:
+        if len(component.edges) > 0:
+            cpp = chinese_postman_greedy(component, debug_mode=debug_mode)
+            parcours = link_components(global_graph, parcours, cpp)
+        else:
+            cpp = [(list(component)[0], None)]
+            parcours = link_components(global_graph, parcours, cpp)
+    return parcours
+
+# def oriented_cpt(G, debug_mode=False):
+#     """
+#     Version orientée du Chinese Postman Problem.
+#     Le graph ne doit pas contenir de cycles de poids négatifs
+#     et le graph doit être fortement connexe pour que l'algo fonctionne
+#     Parameters:
+#     G: Graph à utiliser pour ce problème
+#     """
+#     nb_nodes = len(G.nodes)
+#     class CPP:
+#         def __init__(self, graph):
+#             self.G = nx.DiGraph(graph)
+#             self.delta_tab = { elem: self.G.out_degree(elem) - self.G.in_degree(elem) for elem in self.G.nodes() }
+#             self.neg_degree = []
+#             self.pos_degree = []
+#             self.f = dict()
+#             self.c = dict()
+#             self.path = dict()
+#             # init the c and path dictionnary so it does not have to be in 
+#             self.setup_fields()
+
+#         def addEdge(self,l, u, v):
+#             if ((u, v) not in self.c or self.c[(u,v)] > l):
+#                 self.c[(u,v)] = l
+#                 self.path[(u,v)] = v
+#                 if (not self.G.has_edge(u, v)):
+#                     self.G.add_edge(u,v, length = l)
+#                 else:
+#                     nx.set_edge_attributes(self.G, {(u, v): {"length": l}})
+        
+#         def setup_fields(self):
+#             for i, j in self.G.edges():
+#                 self.c[(i, j)] = self.G.get_edge_data(i,j)["length"]
+#                 self.path[(i, j)] = j
+
+#         def least_cost_paths(self):
+#             for edge in self.G.edges():
+#                 i = edge[0]
+#                 k = edge[1]
+#                 for j in self.G.nodes:
+#                     if ((k, j) in self.c
+#                         and ((i,j) not in self.c
+#                             or self.c[(i, j)] > self.c[(i,k)] + self.c[(k,j)])):
+#                         self.path[(i, j)] = self.path[(i, k)]
+#                         self.c[(i, j)] = self.c[(i,k)] + self.c[(k,j)]
+#                         if i == j and self.c[(i,j)] < 0: return # cycle négatif tu connais
+
+#         def findUnbalanced(self):
+#             for (key, val) in self.delta_tab.items():
+#                 if (val < 0):
+#                     self.neg_degree.append(key)
+#                 elif (val > 0):
+#                     self.pos_degree.append(key)
+
+#         def findFeasible(self):
+#             for i in self.neg_degree:
+#                 for j in self.pos_degree:
+#                     self.f[(i, j)] = -self.delta_tab[i] if -self.delta_tab[i] < self.delta_tab[j] else self.delta_tab[j]
+#                     self.delta_tab[i] += self.f[(i, j)]
+#                     self.delta_tab[j] -= self.f[(i, j)]
+
+#         # Improvements needed
+#         def improvements(self):
+#             residual = CPP(self.G)
+#             for i,j in zip(self.neg_degree, self.pos_degree):
+#                 length = 0
+#                 if ((i,j) in self.c):
+#                     length = self.c[(i, j)]
+#                 residual.addEdge(length, i, j)
+#                 if (i,j) not in self.f:
+#                     self.f[(i,j)] = 0
+#                 elif (self.f[(i,j)] != 0):
+#                     residual.addEdge(-length, j,i)
+#             residual.least_cost_paths()
+            
+#             for node in self.G.nodes:
+#                 if (node,node) in residual.c and residual.c[(node,node)] < 0:
+#                     k = 0
+#                     kunset = True
+#                     u = node
+#                     while True:
+#                         v = residual.path[(u,node)]
+#                         if residual.c[(u,v)] < 0 and (kunset or k > self.f[(v,u)]):
+#                             k = self.f[(v,u)]
+#                             kunset = False
+#                         u = v
+#                         if u == node:
+#                             break
+#                     u = node
+#                     while True:
+#                         v = residual.path[(u,node)]
+#                         if ((u, v) not in residual.c):
+#                             residual.c[(u,v)] = 0
+#                         if ((u, v) not in self.f):
+#                             self.f[(u,v)] = 0
+#                         if ((v, u) not in self.f):
+#                             self.f[(v,u)] = 0
+#                         if residual.c[(u,v)] < 0:
+#                             self.f[(v,u)] -= k
+#                         else:
+#                             self.f[(u,v)] += k
+#                         u = v
+#                         if u == node:
+#                             break
+#                     return True
+#             return False
+
+#         def solve(self):
+#             print(debug_mode)
+#             self.least_cost_paths()
+#             self.findUnbalanced()
+#             self.findFeasible()
+#             while self.improvements():
+#                 pass
+        
+#         def solution(self,start = None, debug_mode=False):
+#             if (start == None):
+#                 start = list(self.G.nodes)[0]
+#             sol = []
+#             arcs = dict()
+
+#             def findPath(fromNode):
+#                 for node in self.G.nodes:
+#                     if ((fromNode,node) in self.f and self.f[(fromNode,node)] > 0):
+#                         return node
+#                 return None
+
+#             v = start
+#             while True:
+#                 u = v
+#                 v = findPath(u)
+#                 if v != None:
+#                     self.f[(u,v)] -= 1
+#                     while u != v:
+#                         if ((u, v) not in self.path):
+#                             debug_print("We found a path with a 0 in it. This is probably a bad thig idk", debug_mode)
+#                             return []
+#                         p = self.path[(u,v)]
+#                         debug_print("Aller du noeud " + str(u) + " au noeud " + str(p), debug_mode)
+#                         sol.append((u,p))
+#                         u = p
+#                 else:
+#                     if ((u, start) not in self.path):
+#                         self.path[(u,start)] = 0
+#                     bridgeNode = self.path[(u,start)]
+#                     if (u, bridgeNode) not in arcs:
+#                         arcs[(u, bridgeNode)] = list(self.G.adj[u].keys()).count(bridgeNode)
+#                     if arcs[(u,bridgeNode)] == 0:
+#                         break
+#                     v = bridgeNode
+#                     for node in self.G.nodes:
+#                         if (u, node) not in arcs:
+#                             arcs[(u, node)] = list(self.G.adj[u].keys()).count(node)
+#                         if node != bridgeNode and arcs[(u,node)] > 0:
+#                             v = node
+#                             break
+#                     arcs[(u,v)] -= 1
+#                     debug_print("Aller du noeud " + str(u) + " au noeud " + str(v), debug_mode)
+#                     sol.append((u,v))
+#             return sol
+    
+#     res = CPP(G)
+#     res.solve()
+#     return res.solution(debug_mode=debug_mode)
diff --git a/ero1/src/deneigeuses/drone_path.py b/ero1/src/deneigeuses/drone_path.py
new file mode 100644
index 0000000..2f563b9
--- /dev/null
+++ b/ero1/src/deneigeuses/drone_path.py
@@ -0,0 +1,23 @@
+import networkx as nx
+
+def drone_path(parcours_drone, G):
+    """
+    Utilise le parcours du drone comme base pour le parcours de la déneigeuse
+    Params:
+        parcours_drone: la liste des arêtes visitées par le drone
+        G: le graphe du quartier original
+    Return:
+        Le parcours de la déneigeuse
+    """
+    parcours_deneigeuse = []
+    for (u,v) in parcours_drone:
+        if G.has_edge(u,v):
+            parcours_deneigeuse.append((u,v))
+        else:
+            pcc = nx.shortest_path(G, u, v, weight='length')
+            for i in range(len(pcc) - 1):
+                parcours_deneigeuse.append((pcc[i], pcc[i+1]))
+            parcours_deneigeuse.append((v,u))
+            for i in range(len(pcc) - 1):
+                parcours_deneigeuse.append((pcc[i], pcc[i+1]))
+    return parcours_deneigeuse
\ No newline at end of file
diff --git a/ero1/src/deneigeuses/hangar_to_deneigeuse.py b/ero1/src/deneigeuses/hangar_to_deneigeuse.py
new file mode 100644
index 0000000..1bd6ae0
--- /dev/null
+++ b/ero1/src/deneigeuses/hangar_to_deneigeuse.py
@@ -0,0 +1,35 @@
+import networkx as nx
+
+def path_hangar_to_deneigeuse(Graphe, start_point):
+    """
+    Fait le lien entre le hangar "theorique" et le départ de la dénéigeuse
+    """
+    hangar = 299783596
+    res = []
+
+    try:
+        _, path_nodes = nx.single_source_dijkstra(Graphe, hangar, start_point, weight='length')
+    except nx.NetworkXNoPath:  
+        return []  
+
+    for i in range(len(path_nodes) - 1):
+        edge = (path_nodes[i], path_nodes[i+1])
+        res.append(edge)
+    return res
+
+def path_deneigeuse_to_hangar(Graphe, start_point):
+    """
+    Fait le lien entre l'emplacement de la deneigeuse et du hangar
+    """
+    hangar = 299783596
+    res = []
+
+    try:
+        _, path_nodes = nx.single_source_dijkstra(Graphe, start_point, hangar, weight='length')
+    except nx.NetworkXNoPath:  
+        return []  
+
+    for i in range(len(path_nodes) - 1):
+        edge = (path_nodes[i], path_nodes[i+1])
+        res.append(edge)
+    return res
diff --git a/ero1/src/deneigeuses/hierholzer_v1.py b/ero1/src/deneigeuses/hierholzer_v1.py
new file mode 100644
index 0000000..e00e103
--- /dev/null
+++ b/ero1/src/deneigeuses/hierholzer_v1.py
@@ -0,0 +1,128 @@
+import networkx as nx
+from src.helper.debug_printer import debug_print
+from src.helper.display_graph import display_graph
+
+def parcours_eulerien(graph, drone_edges, debug_mode=False, start_node=None):
+    """
+    Parcours de la déneigeuse à partir de l'algorithme de Hierholzer.
+    | PREMIERE VERSION - Celle-ci peut rester bloquée dans les impasses ou cycles présents dans le graphe.
+    Parameters:
+        graph : Le graphe orienté de Montréal
+        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
+        debug_mode : Mode debug pour l'affichage des informations
+        start_node : Le noeud de départ [OPTIONNEL]
+    
+    Returns:
+        list : Liste des arêtes formant le chemin de la déneigeuse
+    """
+    if not drone_edges:
+        debug_print("/!\\ Aucun parcours de drone effectué.", debug_mode)
+        return []
+
+    # Point de départ du parcours
+    if start_node is None:
+        start_node = drone_edges[0][0]
+    
+    debug_print(f"Start node: {start_node}", debug_mode)
+    
+    result = []
+    stack = [start_node]
+    current_node = start_node
+    
+    # Récupération des arêtes du drone
+    drone_edges_dict = {}
+    for u, v in drone_edges:
+        if graph.has_edge(u, v) or graph.has_edge(v, u):
+            drone_edges_dict[(u, v)] = True
+            drone_edges_dict[(v, u)] = True
+    
+    # Arêtes du drone non visitées
+    unvisited_drone_edges = set(drone_edges_dict.keys())
+    
+    def get_next_valid_edge(current, actual_edges):
+        '''
+        Trouve la prochaine arête valide depuis le nœud courant.
+        '''
+        for succ in graph.successors(current):
+            if (current, succ) in actual_edges:
+                return (current, succ)
+        return None
+
+    def find_path_to_next_drone_edge(current, actual_edges):
+        '''
+        Trouve un chemin valide vers la prochaine arête du drone non visitée.
+        '''
+        for node in graph.nodes():
+            for succ in graph.successors(node):
+                if (node, succ) in actual_edges:
+                    try:
+                        # Récupération du chemin le plus court entre noeud actuel => noeud suivant (avec poids = longueur)
+                        path = nx.shortest_path(graph, current, node, weight='length')
+                        if path:
+                            return path
+                    except nx.NetworkXNoPath:
+                        continue
+        return None
+
+    last_edges = []
+    while unvisited_drone_edges:
+        # Récupération de la prochaine arête correcte
+        next_edge = get_next_valid_edge(current_node, unvisited_drone_edges)
+        
+        if next_edge:
+            stack.append(current_node)
+            
+            unvisited_drone_edges.discard(next_edge)
+            unvisited_drone_edges.discard((next_edge[1], next_edge[0])) # Autre sens (orienté)
+            
+            result.append(next_edge)
+            last_edges.append(next_edge)
+            
+            current_node = next_edge[1]
+        else:
+            # STUCK HERE => On trouve un chemin vers la prochaine arête
+            next_path = find_path_to_next_drone_edge(current_node, unvisited_drone_edges)
+            
+            if next_path:
+                # Ajout du parcours effectué pour atteindre la prochaine arête
+                for i in range(len(next_path) - 1):
+                    u, v = next_path[i], next_path[i + 1]
+                    result.append((u, v))
+                    last_edges.append((u, v))
+                    if (u, v) in drone_edges_dict:
+                        unvisited_drone_edges.discard((u, v))
+                        unvisited_drone_edges.discard((v, u)) # Autre sens (orienté)
+                current_node = next_path[-1]
+                stack = [current_node]
+
+            elif stack: # Si on est vraiment bien bloqué, on remonte
+                current_node = stack.pop()
+            else:
+                    break
+    
+    debug_print(f"Longueur du chemin : {len(result)}", debug_mode)
+    debug_print(f"Nombre d'arêtes du drone : {len(drone_edges)}", debug_mode)
+    
+    if not result:
+        debug_print("/!\\ Aucun chemin possible avec cet algorithme", debug_mode)
+        return []
+        
+    return result
+
+def process_hierholzer_v1(graph, drone_edges, debug_mode=False):
+    """
+    Traite le graphe avec l'algorithme de Hierholzer en utilisant les arêtes du drone.
+    
+    Parameters:
+        graph : Le graphe orienté de Montréal
+        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
+        debug_mode : Mode debug pour l'affichage d'informations supplémentaires
+    
+    Returns:
+        list : Liste des arêtes formant le chemin de la déneigeuse
+    """
+    debug_print("Application de l'algorithme de Hierholzer avec les arêtes du drone...", debug_mode)
+    
+    path = parcours_eulerien(graph, drone_edges, debug_mode)
+    
+    return path 
\ No newline at end of file
diff --git a/ero1/src/deneigeuses/hierholzer_v2.py b/ero1/src/deneigeuses/hierholzer_v2.py
new file mode 100644
index 0000000..de73c4f
--- /dev/null
+++ b/ero1/src/deneigeuses/hierholzer_v2.py
@@ -0,0 +1,168 @@
+import networkx as nx
+from src.helper.debug_printer import debug_print
+from src.helper.display_graph import display_graph
+
+def parcours_eulerien(graph, drone_edges, debug_mode=False, start_node=None):
+    """
+    Parcours de la déneigeuse à partir de l'algorithme de Hierholzer.
+    | DEUXIEME VERSION - Celle-ci est plus robuste et peut gérer les impasses ou cycles présents dans le graphe.
+    Parameters:
+        graph : Le graphe orienté de Montréal
+        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
+        debug_mode : Mode debug pour l'affichage des informations
+        start_node : Le noeud de départ [OPTIONNEL]
+    
+    Returns:
+        list : Liste des arêtes formant le chemin de la déneigeuse
+    """
+    if not drone_edges:
+        debug_print("/!\\ Aucun parcours de drone effectué.", debug_mode)
+        return []
+
+    # Point de départ du parcours
+    if start_node is None:
+        start_node = drone_edges[0][0]
+    
+    debug_print(f"Start node: {start_node}", debug_mode)
+    
+    result = []
+    stack = [start_node]
+    current_node = start_node
+    
+    # Récupération des arêtes du drone
+    drone_edges_dict = {}
+    for u, v in drone_edges:
+        if graph.has_edge(u, v) or graph.has_edge(v, u):
+            drone_edges_dict[(u, v)] = True
+            drone_edges_dict[(v, u)] = True
+    
+    # Arêtes du drone non visitées
+    unvisited_drone_edges = set(drone_edges_dict.keys())
+    
+    def get_next_valid_edge(current, actual_edges):
+        '''
+        Trouve la prochaine arête valide depuis le nœud courant.
+        '''
+        for succ in graph.successors(current):
+            if (current, succ) in actual_edges:
+                return (current, succ)
+        return None
+
+    def find_path_to_next_drone_edge(current, actual_edges):
+        '''
+        Trouve un chemin valide vers la prochaine arête du drone non visitée.
+        '''
+        for node in graph.nodes():
+            for succ in graph.successors(node):
+                if (node, succ) in actual_edges:
+                    try:
+                        # Récupération du chemin le plus court entre noeud actuel => noeud suivant (avec poids = longueur)
+                        path = nx.shortest_path(graph, current, node, weight='length')
+                        if path:
+                            return path
+                    except nx.NetworkXNoPath:
+                        continue
+        return None
+
+    last_edges = []
+    visited_nodes = set() 
+    retry_count = 0 
+    max_retries = 100 # Cas d'arrêt si on est bloqué trop fortement
+    debug_print("Début du parcours eulerien...", debug_mode)
+    while unvisited_drone_edges and retry_count < max_retries*2:
+        # Récupération de la prochaine arête correcte
+        next_edge = get_next_valid_edge(current_node, unvisited_drone_edges)
+        
+        if next_edge:
+            stack.append(current_node)
+            visited_nodes.add(current_node)
+            retry_count = 0
+            
+            unvisited_drone_edges.discard(next_edge)
+            unvisited_drone_edges.discard((next_edge[1], next_edge[0])) # Autre sens (orienté)
+            
+            result.append(next_edge)
+            last_edges.append(next_edge)
+            
+            current_node = next_edge[1]
+        else:
+            # STUCK HERE => On trouve un chemin vers la prochaine arête
+            next_path = find_path_to_next_drone_edge(current_node, unvisited_drone_edges)
+            
+            if next_path:
+                # Ajout du parcours effectué pour atteindre la prochaine arête
+                for i in range(len(next_path) - 1):
+                    u, v = next_path[i], next_path[i + 1]
+                    result.append((u, v))
+                    last_edges.append((u, v))
+                    visited_nodes.add(u)
+                    if (u, v) in drone_edges_dict:
+                        unvisited_drone_edges.discard((u, v))
+                        unvisited_drone_edges.discard((v, u)) # Autre sens (orienté)
+                current_node = next_path[-1]
+                stack = [current_node]
+                retry_count = 0
+
+            elif stack: # Si on est vraiment bien bloqué, on remonte
+                current_node = stack.pop()
+                retry_count += 1
+            else:
+                # On fait demi-tour si vraiment sens unique
+                if result and retry_count < max_retries and len(last_edges) > 0:
+                    last_edge = last_edges.pop()
+                    current_node = last_edge[0]
+                    result.append((last_edge[1], last_edge[0]))
+                    retry_count += 1
+                elif retry_count >= max_retries:
+                    # On va essayer de trouver le chemin le plus court vers une arête non visitée
+                    closest_edge = None
+                    closest_edge_path = None
+                    min_distance = float('inf') # max
+                    for edge in unvisited_drone_edges:
+                        path = find_path_to_next_drone_edge(current_node, {edge})
+                        if path and len(path) < min_distance:
+                            closest_edge = edge
+                            closest_edge_path = path
+                            min_distance = len(path)
+                    
+                    if closest_edge:
+                        result.extend(closest_edge_path)
+                        current_node = closest_edge[0]
+                        stack = [current_node]
+                        retry_count = 0
+                    else:
+                        break
+                else:
+                    break
+    
+    debug_print("Fin du parcours eulerien...", debug_mode)
+    if retry_count >= max_retries * 2:
+        debug_print("/!\\ Problème rencontré : Déneigeuse bloquée dans un cycle.", debug_mode)
+        return result[:len(result)-retry_count] # suppression du cycle de la path
+    
+    debug_print(f"Longueur du chemin : {len(result)}", debug_mode)
+    debug_print(f"Nombre d'arêtes du drone : {len(drone_edges)}", debug_mode)
+    
+    if not result:
+        debug_print("/!\\ Aucun chemin possible avec cet algorithme", debug_mode)
+        return []
+        
+    return result
+
+def process_hierholzer_v2(graph, drone_edges, debug_mode=False):
+    """
+    Traite le graphe avec l'algorithme de Hierholzer en utilisant les arêtes du drone.
+    
+    Parameters:
+        graph : Le graphe orienté de Montréal
+        drone_edges : Liste des arêtes trouvées par le drone [(u,v), ...]
+        debug_mode : Mode debug pour l'affichage d'informations supplémentaires
+    
+    Returns:
+        list : Liste des arêtes formant le chemin de la déneigeuse
+    """
+    debug_print("Application de l'algorithme de Hierholzer avec les arêtes du drone...", debug_mode)
+    
+    path = parcours_eulerien(graph, drone_edges, debug_mode)
+    
+    return path 
\ No newline at end of file
diff --git a/ero1/src/deneigeuses/maps/verdun.py b/ero1/src/deneigeuses/maps/verdun.py
new file mode 100644
index 0000000..e949b42
--- /dev/null
+++ b/ero1/src/deneigeuses/maps/verdun.py
@@ -0,0 +1,37 @@
+# FICHIER DEPRECATED : Ce fichier n'est plus utilisé.

+

+import osmnx as ox

+import networkx as nx

+import matplotlib

+matplotlib.use('TkAgg')

+

+def create_verdun():

+    """

+    Crée une version fortement connexe du graph représentant

+    le quartier de Verdun

+    Parameters:

+    None

+    """

+    G = ox.graph_from_place("Verdun, Montréal, Québec, Canada", network_type='drive')

+    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(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)

+

+    ox.plot_graph(G)

+

+    fig, ax = ox.plot_graph(G, show=False, save=True, filepath='graph.png', dpi=300)

+

+    return G

+

+create_verdun()
\ No newline at end of file