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
|
Option Explicit On
Option Compare Text
Imports System
Imports System.Globalization
Imports System.Threading
Imports System.Windows
Imports System.Collections
Imports System.Drawing
'Les imports pour la librairie des graphes(QuickGraph)
Imports QuickGraph
Imports Algo_Extension = QuickGraph.Algorithms.AlgorithmExtensions
Imports Algo_PredObservSommetEnreg = QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver(Of String, QuickGraph.Edge(Of String))
Imports Algo_PredObservArcEnreg = QuickGraph.Algorithms.Observers.EdgeRecorderObserver(Of String, QuickGraph.Edge(Of String))
Imports Algo_SommetDistObservEnreg = QuickGraph.Algorithms.Observers.VertexDistanceRecorderObserver(Of String, QuickGraph.Edge(Of String))
Imports DJISKRA = QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm(Of String, QuickGraph.Edge(Of String))
Imports InterfaceVB ' fichier interfaceVB pour ma classe Lien
'----------------------------------------------------------
Public Class frmDjiskra
'objets pour traiter les liens lus dans ms excel
'--------------------------------------------------
Public listeLiens As List(Of Lien) = New List(Of Lien)
Public objLien As Lien
'objet graphe d'adjacence simple
Dim objGraph As AdjacencyGraph(Of String, Edge(Of String))
' objet un lien du graphe
Dim lienGraphe As QuickGraph.Edge(Of String)
'objet "cout d'un lien" de type Dictionnaire (lienGraphe,Cout)
Dim coutLien As Dictionary(Of Edge(Of String), Double)
'objet delegue "fonction cout lien" (methode helper bibliotheque)
Dim FNCout As Func(Of Edge(Of String), Double)
' partie Algo Djiskra
'------------------------------------
' objet Algorithme "Djiskra"
Dim objDjiskra As DJISKRA
' objet "Observateur Sommet" (chemin d'exploration sommet)
Dim predObservSommet As Algo_PredObservSommetEnreg = _
New Algo_PredObservSommetEnreg()
'objet "Observateur Arc" (chemin d'exploration arc)
Dim predObservLien As Algo_PredObservArcEnreg = _
New Algo_PredObservArcEnreg()
' objet "Observateur Distance" (longueur du chemin explore)
Dim distObserver As Algo_SommetDistObservEnreg
'chargement des donnees , j'utilise une liste et une classe lien (arc) auxiliaire
'cest plus facile ,je lis fichier excel et stocke dans
' classe lien (arcs+couts)+une listeLien
' parcourt liste et affecte au graphe.
'remplit le graphe avec les donnes liens
Private Sub RemplitGraphe()
objGraph = New AdjacencyGraph(Of String, Edge(Of String))
coutLien = New Dictionary(Of Edge(Of String), Double)(objGraph.EdgeCount)
'parcourt liste des liens
For Each objLien As Lien In listeLiens
'Ajoute Sommets et Liens au graphe
lienGraphe = New QuickGraph.Edge(Of String)(objLien.sommetNom, objLien.sommetLien)
objGraph.AddVerticesAndEdge(lienGraphe)
'Ajoute "le fameux cout du lien" au Dictionnaire "Cout Lien"
' fameux dico à.les couts sont dans objLien.cout de ma classe liens
coutLien.Add(lienGraphe, Double.Parse(objLien.Cout))
Next
'Assigne dictionnaire "CoutLien" à la fonction delegue "helper edgeCost"
FNCout = Algo_Extension.GetIndexer(coutLien)
End Sub
' lance Djiskra
Private Sub demarreDjiskra()
'Initialise Algo DJISKRA
objDjiskra = New DJISKRA(objGraph, FNCout)
'Attache les observateurs sommet et lien
predObservSommet.Attach(objDjiskra)
predObservLien.Attach(objDjiskra)
'Attache l'observateur cout du chemin
distObserver = New Algo_SommetDistObservEnreg(Algo_Extension.GetIndexer(coutLien))
distObserver.Attach(objDjiskra)
'Execute Algo "DJISKRA" avec noeud "Source" comme Racine
objDjiskra.Compute("SOURCE")
'Affiche liste Noeuds et Arcs du Chemin DJISKRA dans TextBox
Call AfficheCheminVisite(objDjiskra)
End Sub
'affiche le chemin visite dans TexBox.
Private Sub AfficheCheminVisite(ByVal objDjiskra As DJISKRA)
'compte noeuds et arcs du "graphe visite"
TextBox1.ForeColor = System.Drawing.Color.DarkOliveGreen
TextBox1.Font = New Font("courier new", 10, FontStyle.Bold)
TextBox1.Text = "nombre Noeuds :" & (predObservSommet.VertexPredecessors.Count + 1).ToString & vbCrLf & vbCrLf
TextBox1.Text = TextBox1.Text & "nombre Arcs :" & (predObservLien.Edges.Count).ToString & vbCrLf & vbCrLf
'chemin
For Each objKVP As KeyValuePair(Of String, Edge(Of String)) In
predObservSommet.VertexPredecessors
txtChemin.Text = txtChemin.Text & objKVP.Key & " -" &
objKVP.Value.ToString & vbCrLf
Next
'TryGetDistance pour avoir le cout de "root a chaque sommet"
' car l'algo implemente variante de arbre des plus courts chemins
Dim coutChemin As Double = 0.0
For Each objSommet In predObservSommet.VertexPredecessors
objDjiskra.TryGetDistance(objSommet.Key, coutChemin)
txtCoutChemin.Text = txtCoutChemin.Text & objSommet.Key & " -" & coutChemin.ToString & vbCrLf
Next
End Sub
'projet Classe Lien
'------------------
'classe Arc sert à stocker les liens(arcs) avec cout du fichier excel
Public Class Lien
Public sommetNom, sommetLien As String
Public Description, monType As String
Public Cout As Double
Public Sub New()
Me.sommetNom = ""
Me.sommetLien = ""
Me.Description = "Neant"
Me.Cout = 0.0
Me.monType = ""
End Sub
End Class |
