Output from Dijkstra Algorithm

Topics: algorithm, graph
Jul 17, 2007 at 10:09 AM
I am just testing the quickgraph library and am trying to figure out how to:
a) Create a graph
b) Populate the graph
c) Visualize the graph
d) Run Dijkstra on the graph
e) Check the results from Dijkstra

I was able to get through a-d(though still struggling a bit with c), but is really having a hard time figuring out how to get the results from the Dijkstra Algorithm.

Can someone please post an example showing how to handle output from the Dijkstra algorithm.

Do I need to hook up to some of the eventhandlers? If that is the way to do it, It am wondering how to interpret and store the results.

Thanks
Allan
Coordinator
Jul 17, 2007 at 4:22 PM
You need to attach 'observers' to the algorithm before execution (see VertexPredecessorRecorderObserver). There are different types of observers to build a parent vertex map, distance map, etc...

The algorithm themselves don't do anything besides triggering events.
Jul 18, 2007 at 1:03 AM
I have created the graph from the example found in the Dijkstra applet
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

Heres is the code. Maybe someone will find it usefull when they start of with 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);
Jul 18, 2007 at 1:18 AM
And based on the above code I have a few more questions.

a)
I find it a bit tedious to have to save all the edge instances and assign them names(ie. a_b) in order to construct the weights Dictionary that requires an edge reference as key.

I only found an enumerator for the edges in the Adjecency graph, but no indexer. Hence there is no obvious way to access the edges without having a reference to it in the code. Did I miss something or can the weights be constructed in a less tedious way?

b)
Could you please explain the output from the code above?
Distance from root to node A is 0
Distance from root to node B is 0
Distance from root to node D is 0
Distance from root to node C is 0
Distance from root to node E is 0
Distance from root to node G is 0
Distance from root to node F is 1
Distance from root to node J is 0
Distance from root to node H is 1
Distance from root to node I is 0
If you want to get to B you have to enter through the in edge A->B
If you want to get to D you have to enter through the in edge A->D
If you want to get to C you have to enter through the in edge B->C
If you want to get to E you have to enter through the in edge B->E
If you want to get to G you have to enter through the in edge D->G
If you want to get to F you have to enter through the in edge J->F
If you want to get to J you have to enter through the in edge C->J
If you want to get to H you have to enter through the in edge G->H
If you want to get to I you have to enter through the in edge F->I

The vertex predecessors seems to aggree with the applet solution, but how do you interpret the distances? They are merely 0 and 1.

Sorry for the long posts and please have patience with me.
Allan
Coordinator
Jul 18, 2007 at 4:59 PM
a) refactor your code and write a method that adds the vertices if needed, create the edge and set the weight.
b) i need to take a second look
Jul 23, 2007 at 10:16 AM
After deleting a few of the solutions in the library I was able to compile the QuickGraph library. I wasn't able to find the GLEE reference files anywhere on the Internet, though?

Hoping to understand the 0 and 1's in my solution above I started debugging with Visual Studio. This turned out to be quite a task and I still haven't found usefull information.

Any help would be greatly appreciated.
Coordinator
Jul 23, 2007 at 5:36 PM
The GLEE link is in the wiki.
Jul 23, 2007 at 8:27 PM
Thanks a lot Pelikhan.

I found the GLEE link. I will try to compile the entire package when I learn more about the Dijkstra output. This is my main concern right now.

We are considering Quickgraph as the base for a prototype simulation in a project at the Technical University of Denmark. But obviously we also need to consider algorithmic correctness and performance.

Based upon your experience with boost and quickgraph, may I ask, if we should expect a significant decrease in performance compared to using the Boost C++ implementation. We will be deploying very large sparse graphs and will primarily need the Dijkstra Algorithm to run on these large graphs.

Allan
Coordinator
Jul 23, 2007 at 11:09 PM
You should expect decrease in performance, to what extend I am not sure. I don't know of anybody who actually used it for huge graphs.

- Boost is highly optimized/templated code, QuickGraph is managed (good sides, bad sides)
- Boost has a record of handling big graphs, QuickGraph has not,
- it has better a priority queue implementation (fibonaci queue) which should give better result out of Dijsktra - QuickGraph impl. is fairly naive, you will have to write your own.
Jul 30, 2007 at 11:10 AM
Learning that Quickgraph is not ported with the same optimizations as Boost "scared" us away for now. But keep up the good work Pelikhan. We hope that QuickGraph will one day offer state-of-the-art algorihms and implementations. For now it has been a good source of inspiration.

