IT:AD:NET:Libraries:QuickGraph:HowTo:WorkingSample [Notes]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# IT:AD:NET:Libraries:QuickGraph:HowTo:WorkingSample #



<callout type="Navigation" class="small">

* [[../|(UP)]]
{{indexmenu>.#2|nsort tsort}}


</callout>


<panel title="Summary">

SOOOOO few examples.


</panel>


## Process ##

    Here is a fully worked sample in VS 2010 Express.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    using QuickGraph;
    using QuickGraph.Collections;
    using QuickGraph.Algorithms;
    using QuickGraph.Algorithms.ShortestPath;
    using QuickGraph.Algorithms.Observers;


    // Sample code for use of QuickGraph
    // Assembled from various code snippets found in discussions and documentation
    // thanks to those who posted
    // Needs QuickGraph dll
    // Add reference to QuickGraph
    // R. Males 2012

    namespace QuickGraphTest
    {
        class QuickGraphSimpleTest1
        {
            static void Main(string[] args)
            {

                // use simple adjacency graph
                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 (<string> -> the edge is identified by a string value)

                Edge<string> a_e = new Edge<string>("A", "E");
                Edge<string> e_f = new Edge<string>("E", "F");
                Edge<string> f_g = new Edge<string>("F", "G");
                Edge<string> g_h = new Edge<string>("G", "H");

                Edge<string> a_b = new Edge<string>("A", "B");
                Edge<string> b_c = new Edge<string>("B", "C");
                Edge<string> c_d = new Edge<string>("C", "D");
                Edge<string> d_e = new Edge<string>("D", "E");
                Edge<string> e_h = new Edge<string>("E", "H");
                Edge<string> h_i = new Edge<string>("H", "I");
                Edge<string> i_j = new Edge<string>("I", "J");
                Edge<string> j_a = new Edge<string>("J", "A");

                // Add the edges
                graph.AddEdge(a_e);
                graph.AddEdge(e_f);
                graph.AddEdge(f_g);
                graph.AddEdge(g_h);

                graph.AddEdge(a_b);
                graph.AddEdge(b_c);
                graph.AddEdge(c_d);
                graph.AddEdge(d_e);
                graph.AddEdge(e_h);
                graph.AddEdge(h_i);
                graph.AddEdge(i_j);
                graph.AddEdge(j_a);

                Console.WriteLine("\nGraph Edges\n");

                foreach (var vertex in graph.Vertices)
                    foreach (var edge in graph.OutEdges(vertex))
                        Console.WriteLine(edge);

                // Define some lengths to the edges

                Dictionary<Edge<string>, double> edgeCost = new Dictionary<Edge<string>, double>(graph.EdgeCount);
                edgeCost.Add(a_e, 1);
                edgeCost.Add(e_f, 1);
                edgeCost.Add(f_g, 1);
                edgeCost.Add(g_h, 1);
                edgeCost.Add(a_b, 1);

                edgeCost.Add(b_c, 1);
                edgeCost.Add(c_d, 2);
                edgeCost.Add(d_e, 3);
                edgeCost.Add(e_h, 4);
                edgeCost.Add(h_i, 1);
                edgeCost.Add(i_j, 2);
                edgeCost.Add(j_a, 3);

                Console.WriteLine("\nEdge Costs\n");

                foreach (var x in edgeCost)
                    Console.WriteLine("Edge {0} Cost {1}", x.Key, x.Value);



                // use Dijkstra shortest path algorithm.   Note passing the edge cost dictionary

                DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));

                // creating some observers to get output after the computation

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

                // add a path recorder observer
                QuickGraph.Algorithms.Observers.VertexPredecessorPathRecorderObserver<string, Edge<string>> predecessorPathRecorderObserver = new QuickGraph.Algorithms.Observers.VertexPredecessorPathRecorderObserver<string, Edge<string>>();
                predecessorPathRecorderObserver.Attach(dijkstra);

                // and another observer

                VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
                distObserver.Attach(dijkstra);


                // compute paths from vertex A
                dijkstra.Compute("A");

                // report out what the observers contain, just to see what they do

                Console.WriteLine("\nPredecessor Observer\n");

                foreach (var z in predecessorObserver.VertexPredecessors)
                {

                    Console.WriteLine(" Vertex Predecessor key:{0} value:{1}", z.Key, z.Value);
                }

                Console.WriteLine("\nPath Recorder Observer\n");

                foreach (var xx in predecessorPathRecorderObserver.VertexPredecessors)
                {
                    Console.WriteLine(" EndPathVertices {0} ", xx.ToString());
                }


                Console.WriteLine("\nDistance Observer\n");

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


                // get path from root to node I, working backwards, using the predecessor observer

                // note that total costs for path should agree with those above from distance observer

                Console.WriteLine("\nShow Path and Cost\n");

                IEnumerable<Edge<string>> outpath;

                foreach (var endVertex in graph.Vertices)
                {
                    Console.WriteLine("\nPath to End Vertex {0}\n", endVertex);

                    bool validPath = predecessorObserver.TryGetPath(endVertex, out outpath);

                    if (validPath)
                    {
                        int pathCount = 0;
                        double totalPathCost = 0.0;
                        double costForEdge;
                        Console.WriteLine(" ");
                        foreach (var zzz in outpath)
                        {
                            edgeCost.TryGetValue(zzz, out costForEdge);
                            totalPathCost += costForEdge;
                            Console.WriteLine("\tStep {0} {1} edge cost {2} total path cost {3}", pathCount++, zzz.ToString(), costForEdge, totalPathCost);


                        }
                    }
                }
                Console.WriteLine("Press <ENTER> to complete");
                Console.ReadKey();

            }
        }

    }


    and the output is as follows:

     

     

    Graph Edges

    A->E
    A->B
    B->C
    C->D
    D->E
    E->F
    E->H
    F->G
    G->H
    H->I
    I->J
    J->A

    Edge Costs

    Edge A->E Cost 1
    Edge E->F Cost 1
    Edge F->G Cost 1
    Edge G->H Cost 1
    Edge A->B Cost 1
    Edge B->C Cost 1
    Edge C->D Cost 2
    Edge D->E Cost 3
    Edge E->H Cost 4
    Edge H->I Cost 1
    Edge I->J Cost 2
    Edge J->A Cost 3

    Predecessor Observer

     Vertex Predecessor key:E value:A->E
     Vertex Predecessor key:B value:A->B
     Vertex Predecessor key:F value:E->F
     Vertex Predecessor key:H value:G->H
     Vertex Predecessor key:C value:B->C
     Vertex Predecessor key:G value:F->G
     Vertex Predecessor key:D value:C->D
     Vertex Predecessor key:I value:H->I
     Vertex Predecessor key:J value:I->J

    Path Recorder Observer

     EndPathVertices [E, A->E]
     EndPathVertices [B, A->B]
     EndPathVertices [F, E->F]
     EndPathVertices [H, G->H]
     EndPathVertices [C, B->C]
     EndPathVertices [G, F->G]
     EndPathVertices [D, C->D]
     EndPathVertices [I, H->I]
     EndPathVertices [J, I->J]

    Distance Observer

    Distance from root to node A is 0
    Distance from root to node E is 1
    Distance from root to node B is 1
    Distance from root to node F is 2
    Distance from root to node H is 4
    Distance from root to node C is 2
    Distance from root to node G is 3
    Distance from root to node D is 4
    Distance from root to node I is 5
    Distance from root to node J is 7

    Show Path and Cost


    Path to End Vertex A


    Path to End Vertex B


            Step 0 A->B edge cost 1 total path cost 1

    Path to End Vertex C


            Step 0 A->B edge cost 1 total path cost 1
            Step 1 B->C edge cost 1 total path cost 2

    Path to End Vertex D


            Step 0 A->B edge cost 1 total path cost 1
            Step 1 B->C edge cost 1 total path cost 2
            Step 2 C->D edge cost 2 total path cost 4

    Path to End Vertex E


            Step 0 A->E edge cost 1 total path cost 1

    Path to End Vertex F


            Step 0 A->E edge cost 1 total path cost 1
            Step 1 E->F edge cost 1 total path cost 2

    Path to End Vertex G


            Step 0 A->E edge cost 1 total path cost 1
            Step 1 E->F edge cost 1 total path cost 2
            Step 2 F->G edge cost 1 total path cost 3

    Path to End Vertex H


            Step 0 A->E edge cost 1 total path cost 1
            Step 1 E->F edge cost 1 total path cost 2
            Step 2 F->G edge cost 1 total path cost 3
            Step 3 G->H edge cost 1 total path cost 4

    Path to End Vertex I


            Step 0 A->E edge cost 1 total path cost 1
            Step 1 E->F edge cost 1 total path cost 2
            Step 2 F->G edge cost 1 total path cost 3
            Step 3 G->H edge cost 1 total path cost 4
            Step 4 H->I edge cost 1 total path cost 5

    Path to End Vertex J


            Step 0 A->E edge cost 1 total path cost 1
            Step 1 E->F edge cost 1 total path cost 2
            Step 2 F->G edge cost 1 total path cost 3
            Step 3 G->H edge cost 1 total path cost 4
            Step 4 H->I edge cost 1 total path cost 5
            Step 5 I->J edge cost 2 total path cost 7
    Press <ENTER> to complete

## Resources ##


http://quickgraph.codeplex.com/discussions/283972