Newer
Older
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
# TP3 - plus courts chemins
### De Molinier Hugo
#### Université Le Havre Normandie
Novembre 2025
---
## Introduction
Vous êtes un cycliste muni d'un vélo électrique et des cartes de quelques villes qui indiquent l'altitude de chaque intersections de la ville. Votre vélo électrique se décharge lors des montées et se recharge lors des descentes. Vous voulez calculer des itinéraires dans les villes dont vous avez les cartes en vue de vos prochaines vacances mais en minimisant la décharge de votre vélo.
On considère que s'il existe une route montante (ou plate) connectant l'intersection A et l'intersection B, le coût en électricité associé pour le vélo est 5\*(hauteur(B)-hauteur(A))+2 Wh et si la route descend alors le vélo se recharge de (hauteur(B)-hauteur(A))/2 Wh.
Chaque ville est représentée par un graphe orienté dont les sommets sont les intersections de rues et les arêtes sont les rues.
## Graphes représentant des villes
Ouvrez le fichier d'un des [graphes](src/main/resources/graphe_lehavre.dgs) fourni dans les ressources de ce TP.
1. Est-ce que les coûts des arêtes sont fournis ? Si non donnez la fonction qui prend en entrée une arête et renvoie le coût en dépense d’électricité de cette arête.
#### Application
Pour commencer avant tout, ils faut pouvoir faire une fonction pour ouvrir les fichiers .dgs . Donc on fait Graph getTheFileFromPath(String path) pour récupéré l'objet Graph du fichier
Non les coûts des arêtes ne sont pas fournis. Donc pour calculer le cout on fait une fonction pour une arretes données retournes qui fait ca :
```java
if (aHauteur<=bHauteur){//donc monte
return (5*(bHauteur-aHauteur)+2f);
}
return ((bHauteur-aHauteur)/2f);
```
#### Résultat
Par exemple, pour l'arrete 5 du graphe_grenoble.dgs, cela retourne -4.0 :
---
2. Est-ce que les coûts des arêtes peuvent être négatifs ? Est-ce que le graphe peut contenir des cycles de coût négatif ? En déduire l'algorithme adapté pour calculer le plus court chemin sur ces graphes.
#### Application
Pour savoir s'il y a des cycles négatifs. On prend en compte que hauteur = 0.
Donc 5\*(0-0) +2 =2 (montée) et (0-0)/2 = 0 (déscente).
Donc montée + déscente = 2. Donc pas de cycle négatif.
L'algorithme le plus adapté pour un parcours de graph avec des couts d'arretes négatifs mais sans cycle est l'algorithme de Bellman-Ford.
Sur cette valeurs , on suppose que les fichiers graphes sont fait avec des valeurs réels ou réaliste. Hauteur (n mètre au dessus de la mer)
## Algorithme de plus court chemin
Vous avez travaillé en cours sur des algorithmes de plus courts chemins.
1. En utilisant le cours, implémentez l'algorithme de plus court chemin que vous avez donné en réponse de la question 1.2.
2. Pensez à documenter et tester votre code. En bref, faites un travail propre.
#### Application
On a implémenter l'algorithme de bellmanFord qui renvoie 2 map. Fonction BellmanFord
Une map couts contenant le coût minimal pour atteindre chaque nœud u depuis la source s.
Une map pred indiquant le prédécesseur de chaque nœud sur le plus court chemin depuis la source.
On a aussi fait les améliorations possible (S'arrêter si pendant une itération il n'y a pas eu de mise à jour) qui change de 2s le temps d'executions pour graphe_lehavre.dgs par exemple.
```java
public static BellmanFordResult BellmanFord(Graph graph, Node startNode){
Map<Node,Float> mapCost = new HashMap<>();
Map<Node, Node> pred = new HashMap<>();
graph.forEach( node -> {
float value = node == startNode ? 0f: Float.POSITIVE_INFINITY;
mapCost.put(node, value);
pred.put(node, null);
});
AtomicBoolean updated = new AtomicBoolean(true);
for (int k = 1; k < graph.getNodeCount() - 1 && updated.get(); k++) {
updated.set(false);
graph.edges().forEach(edge ->{
float edgeCost = edge.hasAttribute("weight")
? ((Number) edge.getAttribute("weight")).floatValue()
: getCostOfTheArete(edge);
Node sourceNode =edge.getSourceNode();//u
Node targetNode =edge.getTargetNode();//v
if (mapCost.get(sourceNode) +edgeCost<mapCost.get(targetNode)) {
mapCost.put(targetNode,mapCost.get(sourceNode) +edgeCost);
pred.put(targetNode, sourceNode);
updated.set(true);
}
});
}
return new BellmanFordResult(mapCost,pred);
}
```
## Campagne de tests
Lorsqu'on implémente un nouvel algorithme, il est important de tester son efficacité.
1. Calculez le plus court chemin (au sens de la minimisation de l’électricité consommé) du sommet d'identifiant "33317746" au sommet d'identifiant "144477138" dans le graphe représentant la ville du Havre ("graphe_lehavre.dgs").Quel est le coût total en électricité de ce chemin ? Affichez ce chemin en modifiant certains paramètres d'affichages par défaut pour qu'il soit visible.
#### Application
On a implémenter la possibilité d'optenir un chemin + son cout .
Le plus court chemin (au sens de la minimisation de l’électricité consommé) du sommet d'identifiant "33317746" au sommet d'identifiant "144477138" dans le graphe représentant la ville du Havre ("graphe_lehavre.dgs") est
[33317746, 33294633, 11250583245, 11250583244, 33294670, 33317737, 33317639, 33229197, 235046422, 33229200, 33229202, 33229204, 33165539, 33165540, 33294010, 33294036, 33294227, 33294232, 33294220, 33294221, 33294222, 33294246, 899836216, 33233796, 221200001, 221200010, 1016786415, 113364238, 3071543043, 144476197, 1027177076, 1027177104, 144476928, 144476934, 144476876, 113358746, 144476812, 920732771, 144477069, 144477089, 144477084, 144477103, 144477233, 151008691, 151008690, 144477138]
Le coût total en électricité de ce chemin est de 325 Wh.
Pour afficher le tracé sur le graph, on ajoute l'attribut edge.inPath a chaque arrete.
2. Il est évident qu'un seul exemple n'est pas représentatif. Pour chacun des graphes fournis, effectuez des tests sur l'algorithme.
#### Application
Pour rendre les tests représentatifs, nous n’avons pas utilisé un seul exemple de nœuds.
- Pour chaque graphe fourni, nous avons exécuté plusieurs tests en choisissant aléatoirement les nœuds de départ et d’arrivée.
- Pour notre algorithme Bellman-Ford, 25 tests ont été réalisés par graphe.
Ainsi, les résultats tiennent compte des variations dues au choix des nœuds et à la structure du graphe. Plus le nombre de test est élévé moins les variations du pc rentrera en compte.
#### Résultat
Voici la courbes du temps d'éxécution de l'ensemble des graphes, généré avec le [script gnuplot](gnuplot/script/plot_courbeAllMyBellman.gnu)
On peut voir les 8 courbes représentant l'ensembles des graphes et durée d'éxécution en micro-seconde.
#### Information supplémentaire
Complexité de bellmanFord avec Optimisation
| Single-source (S) | All-pairs (A) |
|-----------------|---------------|
| n·m | n²·m |
| Graphe | Nombre de nœuds | Nombre d'arêtes |
|-------------------|----------------|----------------|
| graphe_cherbourg | 13 556 | 32 737 |
| graphe_grenoble | 1 711 | 3 730 |
| graphe_isneauville | 262 | 552 |
| graphe_lehavre | 3 627 | 8 858 |
| graphe_montivilliers | 768 | 1 590 |
| graphe_morlaix | 1 037 | 2 223 |
| graphe_ploemer | 1 441 | 3 163 |
| graphe_rome | 43 223 | 88 831 |
#### Commentaire
On peut observer que le nombre de nœuds et d'arêtes influe directement sur le temps d'exécution.
Cependant, le temps reste exprimé en millisecondes (ms).
Le choix des nœuds de départ et d'arrivée peut également impacter la vitesse de l'algorithme, car certaines distances sont calculées plus rapidement que d'autres, surtout avec l’optimisation “early exit” du Bellman-Ford.
---
3. On souhaite maintenant étudier la version de l'algorithme de Graphstream. Effectuez des tests sur cet algorithme.
#### Application
Pour évaluer les performances de notre algorithme, nous avons créé une [classe de test](src/test/java/org/example/MainTest.java) dans le projet.
Cette classe permet de comparer directement notre implémentation du Bellman-Ford avec celle de GraphStream, qui est optimisée et utilise les fonctionnalités internes de la bibliothèque.
On c'est assurer que les résultats de ses 2 algorithmes sont les memes pour assurer que les
prennent bien le plus court chemin.
Vu que c'est une comparaison entre 2 algorithme, le choix des Nodes n'est pas important mais doit rester les memes entre les 2 pour bien comparé. Et executer les algorithme
Important : pour l’équité, si une arête possède déjà un attribut weight, nous le réutilisons au lieu de recalculer le coût pour notre algorithme.
Aussi pour limité au maximum les variations de performance, j'effectue les 2 algorithme l'un après l'autre pour chaque itération.
Limite : On limite l'éxécution à 5 min pour chaque algorithmes sachant qu'il y a 5 tests par graphes sur 2 algorithmes différent.
#### Résultat
Pour un graphe de la taille de celui du Havre, comprenant 3627 nœuds et 8858 arêtes, on observe que l’algorithme de GraphStream est environ 15 fois plus lent que notre version optimisée.
Dans ce graphique, chaque cluster représente un test avec deux barres :
- Bleu : GraphStream
- Rouge : notre algorithme maison
Les durées sont exprimées en secondes pour plus de lisibilité. Mais on été enregistrer en ms.
Chaque tests est fait un noeud start et end aléatoir dans le graphe.
On peut donc aussi voir que le temps d'execuition pour chaque noeud n'est pas similaire
#### Comprendre pourquoi l'algorithme de GraphStream est lent
Le code de GraphStream utilise une approche récursive pour reconstruire les chemins les plus courts.
On peut voir que la fonction rappelle elle-même pour chaque prédécesseur, créant une copie du chemin à chaque appel.
En conclusion, cette méthode devient très lente sur des graphes larges ou denses, car la récursivité combinée aux multiples copies de chemins fait croître le nombre d’opérations de manière exponentielle avec le nombre de nœuds et de branches.
```java
private void pathSetShortestPath_facilitate(Node current, Path path,
List<Path> paths) {
Node source = graph.getNode(this.source_id);
if (current != source) {
Node next = null;
ArrayList<? extends Edge> predecessors = (ArrayList<? extends Edge>) current
.getAttribute(identifier+".predecessors");
while (current != source && predecessors.size() == 1) {
Edge e = predecessors.get(0);
next = e.getOpposite(current);
path.add(current, e);
current = next;
predecessors = (ArrayList<? extends Edge>) current
.getAttribute(identifier+".predecessors");
}
if (current != source) {
final Node c = current ;
predecessors.forEach(e -> {
Path p = path.getACopy();
p.add(c, e);
pathSetShortestPath_facilitate(e.getOpposite(c), p, paths);
});
}
}
if (current == source) {
paths.add(path);
}
}
```
## Difficulté rencontrée
Lors du TP, nous avons découvert l’importance d’utiliser un timeout pour l’exécution des algorithmes avec GraphStream.
Sans cette protection, certains calculs sur les grands graphes pouvaient bloquer le programme indéfiniment.
L’utilisation de Future et executor.submit() nous a permis de limiter le temps d’exécution et d’éviter que le programme prenne trop de temps.
J'ai découvert et appris comment les utiliser lors de ce tp.
## Conclusion
Ce TP a permis de mettre en pratique plusieurs notions essentielles sur les graphes et les algorithmes de plus courts chemins :
- Manipulation des graphes : ouverture de fichiers .dgs, lecture des nœuds et arêtes, attribution de coûts selon des critères spécifiques.
- Analyse des coûts et choix de l’algorithme : identification des arêtes à coût négatif et sélection de Bellman-Ford comme algorithme adapté pour des graphes sans cycles de coût négatif.
- Implémentation et optimisation : création d’une version maison de Bellman-Ford avec optimisation “early exit”, réduisant considérablement le temps d’exécution.
- Tests et évaluation des performances : exécution de multiples tests sur différents graphes, analyse de la variabilité des temps selon le choix des nœuds et la densité du graphe.
- Comparaison : mise en évidence des limites de l’implémentation de GraphStream, améliorer ma facon de comparer de facon pertinente.
En résumé, ce TP a permis non seulement de comprendre la logique des algorithmes de plus courts chemins mais aussi d’appréhender les contraintes de performance liées à la structure des graphes et à l’implémentation de l’algorithme. Il a montré l’importance d’optimiser les algorithmes et de tester leur comportement sur différents scénarios pour obtenir des résultats fiables et efficaces.