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
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
|
'projet principal frmFloydWarshal
'--------------------------
'1 AJOUT REFERENCE À :
'- QuickGraph.dll , QuickGraph.Glee.dll
'- Microsot Excel 11.0 Object Library(office 2003) ou bien
'- Microsot Excel 12.0 Object Library(office 2007)
'2 AJOUT CONTROLES :
'- 2 TextBox(pour resultats),1 Button(pour ouvrir classeur)
'3 GENERATION DU PROJET:
'- dans projet frmFloydWarshal ajouter reference->projets>InterFacevb->0k
'6- GENERER LA SOLUTION
Option Explicit On
Option Compare Text
Imports System
Imports System.Globalization
Imports System.Threading
Imports System.Windows
Imports System.Collections
Imports System.Drawing
'imports pour MS Office Excel 2003
Imports Microsoft.Office.Interop
'imports pour la librairie des graphes(QuickGraph)
Imports QuickGraph
Imports Algo_Extension = QuickGraph.Algorithms.AlgorithmExtensions
Imports FLOYDWARSHAL = QuickGraph.Algorithms.ShortestPath.FloydWarshallAllShortestPathAlgorithm(Of String, QuickGraph.Edge(Of String))
'imports pour les methodes d'extensions
Imports QuickGraph.Glee
'imports pour projet interfaceVB(classes Lien )
Imports InterfaceVB
Public Class frmFloydWarshal
'objets donnees liens de MS Excel
'--------------------------------------------------
Public listeLiens As List(Of Lien) = New List(Of Lien)
Public objLien As Lien
'Lib QuickGraph (Partie graphe)
'------------------------------
'objet public graphe d'adjacence simple
Public 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 d'aide bibliotheque)
Dim FNCout As Func(Of Edge(Of String), Double)
' objet Algorithme "FloydWarshal"
Public objFloydWarshall As FLOYDWARSHAL
'Objet classeur MS Excel 2003
'----------------------------
Dim appExcel As Excel.Application
Public Sub New()
' Cet appel est requis par le Concepteur Windows Form.
InitializeComponent()
' Ajoutez une initialisation quelconque après l'appel InitializeComponent()
End Sub
'Recherche le fichier excel contenant les arcs du graphe
Private Sub btnOuvreFichArcs_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnOuvreFichLiens.Click
Dim nomFichierLiens As String = ""
Dim dlgOuvreFichier As OpenFileDialog = New OpenFileDialog
dlgOuvreFichier.Filter = "Fichier Arcs(*.xls)|*.xls"
If dlgOuvreFichier.ShowDialog = Forms.DialogResult.OK Then
nomFichierLiens = dlgOuvreFichier.FileName
If Len(nomFichierLiens) = 0 Then
MessageBox.Show("entrer un nom de fichier svp...")
Exit Sub
Else
'Si fichier excel trouve
Call LitFichierGraphe(nomFichierLiens)
Call RemplitGraphe()
Call demarreFloydWarshal()
End If
End If
End Sub
'Lit le fichier excel et charge liens(arcs) du graphe
Private Sub LitFichierGraphe(ByVal nomFichierLiens As String)
Dim nbLig As Integer = 12 'limite à 12 lignes
Dim nbCol As Integer = 5 'limite à 5 colonnes
'ferme toute application excel en cours
If appExcel IsNot Nothing Then
appExcel.Quit()
End If
Try
Dim appExcel As Excel.Application = New Excel.Application
appExcel.Visible = True
Dim monClasseur As Excel.Workbook = appExcel.Workbooks.Open(nomFichierLiens)
Dim maFeuille As Excel.Worksheet = monClasseur.Worksheets(1)
For I As Integer = 2 To nbLig
objLien = New Lien
For J As Integer = 1 To nbCol
Select Case J
Case 1
objLien.sommetNom = CType(maFeuille.Cells(I, J).value, String)
Case 2
objLien.Description = CType(maFeuille.Cells(I, J).value, String)
Case 3
objLien.sommetLien = CType(maFeuille.Cells(I, J).value, String)
Case 4
objLien.Cout = CType(maFeuille.Cells(I, J).value, Double)
Case 5
objLien.monType = CType(maFeuille.Cells(I, J).value, String)
End Select
Next
'ajout à liste liens
listeLiens.Add(objLien)
Next
Catch ex As Exception
MessageBox.Show(ex.Message)
If appExcel IsNot Nothing Then
appExcel.Quit()
End If
End Try
End Sub
'Remplit(populate) le graphe avec les donnes liens
Private Sub RemplitGraphe()
'parcourt liste des liens
'Ajoute Sommets et Liens au graphe
objGraph = New AdjacencyGraph(Of String, Edge(Of String))
coutLien = New Dictionary(Of Edge(Of String), Double)(objGraph.EdgeCount)
For Each objLien As Lien In listeLiens
lienGraphe = New QuickGraph.Edge(Of String)(objLien.sommetNom, objLien.sommetLien)
objGraph.AddVerticesAndEdge(lienGraphe)
'Ajoute "le cout du lien" au Dictionnaire "Cout Lien"
coutLien.Add(lienGraphe, Double.Parse(objLien.Cout))
Next
'Assigne à la fonction "FNCout" delegue
'le dictionnaire "CoutLien"
FNCout = Algo_Extension.GetIndexer(coutLien)
End Sub
'executeFloydWarshal
Private Sub demarreFloydWarshal()
'Initialise Algo FLOYDWARSHAL
objFloydWarshall = New FLOYDWARSHAL(objGraph, FNCout)
'Execute Algo "FLOYDWARSHALL"
objFloydWarshall.Compute()
'Affiche les chemins et couts dans TextBox
Call AfficheChemin()
End Sub
'Affiche les chemins et couts dans TextBox.
Private Sub AfficheChemin()
txtListeSommet.ForeColor = System.Drawing.Color.DarkOliveGreen
txtListeSommet.Font = New Font("courier new", 10, FontStyle.Bold)
'compte sommets(ou noeuds) du "graphe "
txtListeSommet.Text = "nombre Sommets :" & objGraph.Vertices.Count.ToString & vbCrLf & vbCrLf
'compte liens (ou arcs) du "graphe "
txtListeSommet.Text = txtListeSommet.Text & "nombre Liens :" & objGraph.Edges.Count.ToString & vbCrLf & vbCrLf
'Retrouve le cout chemin avec fonction TryGetDistance
'Retrouve les liens chemin avec fonction TryGetPath
txtChemin.Text = ""
Dim objCoutChemin As Double = 0.0
Dim objChemin As IEnumerable(Of QuickGraph.Edge(Of String)) = Nothing
For Each objSource In objGraph.Vertices
For Each objDestination In objGraph.Vertices
's'il ya un chemin entre Source et Destination
'liste le nom chemin et cout
If objFloydWarshall.TryGetDistance(objSource, objDestination, objCoutChemin) Then
txtChemin.Text = txtChemin.Text & _
"chemin de : " & objSource & " -> " & objDestination & " Cout: " & objCoutChemin.ToString & vbCrLf
End If
'liste les liens du chemin
If objFloydWarshall.TryGetPath(objSource, objDestination, objChemin) Then
For Each objLienGraphe In objChemin
txtChemin.Text = txtChemin.Text & objLienGraphe.Source & " -" & objLienGraphe.Target & vbCrLf
Next
End If
txtChemin.Text = txtChemin.Text & " --------- " & vbCrLf
Next 'au chemin suivant
Next
End Sub
End Class
'projet InterFacevb contient la Classe Lien
'------------------
'classe Lien sert à stocker les liens(arcs) du fichier excel
Public Class Lien
Public sommetNom, sommetLien As String
Public Description, monType As String
Public Cout As Double ' quickgraph n'accepte le type integer
Public Sub New()
Me.sommetNom = ""
Me.sommetLien = ""
Me.Description = "Neant"
Me.Cout = 0.0
Me.monType = ""
End Sub
End Class |
