c# - QuickGraph ダイクストラの例

Question

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

誰かが私に従うことができる例を持っていますか?

私が 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 のアルゴリズムを実行するときの例は、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;
}