Newer
Older
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
## Plan
* [Rappelle du projet](#rappelle-du-projet)
* [Utilite de l algorithme de didjkstra](#utilite-de-l-algorithme-de-didjkstra)
* [RandomGenerator](#randomgenerator)
* [Generateurs de graphes aleatoire](#generateurs-de-graphes-aleatoire)
* [Description de l algorithme naive de dijkstra](#description-de-l-algorithme-naive-de-dijkstra)
- [***Parcours en largeur***](#parcours-en-largeur)
- [***Fil d attente prioritaire***](#fil-d-attente-prioritaire)
- [***Etapes de l algorithme***](#etapes-de-l-algorithme)
- [***Complexite***](#complexite)
- [***code generateur***](#code-generateur)
- [***Fichier***](#fichier)
* [Description de l algorithme dijkstra de graphstream](#description-de-l-algorithme-dijkstra-de-graphstream)
* [Comparaison des deux version selon le temps d'execution](#comparaison-des-deux-version-selon-le-temps-d-execution)
* [Temp d execution naive didjikstra](#temp-d-execution-naive-didjikstra)
* [***Code naive didjkstra***](#code-naive-didjkstra)
* [***Stocker le resultat dans un fichier naive didjkstra***](#stocker-le-resultat-dans-un-fichier-naive-didjkstra)
* [***Resultat naive didjkstra***](#resultat-naive-didjkstra)
* [***Script gnuplot naive didjkstra***](#script-gnuplot-naive-didjkstra)
* [***Resultat en image naive didjkstra***](#resultat-en-image-naive-didjkstra)
* [Temp d execution graphstream didjikstraa](#temp-d-execution-graphstream-didjikstra)
* [***Code graphstream didjikstra***](#code-graphstream-didjikstra)
* [***Stocker le resultat dans un fichier graphstream didjikstra***](#stocker-le-resultat-dans-un-fichier-graphstream-didjikstra)
* [***Resultat graphstream didjikstra***](#resultat-graphstream-didjikstra)
* [***Script gnuplot graphstream didjikstra***](#script-gnuplot-graphstream-didjikstra)
* [***Resultat en image graphstream didjikstra***](#resultat-en-image-graphstream-didjikstra)
* [Temp d execution comparaison](#temp-d-execution-comparaison)
* [***Lancer les deux version***](#lancer-les-deux-version)
* [***Fichier source***](#fichier-source)
* [***Script gnuplot***](#script-gnuplot)
* [***Resultat en image***](#reultat-en-image)
* [Quelques test en plus](#quelques-test-en-plus)
* [Tester les deux methode pour voir les plus court chemain](#tester-les-deux-methode-pour-voir-les-plus-court-chemain)
* [***Test des plus court chemain des deux version***](#test-des-plus-court-chemain-des-deux-version)
* [***Test junit de la class naive didjikstra***](#test-junit-de-la-class-naive-didjikstra)
* [Conclusion](#conclusion)
## Rappelle du projet
Ceci est le rapport du travail effectué lors du TP de Graphes sur les plus courts chemins en utilisant deux version de l'algorithme de Didjikstra (naive et celle de graphstream)
Le but de ce [TP](https://eureka.univ-lehavre.fr/mod/assign/view.php?id=56242) est d'implémenter une version naïve de l'algorithme de Dijkstra vu en classe, puis de pouvoir comparer les résultats, notamment les performances produites par cet algorithme avec la version déjà disponible sur [GraphStream](https://graphstream-project.org/doc/Algorithms/Shortest-path/Dijkstra/) ([`documentation`](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Dijkstra.html)).
L'algorithme de Dijkstra sert a calculer le chemin le plus court d'un nœud donné, appelé la source, à tous les autres nœuds du graphe.Il ne fonctionne pas pour des longueurs négatives, que nous utiliserons évidemment ici. Pour l'implémentation, nous utiliserons le générateur de graphes d'une taille donnée N déjà fourni par l'API Graphstream.
Il existe plusieurs générateurs, mais nous allons ici nous intéresser au RandomGenerator.
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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
## RandomGenerator
Ces algorithmes seront testés sur des graphes générés aléatoirement grâce au [Random graph generator](https://graphstream-project.org/doc/Generators/Random-graph-generator/) ([`documentation`](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/generator/RandomGenerator.html)). Ici, nous devons travailler sur des graphes orientés pour faire la liste des plus courts chemins entre la source et tous les autres noeuds de notre graphe.
Afin d'expliquer au mieux la démarche suivie lors de ce travail, nous allons commencer par expliquer comment utiliser le [Random graph generator](https://graphstream-project.org/doc/Generators/Random-graph-generator/), décrire quel générateur nous avons utiliser et donner ses paramètres.
Par la suite, nous allons décrire les deux algorithmes de Dijkstra en commençant par la version naïve d'implémentée.
Enfin, nous terminerons par décrire les tests effectués afin de comparer les deux algorithmes, et nous présenterons les résultats obtenus sous forme brut et sous forme de graphes.
Ce projet a été réalisé sous `JAVA` avec l'aide de la librarie [GraphStream](https://graphstream-project.org/)
## Generateurs de graphes aleatoire
Ce générateur crée des graphes aléatoires de taille arbitraire. Les liens du graph sont créés en fonction de seuils. Si la distance euclidienne entre deux nœuds est inférieure à un seuil donné, un lien est créé entre ces deux nœuds. Les appels à begin() placent un nœud dans le graphe, puis nextEvents() ajoute un nouveau nœud pour chaque appel et connecte ce nœud à ses voisins en fonction d'une distance plane euclidienne seuil. Le générateur est capable d'ajouter des valeurs choisies au hasard à n'importe quel attribut sur une arête ou un nœud du graphe, et de choisir au hasard la direction de l'arête.
Une liste de propriétés peut être fournie pour les nœuds et les arêtes. Dans ce cas, chaque nouveau nœud ou arête ajouté aura cette propriété et la valeur sera un nombre choisi au hasard. Vous pouvez spécifier une plage à partir de laquelle sélectionner ces nombres.
Par défaut, les arêtes n'ont pas de direction. Des directions peuvent être demandées, auquel cas les directions sont choisies au hasard.
En ce qui concerne la complexité de ce générateur, chaque appel à nextEvents() effectue au plus k opérations, où k est le degré moyen.
### ***code generateur***
Une première partie ou on crée et on donne quelques paramètres à notre générateur comme par exemple le fait que les arêtes soient orientées . Nous devons aussi donner aussi un degré moyen
```java
public RandomGenerator Gen_al(Graph graph ,double avrage_degree){
RandomGenerator random_gen = new RandomGenerator(avrage_degree,false,true);
random_gen.addEdgeAttribute("cap");
random_gen.addSink(graph);
return random_gen;
}
```
Dans cette partie on vas démarrer l'algorithme on lui donnant le génerateur crée précedamant avec un nombre de noued
```java
public void demarrer_genb(RandomGenerator gn , int nb_nd) {
gn.begin();
for (int i=0;i<nb_nd;i++) {
gn.nextEvents();
}
gn.end();
}
```
### ***fichier***
Le code se trouve dans le fichier [Generateur_Aleatoire.java](/src/main/java/tP3GraphePlusCourtChemin/Generateur_Aleatoire.java)
### ***Exemple en image***
## Description de l algorithme naive de dijkstra
On cherche le chemin le plus court à partir d'un seul point(sommet) vers un autre point(sommet), disons X.
### ***Parcours en largeur***
Sa mise en oeuvre se base sur une recherche modifiée en largeur. La recherche en largeur d'abord (BFS) est un algorithme de traversée de graphe qui fonctionne en explorant d'abord tous les nœuds voisins, avant de passer au niveau suivant de voisins (voisins de voisins).
### ***Fil d attente prioritaire***
L'une des modifications de l'algorithme de Dijkstra sur la recherche en largeur d'abord est son utilisation d'une file d'attente prioritaire au lieu d'une file d'attente normale. Avec une file d'attente prioritaire, chaque noeud ajoutée à la file d'attente a une «priorité» et s'insérera en conséquence dans la file d'attente en fonction de son niveau de priorité.
### ***Etapes de l algorithme***
Initialiser le noeud source avec une distance de 0 puisque nous commençons à partir de celui-ci.
Initialiser tous les autres nœuds avec une distance infinie.
Démarrer la boucle de file d'attente après y avoir inséré notre nœud source.
Pour chaque voisin de notre nœud, on calcul la distance provisoire entre la distance du nœud actuel et la distance à son voisin.
Si la distance provisoire est inférieure à la distance du voisin, définissez la distance de ce nœud voisin sur la distance provisoire et mettez-la en file d'attente avec cette distance comme priorité.
Continuez à travers la file d'attente prioritaire jusqu'à ce que nous ayons calculé le chemin le plus court de tous les nœuds vers la source
En option, nous pouvons fournir un nœud cible et dès que ce nœud est retiré de la file d'attente, nous pouvons arrêter notre recherche
### ***Complexite***
La compléxité depend en effet de l'implémenetation des fils d'attente prioritaires.
pour une simple liste sa compléxité sera de ***O(n²)*** alors que pour une liste triée elle sera de ***O(nm)***.
### ***Code***
- Constructeur :
Pour le constructeur de la class on vas lui passer deux paramètre un graph et un noued source , on instancie aussi une Hashmap qui prend un Noeud comme clé et un double comme valeur
```java
Graph graph;
Node source;
HashMap<Node, Double> queue;
public Dijkstra_naïve(Graph graph, Node noeud_source) {
this.graph = graph;
this.source = noeud_source;
this.queue = new HashMap<Node, Double>();
}
```
- Méthode init() :
on rajoute ici deux attributs à chaque noeud du graph distance et parent
```java
private void init() {
for (Node n : graph.getEachNode()) {
n.addAttribute("distance", n.getId().equals(source.getId()) ? 0 : Double.POSITIVE_INFINITY);
n.addAttribute("parent", new Stack<Node>());
}
}
```
- Distance minimal :
```java
private Node getMinDistanceNode(Set<Node> nodes) {
Node Min_Distance_Noued = null;
Double Min_Distance = Double.MAX_VALUE;
for (Node node : nodes) {
Double Noued_Ditance = node.getAttribute("distance");
if (Noued_Ditance < Min_Distance) {
Min_Distance = Noued_Ditance;
Min_Distance_Noued = node;
}
}
return Min_Distance_Noued;
}
```
- Méthode compute() : calculer le plus court chemin
```java
public void compute() {
init();
queue.put(source, source.getAttribute("distance"));
while (queue.size() != 0) {
Node noued_courant = getMinDistanceNode(queue.keySet());
Iterator<Edge> Iterator_Edge = noued_courant.getLeavingEdgeIterator();
queue.remove(noued_courant);
while (Iterator_Edge.hasNext()) {
Edge Edge_Courant = Iterator_Edge.next();
Node Noud_op = Edge_Courant.getTargetNode();
if(! queue.containsKey(Noud_op)) {
Double Distance_Noued_Courant = noued_courant.getAttribute("distance");
Double Poid_Edge = Edge_Courant.getAttribute("cap");
Double somme = Distance_Noued_Courant + Poid_Edge;
Double Distance_Noued_op = Noud_op.getAttribute("distance");
if (Distance_Noued_op > somme) {
Noud_op.setAttribute("distance", somme);
Noud_op.setAttribute("parent", noued_courant);
queue.put(Noud_op, Noud_op.getAttribute("distance"));
}
}
}
}
}
```
### ***Fichier***
on retrouve ici le code source de la class [Dijkstra_naïve.java](/src/main/java/tP3GraphePlusCourtChemin/Dijkstra_naïve.java)
## Description de l algorithme dijkstra de graphstream
Graphstream nous met déja à disposition des algorithmes pour traiter nos graphes et a aussi implémenter sa version de Dijkstra. En effet, cette implémentation utilise en interne Fibonacci Heap, une structure de données qui la rend plus rapide pour les gros graphiques.
Lors d'un appelle de la méthode compute(), l'algorithme calcul non seulement le plus court chemin d'un noeud source vers tout les autres mais aussi permet de prendre également en compte "les longeurs des noeuds" ainsi que d'autres fonctionnalités.
Voici un exemple de code:
```java
Graph graph = ...;
Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.edge, "result", "length");
// calcul le chemin le plus court dans le graphe à partire de A vers tout les autres noeuds
dijkstra.init(graph);
dijkstra.setSource(graph.getNode("A"));
dijkstra.compute();
// Affiche le plus court chemin entre les noeuds A et B
System.out.println(dijkstra.getPath(graph.getNode("B"));
```
## Comparaison des deux version selon le temps d execution
Pour la procédure de test nous allons tour à tour mesurer le temps d'execution de ces deux algorithme en multipliant par pas de un le nombre de noeuds.
On va debuter avec un échantillon de 5000 noeuds
### Temp d execution naive didjikstra
#### ***Code naive didjkstra***
```java
public void DidjikstraNaive(Graph graph) throws Exception {
...
int compteur=1,len=500,maximum=500;
.....
while(compteur<=100) {
...
debut = System.currentTimeMillis();
Dijkstra_naïve naivedidj = new Dijkstra_naïve(graph, graph.getNode(0));
naivedidj.compute();
fin =System.currentTimeMillis();
temp=fin-debut;
....
graph.clear();
compteur++;
len=maximum * compteur;
}
...
}
```
#### ***Stocker le resultat dans un fichier naive didjkstra***
```java
public void DidjikstraNaive(Graph graph) throws Exception {
...
int compteur=1 .. ;
....
BufferedWriter w = new BufferedWriter(new FileWriter("donnée/didjikstanaive.dat"));
while(compteur<=100) {
...
w.write(String.format("%d%6d%n", graph.getNodeCount(),temp));
}
w.close();
}
```
#### ***Resultat naive didjkstra***
Le resultat vas se trouver dans le fichier [didjikstanaive.dat](/donnée/didjikstanaive.dat)
#### ***Script gnuplot naive didjkstra***
Le script se trouver dans le fichier [script_Didjiksta_naive.gnu](/donnée/script_Didjiksta_naive.gnu)
#### ***Resultat en image naive didjkstra***
### Temp d execution graphstream didjikstra
#### ***Code graphstream didjikstra***
```java
public void DidjikstraGraphstream(Graph graph) throws Exception {
...
int compteur=1,len=500,maximum=500;
.....
while(compteur<=100) {
...
debut=System.currentTimeMillis();
Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.EDGE, "result", "length");
dijkstra.init(graph);
dijkstra.setSource(graph.getNode(0));
dijkstra.compute();
fin=System.currentTimeMillis();
temp=fin-debut;
....
graph.clear();
compteur++;
len=maximum * compteur;
}
...
}
```
#### ***Stocker le resultat dans un fichier graphstream didjikstra***
```java
public void DidjikstraNaive(Graph graph) throws Exception {
...
int compteur=1 .. ;
....
BufferedWriter w = new BufferedWriter(new FileWriter("donnée/didjikstraGraphStream.dat"));
while(compteur<=100) {
...
w.write(String.format("%d%6d%n", graph.getNodeCount(),temp));
}
w.close();
}
```
#### ***Resultat graphstream didjikstra***
Le resultat vas se trouver dans le fichier [didjikstraGraphStream.dat](/donnée/didjikstraGraphStream.dat)
#### ***Script gnuplot graphstream didjikstra***
Le script se trouver dans le fichier [script_didjikstra_graphstream.gnu](/donnée/script_Didjiksta_naive.gnu)
#### ***Resultat en image graphstream didjikstra***
### Temp d'execution comparaison
#### ***Lancer les deux version***
```java
Thread threadnaive = new Thread(()->{
try {
Didjk_naive_Temp.main(args);
} catch (Exception e) {
e.printStackTrace();
}
});
Thread threagraphstreamdidj = new Thread(()->{
try {
Didjk_GraphStream_Temp.main(args);
} catch (Exception e) {
e.printStackTrace();
}
});
threadnaive.start();
threagraphstreamdidj.start();
```
#### ***Fichier source ***
Le fichier du code source est [Tester_temp_deux_version.java](/src/main/java/tP3GraphePlusCourtChemin/Tester_temp_deux_version.java)
#### ***Script gnuplot***
Le script se trouver dans le fichier [script_comp.gnu](/donnée/script_comp.gnu)
#### ***Reultat en image***
## Quelques test en plus
### Tester les deux methode pour voir les plus court chemain
#### ***Test des plus court chemain des deux version***
Le fichier du code source est [Tester_temp_deux_version.java](/src/main/java/tP3GraphePlusCourtChemin/Tester_temp_deux_version.java)
#### ***Test junit de la class naive didjikstra***
Le fichier du code source est [Test.java](/src/test/java/tP3GraphePlusCourtChemin/Tester_temp_deux_version.java)
## Conclusion
On peu voir que plus le graphique est grand, plus il faut de temps pour implémenter l'algorithme Djikistra naive (vert).
O (M + N) est la complexité du code dans la version naïve de l'algorithme de recherche en largeur. Ajoutez à cela la recherche de l'élément de priorité la plus basse (min) de complexité O(N), à l'aide d'un algorithme de parcours simple.
Par contre, selon la documentation, l'algorithme fourni par GraphStream prend O (m + nlogn) à chaque fois que vous appelez compute(). En fait, l'utilisation du tas de Fibonacci améliore les performances.