QuickGraph Dijkstraの例

Question

私はAlgorithmExtensions.ShortestPathsDijkstraを実行したいですが、QuickGraphのドキュメントは最適ではありません。AdjacencyGraph<string, Edge<string>>です。

誰でも私が従うことができる例はありますか？

私がGoogleで見つけたものはすべて、AlgorithmExtensionには必要のないオブザーバを使用していました。

Answer 1

私はドキュメントを更新しましたが、要約すると、グラフ、エッジウェイトマップ（デリゲートとして）、ルートの頂点が必要です。 AlgorithmExtensionsメソッドは、最短パスを取得するためにクエリできる「TryFunc」を返します。ここで

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

例は、QuickGraphでDijkstra's Algorithmを実行しているときにquickgraph.codeplex.comから取ったものです。

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

は、別のサンプル（これはLinqPadで実行 - F4に必ずとQuickGraph DLLへの参照を追加）だはい、私はこれを見てきました

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