Discussion :

[nikita_4]

Bonjour,

je commence à l'utilisation de la library QuickGraph pour l'implémentation des algorithmes de la théorie des graphes sur mon réseau que j'ai sous la forme d'un fichier en format GraphML,
jusqu'à maintenait j'ai pu utiliser quelques algorithmes comme celui de Dijkstra, mais cela en fixant la source du graphe et ca me donne après les plus cours chemins des nœuds lié à la source.

Le problème que j'ai mnt, c'est comment je peux fixer le nœud de destination sur mon programme et aussi comment je peux prendre en considération le cout (que j'ai définie sur le fichier GraphML)de chaque vecteur ?

Voici une partie de mon code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
            //lecture du fichier GRAPHML
            var g = new BidirectionalGraph<int, Edge<int>>();
            using (var xreader = XmlReader.Create(@"C:\GraphML\test2.graphml"))
                g.DeserializeFromGraphML(xreader,
                    id => int.Parse(id),
                    (source, target, id) => new Edge<int>(source, target)
                );
 
 
            int root = 68; // Le numéro du noeud source definie dans le fichier GraphML
 
            Func<Edge<int>, double> edgeCost1 = b => 1; // Le cout definie comme constante
 
            var predecessors = new VertexPredecessorRecorderObserver<int, Edge<int>>();
 
 
            // utilisation de Dijkstra sur le graphe
            DijkstraShortestPathAlgorithm<int, Edge<int>> dijkstra1 = new DijkstraShortestPathAlgorithm<int, Edge<int>>(g, edgeCost1);
 
            //joindre un observateur de distance qui nous donne les distances du plus court chemin
            VertexDistanceRecorderObserver<int, Edge<int>> distObserver1 = new VertexDistanceRecorderObserver<int, Edge<int>>(edgeCost1);
            distObserver1.Attach(dijkstra1);
 
            //joindre un "VertexPredecessorRecorderObserver" qui fournis les chemins
            VertexPredecessorRecorderObserver<int, Edge<int>> predecessorObserver1 = new VertexPredecessorRecorderObserver<int, Edge<int>>();
            predecessorObserver1.Attach(dijkstra1);
 
            // On execute l'algorithme, on specifie le noeud source
            dijkstra1.Compute(root);
 
            foreach (KeyValuePair<int, double> kvp in distObserver1.Distances)
                 Console.WriteLine("Distance de la source jusqu'à le noeud {0} est {1}", kvp.Key, kvp.Value);
             foreach (KeyValuePair<int, Edge<int>> kvp in predecessorObserver1.VertexPredecessors)
                 Console.WriteLine("Pour aller au noeud {0} il faut passer par le vecteur {1}", kvp.Key, kvp.Value);

Merci.

[MABROUKI]

bonjour moi j'utilise l'api en vb.net ,j'ai du traduire car je suis refractaire à c++et c#,a cause des tildes et des ;

voila tu dois avoir avoir d'abord assigner les couts reels dans un dictionnaire en double c'est si necessaire comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

tu peux utiliser l'interactivite en entrant la "racine" a chaque lancement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
        objDjiskra.ClearRootVertex
        '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")

Si tu veux l'algo plus court chemin entre 2 sommets il me semble que ca doit se trouver peut etre dans ceci . QuickGraph.Algorithms.ShortestPath.ShortestPathAlgorithmBase(Of String, QuickGraph.Edge(Of String)).

Mais laisse-moi le temps de voir.
J'ai utilise BFS,DFS,FloydWarshall(tous les plus courts chemins possibles dans un graphe oriente).
J'ai un post avec code source sur le forum que j'ai donne quelq'un.
J'utilise pour visualiser MSGLEE,MSAGL ....
bon code.......