We have implemented our own graph environment and Dijkstra algorithm with a Priority Queue.

Allan
Coordinator
Jul 30, 2007 at 4:36 PM
Note that we've never tried to run benchmark to determine how 'bad' it is... QuickGraph let's you do graph in the managed environment: faster prototyping, garbage collection, better tools. Of course, there's no free lunch :)
Jul 30, 2007 at 6:22 PM
Working with QuickGraph in the managed C# environment feels like a steak dinner lunch compared to template programming with boost :-)

We have found sources, that used C# and they report that the "penalty" for using a managed environment is not significant as long as you are working with static graphs. Static meaning that you are not making changes to your graph once it is build and being cautious when allocating memory for your algorithms. If you can keep the activity of the garbage collector close to zero, the runtime of algorithmic operations is comparable to C++.

But it would certainly be an interesting study if someone would implement similar large graphs in both boost and QuickGraph an use these to compare the enviromental penalty.

Oct 20, 2007 at 2:03 PM
I'm trying to use the distance observer.
I was expecting to get the distance from source to vextex a in the dictionnary, but it is not.
I've just look at the code of quickgraph and understand that distance value is an int.
Like Sandrasmurf I don't understand the concept of distance map.

Could you help
Coordinator
Oct 21, 2007 at 2:43 AM
there might be a bug there, looking
Coordinator
Oct 21, 2007 at 3:16 AM
The distance observer has nothing to do with dijkstra. Just use the recorder observer to build the tree, then walk the list of predessor edge and compute the distance on the fly:

(i've also updated the ObserverScope to make it easier to attach/detach):
            // We want to use Dijkstra on this graph
            DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, edgeCost);
 
            // Attach a Vertex Predecessor Recorder Observer to give us the paths
            VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new VertexPredecessorRecorderObserver<string, Edge<string>>();
            using (ObserverScope.Create<IVertexPredecessorRecorderAlgorithm<string, Edge<string>>>(dijkstra, predecessorObserver)) {
                // Run the algorithm with A set to be the source
                dijkstra.Compute("A");
            }
 
            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);
 
            foreach (string v in graph.Vertices) {
                double distance = 0;
                string vertex = v;
                Edge<string> predecessor;
                while (predecessorObserver.VertexPredecessors.TryGetValue(vertex, out predecessor)) {
                    distance += edgeCost[predecessor];
                    vertex = predecessor.Source;
                }
                Console.WriteLine("A -> {0}: {1}", v, distance);
            }
 
Oct 21, 2007 at 9:00 AM
Thanks a lot for your answer.

I'm using quickgraph to find shortest path from A to B on the french railway network.
For the moment, it's just a test that works great.
I have now to model all the constraints in the grah, so still some works to do
I hope I will find the time.
For the moment the graph is 2200 vertices 6400 edges and it works well on a small laptop
Coordinator
Dec 13, 2007 at 6:38 PM
As long as you don't have millions of vertices :)
Jun 29, 2008 at 9:55 PM

Really It was agreat discussion as iam new with quick graph and also want to run the dijkstra algorithm With SharpMap,
But I have some Questions:

1)AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);
   1.1)what's true value mean??
   1.2) are this wil be available if we exchange "string" with sharpMap.Geometry of type Point ??????

2)what's Mean By 'observers' ??? and can u just give me alittle explain about it's types i will use to run the dijkstraaa like:"VertexPredecessorRecorderObserver"and it's importance???

3)your cade seeked to compute all pathes from Node "A",
   Well,What about i want to get the shortest path from Node "A" To Node "D" ForExample.

4) why we do that:
// Remember to detach the observers
distObserver.Detach(dijkstra);
predecessorObserver.Detach(dijkstra);


thanxx in advance,
ElSendrella

Jul 5, 2008 at 1:28 PM
Edited Jul 5, 2008 at 5:46 PM
Hi

First, I would like to thank you for creating QuickGraph

I have some problems with dijekstra

is it suppose to work?

I have observed the source code and found that its usind the dfs algorithm events.
in dijekstra you suppose to choose an edge that gives the minimal weight path from the discovered group to some vertex that wasnt discovered yet:

in each step
    examine the edges that goes out from the discovered vertices to the other
    select the closest undiscovered vertex v such that w(s,v) is minaimal
    add v to the discovered vertices

 
