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
|
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
|
