Exemple QuickGraph Dijkstra

Question

J'ai un AdjacencyGraph<string, Edge<string>> sur lequel j'aimerais lancer AlgorithmExtensions.ShortestPathsDijkstra, mais la documentation QuickGraph n'est pas la meilleure.

Est-ce que quelqu'un a un exemple que je peux suivre? Tout ce que j'ai trouvé sur Google a utilisé un observateur, dont AlgorithmExtension ne nécessite pas.

Answer 1

J'ai mis à jour la documentation, mais en un mot, vous avez besoin d'un graphique, une carte de poids de bord (en tant que délégué) et un sommet racine. La méthode AlgorithmExtensions renvoie un 'TryFunc' que vous pouvez interroger pour récupérer les chemins les plus courts.

using QuickGraph; 
using QuickGraph.Algorithms; 

IVertexAndEdgeListGraph<TVertex, TEdge> graph = ...; 
Func<TEdge, double> edgeCost = e => 1; // constant cost 
TVertex root = ...; 

// compute shortest paths 
TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root); 

// query path for given vertices 
TVertex target = ...; 
IEnumerable<TEdge> path; 
if (tryGetPaths(target, out path)) 
    foreach(var edge in path) 
     Console.WriteLine(edge); 

Answer 2

Exemple tiré de quickgraph.codeplex.com sur l'exécution de l'algorithme de Dijkstra sur un QuickGraph.

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true); 

// Add some vertices to the graph 
graph.AddVertex("A"); 
graph.AddVertex("B"); 
graph.AddVertex("C"); 
graph.AddVertex("D"); 
graph.AddVertex("E"); 
graph.AddVertex("F"); 
graph.AddVertex("G"); 
graph.AddVertex("H"); 
graph.AddVertex("I"); 
graph.AddVertex("J"); 

// Create the edges 
Edge<string> a_b = new Edge<string>("A", "B"); 
Edge<string> a_d = new Edge<string>("A", "D"); 
Edge<string> b_a = new Edge<string>("B", "A"); 
Edge<string> b_c = new Edge<string>("B", "C"); 
Edge<string> b_e = new Edge<string>("B", "E"); 
Edge<string> c_b = new Edge<string>("C", "B"); 
Edge<string> c_f = new Edge<string>("C", "F"); 
Edge<string> c_j = new Edge<string>("C", "J"); 
Edge<string> d_e = new Edge<string>("D", "E"); 
Edge<string> d_g = new Edge<string>("D", "G"); 
Edge<string> e_d = new Edge<string>("E", "D"); 
Edge<string> e_f = new Edge<string>("E", "F"); 
Edge<string> e_h = new Edge<string>("E", "H"); 
Edge<string> f_i = new Edge<string>("F", "I"); 
Edge<string> f_j = new Edge<string>("F", "J"); 
Edge<string> g_d = new Edge<string>("G", "D"); 
Edge<string> g_h = new Edge<string>("G", "H"); 
Edge<string> h_g = new Edge<string>("H", "G"); 
Edge<string> h_i = new Edge<string>("H", "I"); 
Edge<string> i_f = new Edge<string>("I", "F"); 
Edge<string> i_j = new Edge<string>("I", "J"); 
Edge<string> i_h = new Edge<string>("I", "H"); 
Edge<string> j_f = new Edge<string>("J", "F"); 

// Add the edges 
graph.AddEdge(a_b); 
graph.AddEdge(a_d); 
graph.AddEdge(b_a); 
graph.AddEdge(b_c); 
graph.AddEdge(b_e); 
graph.AddEdge(c_b); 
graph.AddEdge(c_f); 
graph.AddEdge(c_j); 
graph.AddEdge(d_e); 
graph.AddEdge(d_g); 
graph.AddEdge(e_d); 
graph.AddEdge(e_f); 
graph.AddEdge(e_h); 
graph.AddEdge(f_i); 
graph.AddEdge(f_j); 
graph.AddEdge(g_d); 
graph.AddEdge(g_h); 
graph.AddEdge(h_g); 
graph.AddEdge(h_i); 
graph.AddEdge(i_f); 
graph.AddEdge(i_h); 
graph.AddEdge(i_j); 
graph.AddEdge(j_f); 

