Newer
Older
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
## Introduction
Dans ce TP, nous allons implémenter un algorithme de Dikjstra pour essayer de trouver le plus court chemin à partir d'un noeud donné dans un graph.
Nous allons aussi utiliser la bilbiothèque graphstream pour comparer nos résultats à l'algorithme de cette bibliothèque
### Génération des graphs
Pour générer les graphs, j'ai utilisé un générateur aléatoire, voici la méthode utilisée :
```java
private static Graph getRandomGraph(String id, double averageDegree, int nodeCount) {
Graph g = new SingleGraph(id);
Generator gen = new RandomGenerator(averageDegree, false, false, "", "length");
gen.addSink(g);
gen.begin();
for(int i = 0; i < nodeCount; ++i)
gen.nextEvents();
gen.end();
gen.removeSink(g);
return g;
}
```
On va créer un graph puis grâce au générateur, on va créer un nombre de noeud défini en paramètre de la méthode, ces noeuds seront liés par des arrêtes créées de telle sorte que le degré moyen du graph soit celui défini en paramètre de la méthode.
En plus de cela, le générateur va associer à chaque arrête une valeur 'length' choisie aléatoirement entre 0 et 1
Tous les graphs que l'on génère pour les tests sont créés avec ces paramètres stockés dans des constantes:
```java
private final static int TEST_GRAPH_COUNT = 25;
private final static double AVERAGE_DEGREE = 3;
private final static int NODE_COUNT = 500;
```
- GRAPH_COUNT : Le nombre de graphs de test
- AVERAGE_DEGREE : Le degré moyen de chaque graph de test
- NODE_COUNT : Le nombre de noeud de ces graphs
J'ai toujours gardé les deux premiers paramètres constants en changeant uniquement le nombre de noeuds des graphs pour mes tests.
### L'algorithme implémenté
Voici l'algorithme:
```java
/**
* @param g The graph on which you want to run dijkstra algorithm on
* @param source The source node from which you want to calculate distances
* @return An object of type DijkstraResult on which you can require path
*/
private static DijkstraResult dijkstra(Graph g, Node source) {
assert source != null;
HashMap<Node, Node> previous = new HashMap<>();
HashMap<Node, Double> distances = new HashMap<>();
ArrayList<Node> nodes = new ArrayList<>();
g.nodes().forEach(n -> {
nodes.add(n);
distances.put(n, Double.POSITIVE_INFINITY);
previous.put(n, null);
});
distances.put(source, 0.0);
while(!nodes.isEmpty()) {
Node n = findMin(nodes, distances);
if(n == null) break;
nodes.remove(n);
n.neighborNodes().forEach(nei -> updateDistances(distances, previous, n, nei));
}
return new DijkstraResult(previous, distances, source);
}
```
Cet algorithme va commencer par initialiser les variables utilisées, premièrement les HashMap contenant les distances de chanque noeud ainsi que leur prédécésseur.
Ensuite, on va trouver la distance minimale pour aller jusqu'à chaque noeud grace à la méthode findMin:
```java
/**
* @param nodes ArrayList of nodes where you want to find the minimum distance
* @param distances the HashMap of distances
* @return the Node with the minimum distance
*/
private static Node findMin(ArrayList<Node> nodes, HashMap<Node, Double> distances) {
Double min = Double.POSITIVE_INFINITY;
Node minNode = null;
for(Node n : nodes) {
Double dist = distances.get(n);
if(dist < min) {
min = dist;
minNode = n;
}
if(min == 0.0) break;
}
return minNode;
}
```
Puis on va mettre à jour les distances avec les nouvelles données:
```java
/**
* @param distances the HashMap of distances
* @param previous the HashMap of previous nodes
* @param n1 Node number 1
* @param n2 Node number 2
*/
private static void updateDistances(HashMap<Node, Double> distances, HashMap<Node, Node> previous, Node n1, Node n2) {
Double distN1 = distances.get(n1);
Double distN2 = distances.get(n2);
Edge n1n2 = n1.getEdgeBetween(n2);
assert n1n2 != null;
Double lengthN1N2 = Double.parseDouble(n1n2.getAttribute("length").toString());
if(distN2 > distN1 + lengthN1N2) {
distances.put(n2, distances.get(n1) + lengthN1N2);
previous.put(n2, n1);
}
}
```
L'algorithme renvoie un objet de type DikjstraResult qui permet d'obtenir les distances et chemins entre la source et un autre noeud du graph.
J'ai testé l'algorithme avec plusieurs types de graphs, pour essayer de voir s'il y avait des erreurs mais tous les cas semblent être pris en compte, qu'il y ait des chemins entre la source et les autres noeuds ou non.
### L'algorithme de GraphStream
L'algorithme utilisé par GraphStream semble assez complexe, il crée un objet Data pour chaque noeud lorsuq'il itère dessus dans la méthode `makeTree()`
Les résultat sont ensuite stockés pour permettre de les récupérer, dans notre cas avec les méthodes `getPath()` et `getPathLength()`
### Tests effectués
Les tests effectués ont été les suivants:
- Tests sur plusieurs graphs de taille différente
- Tests sur des graphs de même taille mais de degré moyen différent
- Tests avec des graphs sans chemin entre la source et la destination
- Tests sur des graphs non connexes mais avec un chemin entre la source et la destination
### Résultats obtenus
Voici les résultats obtenus, les tests ont été faits avec des graphs de taille 100, 500, 1000, et 10000.
Premièrement les temps d'éxécution des algorithmes:
- Pour 100 noeuds:
- 500 noeuds:
- 1000 noeuds:
- 10 000 noeuds:
On remarque que plus le nombre de noeuds augmente plus la différence de temps d'éxécution entre l'algorithme de graphstream et celui implémenté augmente.
Pour 100 noeuds, la différence n'est presque pas notable,
pour 500, on observe une petite différence,
elle est encore un peu plus présente avec 1000 noeuds
mais là où ça devient vraiment significatif c'est avec 10000 noeuds, on observe un temps très bas pour l'algorithme de graphstream mais des temps qui se comptent en secondes pour l'algorithme implémenté.
Pour ce qui est des résultats de l'algorithme, aucune différence n'a été notée lors de l'ensemble des tests.
Autre remarque, lors des tests, j'ai remarqué qu'au niveau des premiers graphs, le temps était toujours très élevé comparé aux autres, je n'ai pas d'explication a ce phénomene, une hypotèse peut être le temps qu'il faut au processeur pour commencer à travailler à pleine puissance.
### Explications des résultats et des différences
On peut assez aisaiment comprendre la différence entre les résultats de l'algorithme intégré à graphstream et celui implémenté.
Premièrement, celui que j'ai implémenté est beaucoup moins optimisé que celui dans graphstream, aussi, il est moins complexe que celui de graphstream, on peut donc comprendre pourquoi il est plus long.
Et bien sûr une autre raison est le fait que je ne suis pas expert dans le domaine des graph contrairement aux personnes ayant créé l'algorithme dans graphstream.
## Conclusion
Pour conclure, il est préférable d'utiliser l'algorithme intégré à graphstream lorsqu'on veut atteindre de bonnes performances, surtout lors d'utilisation de grands graphs.
On peut peut-être penser que dans tous les cas, l'utilisation d'un algorithme d'une bibliothèque spécifique sera forcément plus efficace qu'un algorithme fait à la main pour répondre à nos besoins.