diff options
Diffstat (limited to 'ero1/src/deneigeuses/hierholzer_v2.py')
| -rw-r--r-- | ero1/src/deneigeuses/hierholzer_v2.py | 168 |
1 files changed, 168 insertions, 0 deletions
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 |