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
# Graphes - TP3 (DJIKSTRA)
## INTRODUCTION
Ce tp consiste à implémenter une méthode naive de Djisktra sur les graphes pour trouver le plus court chemin entre un noeud et tous les autres. Ensuite, faire une étude comparative avec celle de graphStream et en tirer des conclusions.
## 1)- RandomGenerator
Pour générer un graphe de grande taille, nous avons uttilisé RandomGenerator de GraphStream qui est capable de créer des graphes de n'importe quelle taille. Avec ce générateur, nous pouvons augmenter la probabilité que tous les noeuds soient connectés entre eux en mettant en paramètre un grand nombre de dégré moyen.
Dans notre cas, nous faisons varier le dégré de 10 à 50 en fonction de la taille de la graphe que nous souhaitons avoir.
```
Generator g = new RandomGenerator(10,false, false,"","cap");
```
- le premier paramètre determine le dégré moyen.
- le premier boolean consiste à autoriser ou non une suppression dans le graphe.
- le troisième paramètre indique que notre graphe n'est pas orienté.
- les deux derniers paramètres sont respectivement les valeurs au hasard que nous attribuons aux noeuds aux liens.
Voici notre code complet pour générer un graphe aléatoire
Graph graph = new SingleGraph("Graphe aléatoire");
System.setProperty("org.graphstream.ui.renderer", "org.graphstream.ui.j2dviewer.J2DGraphRenderer");
graph.addAttribute("ui.quality");
graph.addAttribute("ui.antialias");
Generator g = new RandomGenerator(10,false, false,"","cap");
g.addSink(graph);
g.begin();
for (int i = 0; i < taille; i++)
g.nextEvents();
g.end();
À chaque appel à nextEvents() , k opérations sont exécutées avec k le degré moyen.
## 2)- Djikstra Naive
Dans notre méthode, nous commençons par initialiser la distance des noeuds. 0 pour la source et infini pour les autres.
En suite, nous initilisons notre liste de type HashMap en y insérant le premier noeud. Ce HashMap va nous permettre de mieux gérer les noeuds, effectuer quelques tests et les mettre en attente.
Nous effectuons un parcours en largeur sur notre graphe en prenant en compte les priorités. Le noeud d'évaluation doit être celui dont la distance est la plus faible par rapport à la source. Ceci est géré dans la méthode priporiteMin().
Nous calculons les nouvelles distances pour diriger les voisins en gardant les distances à chaque évaluation puis on ajoute les voisins qui ne sont pas encore installés dans la liste d'attente.
## 3)- Djisktra de GraphStream
La classe Djikstra de GraphStream une classe prédéfinie qui permet de trouver le plus court chemins entre deux noeuds d'un granphe, ou entre un noeud que nous allons définir comme source et tous les autres.
L'utilisation de Djikstra est simple, il suffit tout simplement de lui montrer le graphe sur lequel il doit travailler et lui donner un noeud de départ.
Nous l'utilisons dans la méthode djistraPCC qui prend en paramètre un graphe. Le premier noeud du graphe est par défaut le noeud de départ.
Dijkstra dijkstra = new Dijkstra(EDGE, null, null);
dijkstra.init(graph);
dijkstra.setSource(graph.getNode("0"));
dijkstra.compute();
Cet algorithme de Djikstra a une complexité de O(n log(n) + m) avec n le nombre de noeuds et m le nombre de liens.
## 4) - Tests et résultats
Nos tests sont réalisés dans le fichier Main.java
- generer_aleatoire(int taille) est la méthode qui génère un graphe d'une taille égale au nombre pris en paramètre. La taille peut varier aussi selon le dégré moyen que nous utilisons.
- Le dégré moyen est à 50 pour un graphe de taille compris entre 10000 et 100000; et 10 pour le reste. Pour un grand nombre de noeuds, nous faisons grimper le dégré moyen pour ne pas qu'il ait trop de noeuds isolés.
- Nous faisons des tests des tailles de noeuds compris dans l'ennsemble {10, 100, 1000, 10000, 100000}
Nous calculons en même temps le temps d'éxécution des deux principales méthodes en utilisant
System.currentTimeMillis();
qui nous retourne le temps présent en milliseconde.
Grâce aux tests effectués, nous avons obtenu des résultats que nous avons stockés dans des fichiers textes djikstraNaive et djisktraGS. Ces données sont utilisées pour faire une représentation graphique avec gnuplot.
Nous remarquons que plus la taille du graphe augmente, plus les temps d'exécution évoluent.
Pour des graphes de petites tailles, la méthode naive passe à peu près le même nombre de temps que celle de graphStream. Quand il s'agit d'une taille proche de 100000, la méthode naive peut mettre plusieurs minutes à s'éxécuter.
Ce tp m'a permis de mieux comprendre le fonctionnement de l'algorithme de Djikstra et de découvrir celle de GraphStream. Il m'a aussi permis d'implémenter des lignes de codes à partir
d'un algorithme donné en cours, cette partie fut également la grande difficulté de ce tp.