add: added projectsHEADmain

1 files changed, 128 insertions, 0 deletions

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