Why no samples and only partial code?

Topics: algorithm
Dec 23, 2011 at 4:39 AM

I am very interested in using this library, but have spent a good deal of time struggling with first obtaining it, then attempting to learn and use it.  There seem to be many requests on this discussion forum for complete samples, which go unanswered.   Most of the code posted, when there is a reply, is not complete.  Is there a particular reason and philosophy for not providing fully worked simple examples for those of us who are beginners and operate best from such a starting point?  Am I missing the location of some library of examples?

Thanks.

R. Males

Cincinnati, Ohio, USA

Dec 23, 2011 at 9:11 AM

This is obviously something for the author to answer.

My guess is that QuickGraph has always been a side project.

I doubt the author was ever paid to work on it, or anybody else.

It is up to us to provide any missing bits (code, documentation, any other form of help).

This is true for many other open source projects.

Dec 23, 2011 at 3:02 PM

I agree, and should I ever get a simple solution working in my environment (Visual Studio 2010 Express), I will post it, together with an explanation.

 

Dick

Feb 7, 2012 at 2:21 PM

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

Feb 22, 2013 at 6:04 PM
Thanks they are really helpful examples.

For a mere mortal line of business developer like myself this library looks very promising but it's a huge learning curve.

Once I've got my head around everything, I may join in the phone do some getting started guides as well.

Thanks again.