but what happens in the code is different.
its a simple dfs that doesnt choose the "right" vertex in each step

The key to success is to make it choose the right edge in each step, any idea how to make the dfs do that?


I can offer the following implelmentation which does the job but is not robust or "wanabe" efficiant..

class dijekstra
    {
        public Dictionary<TVertex, double> Distances;
        public Dictionary<TVertex, TEdge> ssTreePredecssors;
        public void runDijekstra(IVertexAndEdgeListGraph<TVertex, TEdge> g,                             IDictionary<TEdge, double> weights, TVertex source)
        {
            ssTreePredecssors = new Dictionary<TVertex, TEdge>();
            Distances = new Dictionary<TVertex, double>();
            List<TVertex> Undiscovered = new List<string>();

            // initialize
            foreach (TVertex v in g.Vertices)
            {
                Distances.Add(v, double.MaxValue);
                Undiscovered.Add(v);
            }
            Undiscovered.Remove(source);
            Distances.Remove(source);
            Distances.Add(source, 0);

           
            while (Undiscovered.Count > 0)
            {

                TEdge bestEdge =null;
                foreach (TEdge e in weights.Keys)
                {

                   
                    if (!Undiscovered.Contains(e.Source)
                        && Undiscovered.Contains(e.Target))
                    {
                        if (bestEdge == null) { bestEdge = e; }
                        else if (Distances[bestEdge.Source] + weights[bestEdge] >                                                                     Distances[e.Source] + weights[e])
                        {
                            bestEdge = e;
                        }
                        
                    }
                    // no need to check edges between discovered vertices
                    if (!Undiscovered.Contains(e.Source)
                        && !Undiscovered.Contains(e.Target))
                    {
                        //weights.Remove(e);
                    }
                }

                if (bestEdge == null) { return; };
                Distances[bestEdge.Target] = Distances[bestEdge.Source]+                                  weights[bestEdge];
                weights.Remove(bestEdge);
                Undiscovered.Remove(bestEdge.Target);
                ssTreePredecssors.Add(bestEdge.Target, bestEdge);
            }

        }

    }

it gave the correct result for the code in a previus post:
(the example in : http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html)
Distance from root to node {A} is {0}
Distance from root to node {B} is {4}
Distance from root to node {C} is{6}
Distance from root to node {D} is {1}
Distance from root to node {E} is {16}
Distance from root to node {F} is {26}
Distance from root to node {G} is {23}
Distance from root to node {H} is {33}
Distance from root to node {I} is {37}
Distance from root to node {J} is {18}

Distance from root to node {D} is {A->D}
Distance from root to node {B} is {A->B}
Distance from root to node {C} is {B->C}
Distance from root to node {E} is {B->E}
Distance from root to node {J} is {C->J}
Distance from root to node {G} is {D->G}
Distance from root to node {F} is {J->F}
Distance from root to node {H} is {G->H}
Distance from root to node {I} is {F->I}
Coordinator
Aug 25, 2008 at 6:20 PM
There was a bug in the dijkstra algorithm, I was hooking to the wrong event in the BFS (TreeEdge instead of ExamineEdge), which might have produced invalid path.

Fixed in the source now.
May 17, 2013 at 3:33 PM
Hello, I don't know if this project is still being worked on or if these forums are still being monitored but I was wondering if anyone could assist me. I wanted to try out the example that sandrasmurf had originally posted so I could try to leanr about how to use QuickGraph in other ways, since I'm still fairly new to the QuickGraph library, but I'm getting compile errors.

One error I am getting is when she is instantiating a new DijkstraShortestPathAlgorithm variable called dijkstra. On the second half of the instantiation, I get the error "The best overloaded method match for 'QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm<string,QuickGraph.Edge<string>>.DijkstraShortestPathAlgorithm(QuickGraph.IVertexListGraph<string,QuickGraph.Edge<string>>, System.Func<QuickGraph.Edge<string>,double>)' has some invalid arguments "

The other errors occur when she attemps to create the VertexDistanceRecorderObserver. I am thinking I might be able to substitute some of that code with the code that pelikhan is using. For right now I would just like to know the correct syntax for creating the DijkstraShortestPathAlgorithm.

Thanks in advance and thanks alot for creating the QuickGraph library. If I can get it to work I think it could save me alot of having to learn C++/CLI code.