QuickGraph Dijkstra Beispiel

Question

Ich habe eine AdjacencyGraph<string, Edge<string>>, die ich gerne AlgorithmExtensions.ShortestPathsDijkstra ausführen würde, aber die QuickGraph Dokumentation ist nicht die beste.

Hat jemand ein Beispiel, dem ich folgen kann?

Alles, was ich bei Google gefunden habe, verwendete einen Beobachter, den die AlgorithmExtension nicht benötigt.

Answer 1

Ich habe die Dokumentation aktualisiert, aber auf den Punkt gebracht, benötigen Sie ein Diagramm, ein Kantengewicht Karte (als Delegierter) und einen Wurzelknoten. Die AlgorithmExtensions-Methode gibt eine "TryFunc" zurück, die Sie abfragen können, um die kürzesten Pfade abzurufen.

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

Beispiel aus quickgraph.codeplex.com zum Ausführen von Dijkstra-Algorithmus auf einem 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

Hier ist ein weiteres Beispiel (das in LinqPad läuft - bis F4 sicher sein, und einen Verweis auf die QuickGraph dll hinzufügen)

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; 
}