1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
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
|