// Define some weights to the edges 
Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount); 
edgeCost.Add(a_b, 4); 
edgeCost.Add(a_d, 1); 
edgeCost.Add(b_a, 74); 
edgeCost.Add(b_c, 2); 
edgeCost.Add(b_e, 12); 
edgeCost.Add(c_b, 12); 
edgeCost.Add(c_f, 74); 
edgeCost.Add(c_j, 12); 
edgeCost.Add(d_e, 32); 
edgeCost.Add(d_g, 22); 
edgeCost.Add(e_d, 66); 
edgeCost.Add(e_f, 76); 
edgeCost.Add(e_h, 33); 
edgeCost.Add(f_i, 11); 
edgeCost.Add(f_j, 21); 
edgeCost.Add(g_d, 12); 
edgeCost.Add(g_h, 10); 
edgeCost.Add(h_g, 2); 
edgeCost.Add(h_i, 72); 
edgeCost.Add(i_f, 31); 
edgeCost.Add(i_h, 18); 
edgeCost.Add(i_j, 7); 
edgeCost.Add(j_f, 8); 

// We want to use Dijkstra on this graph 
DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost); 

// attach a distance observer to give us the shortest path distances 
VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(); 
distObserver.Attach(dijkstra); 

// Attach a Vertex Predecessor Recorder Observer to give us the paths 
VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>(); 
predecessorObserver.Attach(dijkstra); 

// Run the algorithm with A set to be the source 
dijkstra.Compute("A"); 

foreach (KeyValuePair<string, int> kvp in distObserver.Distances) 
Console.WriteLine("Distance from root to node {0} is {1}", kvp.Key, kvp.Value); 

foreach(KeyValuePair<string, Edge<string>> kvp in predecessorObserver.VertexPredecessors) 
Console.WriteLine("If you want to get to {0} you have to enter through the in edge {1}", kvp.Key, kvp.Value); 

// Remember to detach the observers 
distObserver.Detach(dijkstra); 
predecessorObserver.Detach(dijkstra); 

Answer 3

Voici un autre exemple (cela va dans LINQPad - assurez-vous de F4 et ajouter une référence à la dll QuickGraph)

void Main() 
{ 
    const int nNodes = 10; 
    var graphAsDict = RandomGraphWithSelfEdgeAsDict(nNodes).Dump("graphAsDict: Random graph as Dict"); 

    var velg1 = graphAsDict.ToVertexAndEdgeListGraph(
     kv => Array.ConvertAll<int, SEquatableEdge<int>>(
      kv.Value.ToArray(), 
      v => new SEquatableEdge<int>(kv.Key, v))).Dump("velg1: Vertex and Edge-List Graph"); 

    Func<SEquatableEdge<int>, double> edgeCost = (edge => 1.0D); 

    int start = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("start point"); 
    int end = new Random(Guid.NewGuid().GetHashCode()).Next(1, nNodes + 1).Dump("end point"); 

    var algo = new DijkstraShortestPathAlgorithm<int, SEquatableEdge<int>>(velg1, edgeCost); 
    var predecessors = new VertexPredecessorRecorderObserver<int, SEquatableEdge<int>>(); 
    using (predecessors.Attach(algo)) 
    { 
     algo.Compute(start); 
     IEnumerable<SEquatableEdge<int>> path; 
     if (predecessors.TryGetPath(end, out path).Dump("TryGetPath")) 
      path.Dump("path"); 
    } 
} 

public static int[] RandomPermutation(Random ran, int n) 
{ 
    var r = Enumerable.Range(1, n).ToArray(); 
    for (var i = 0; i < n - 1; i++) 
    { 
     var k = ran.Next(i + 1, n); 
     var t = r[i]; 
     r[i] = r[k]; 
     r[k] = t; 
    } 
    return r; 
} 

public static Dictionary<int, IEnumerable<int>> 
RandomGraphWithSelfEdgeAsDict(int nNodes) 
{ 
    var ran = new Random(Guid.NewGuid().GetHashCode()); 
    var result = new Dictionary<int, IEnumerable<int>>(); 

    for (var j = 1; j <= nNodes; j++) 
    { 
     var k = ran.Next(0, nNodes); 
     var cs = RandomPermutation(ran, nNodes); 
     result[j] = cs.Take(k); 
    } 

    return result; 
}