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
#TP3 - Les plus courts chemins
Ce TP consiste à comparer les performances entre 2 algorithmes de dijkstra (le notre et celui de GraphStream).
l'algorithme de dijkstra calcule le plus court chemin entre deux noeuds tant qu'aucun des poids du graphe ne soit négatif.
## Fonctionnement
On utilise la classe RandomGenerator de GraphStream pour créer un graphe, (avec un nombre de nodes et un nombre d'arrête moyenne passés en paramètres). Nous pouvons aussi définir un poids pour chaque arrêtes grace au générateur mais devons faire avec le fait qu'il ne génère que 0 ou 1.
Nous avons crée donc un generateur (RandomGenerator) avec un degré moyen, nous lui disons que les arrêtes ont un poids sinon dijkstra ne marche pas, puis on génère. une fois fait nous attribuons une valeur numérique à chaque attribut poids.
```java
private static void genererGraph(Graph graph, int nbNoeuds, double degreMoyen, boolean estOriente) {
RandomGenerator generator = new RandomGenerator(degreMoyen);
generator.setDirectedEdges(estOriente, true);
generator.addSink(graph);
generator.addEdgeAttribute("poids");
generator.begin();
for (int i = 0; i < nbNoeuds; i++) {
generator.nextEvents();
}
generator.end();
graph.edges().forEach(e -> {
double poids = (double) e.getAttribute("poids");
e.setAttribute("poids", (int) (poids * 20)); //multiplie le nombre par celui que l'on veut
});
}
```
## Implémentation de notre algorithme dijkstra
Dijkstra effectue un parcours en largeur (BFS). l'algorithme regardes tout les noeuds voisins du noeud courant, en choisi un et regarde encore une fois tout les voisins, etc.
On initialise tout les noeuds à une distance de -1, notre node source prend une distance 0, ensuite nous l'insérons dans une liste de noeuds puis allons actualiser la distance entre lui et ses voisins.
Si on trouve une distance plus courte que celle actuelle nous ajoutons le noeud dans notre file d'attente qui répètera les étapes fait ci-dessus.
```java
public static void dijkstra(Graph graph, Node source, boolean oriente) {
graph.nodes().forEach(n -> n.setAttribute("distance", -1));
source.setAttribute("distance", 0);
ArrayList<Node> listNodes = new ArrayList<>();
listNodes.add(source);
while (!listNodes.isEmpty()) {
Node nCourante = listNodes.remove(0);
// obtient toutes les arêtes restantes si le graphe est orienté sinon récupère les voisins restants.
Stream<Node> nodes = oriente ? nCourante.leavingEdges().map(Edge::getTargetNode) : nCourante.neighborNodes();
nodes.forEach(voisin -> {
int distanceCourante = (int) nCourante.getAttribute("distance");
int distanceVoisin = (int) voisin.getAttribute("distance");
int poidsArrete = (int) voisin.getEdgeBetween(nCourante).getAttribute("poids");
int distanceCalculee = distanceCourante + poidsArrete;
// Si vrai une distance plus courte a été trouvé.
if (distanceVoisin == -1 || distanceVoisin > distanceCalculee) {
voisin.setAttribute("distance", distanceCalculee);
voisin.setAttribute("parent", nCourante);
listNodes.add(voisin);
}
});
}
}
```
## Dijkstra par GraphStream
GraphStream à sa propre implémentation de Dijkstra pour cela nous crééons une variable de type Dijkstra.
Ensuite on l'initialise avec un graph et ajout notre noeud de départ.
Ensuite on peut lancer le calcule.
```java
Dijkstra d = new Dijkstra();
d.init(g); // g est un graph.
d.setSource(n); // n est le noeud source.
d.compute();
```
## Les test
On exécute les deux algorithmes un à un sur des graphs générés aléatoirement mais avec le même nombre de noeuds et le même degré moyen.
```java
for (int i = 0; i < NB_TEST; i++) {
SingleGraph graph = new SingleGraph("Comparatif graphe de taille identique");
genererGraph(graph, 3000, 70, false);
Node n = graph.getNode(0);
resultatsCustom[i] = calculTempsCustom(graph, graph.getNode(0));;
resultatsGraphStream[i] = calculTempsGraphStream(graph, graph.getNode(0));
}
System.out.println("Comparatif de " + NB_TEST + " résultats pour un graphe de taille identique :");
affichageComparatif(resultatsCustom, resultatsGraphStream);
private static void affichageComparatif(long[] resultatsCustom, long[] resultatsGraphStream) {
System.out.println("Custom dijkstra :\n\ttemps :");
System.out.println("\t\tMinimal: " + Arrays.stream(resultatsCustom).min().getAsLong() + "ms.");
System.out.println("\t\tMaximal: " + Arrays.stream(resultatsCustom).max().getAsLong() + "ms.");
System.out.println("\t\tMoyenne: " + Arrays.stream(resultatsCustom).average().getAsDouble() + "ms.");
System.out.println("GraphStram dijkstra :\n\ttemps :");
System.out.println("\t\tMinimal: " + Arrays.stream(resultatsGraphStream).min().getAsLong() + "ms.");
System.out.println("\t\tMaximal: " + Arrays.stream(resultatsGraphStream).max().getAsLong() + "ms.");
System.out.println("\t\tMoyenne: " + Arrays.stream(resultatsGraphStream).average().getAsDouble() + "ms.");
}
private static long calculTempsCustom(Graph g, Node n) {
long time = System.currentTimeMillis();
dijkstra(g, n, false);
time = System.currentTimeMillis() - time;
return time;
}
private static long calculTempsGraphStream(Graph g, Node n) {
Dijkstra d = new Dijkstra();
d.init(g);
d.setSource(n);
long time = System.currentTimeMillis();
d.compute();
time = System.currentTimeMillis() - time;
return time;
}
```
```
Comparatif de 200 résultats pour un graphe de taille identique :
Custom dijkstra :
temps :
Minimal: 467ms.
Maximal: 875ms.
Moyenne: 613.24ms.
GraphStram dijkstra :
temps :
Minimal: 37ms.
Maximal: 106ms.
Moyenne: 61.99ms.
Comparatif de 200 résultats pour un graphe de taille aléatoire :
Custom dijkstra :
temps :
Minimal: 478ms.
Maximal: 949ms.
Moyenne: 683.095ms.
GraphStram dijkstra :
temps :
Minimal: 37ms.
Maximal: 120ms.
Moyenne: 65.475ms.
```
On peut observer que l'implémentation de GraphStream est beaucoup plus rapide que notre version naïve.
La différence vient de l'optimisation lié au tas de Fibonnacci sur l'ajout et le retrait de nodes. au vu de la complexité ``O(m + nlog n)``, tandis que notre complexité est ``O(n + m)``
On peut donc se dire que l'implémentation de l'algorithme sera toujours à peu près similaire mais peut-être optimisé via différent moyen (tas de Fibonnacci, etc.)