IT:AD:NET:Libraries:QuickGraph:HowTo:WorkingSample
Summary
SOOOOO few examples.
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