CodePlexProject Hosting for Open Source Software

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);

Func<TEdge, double> edgeCost = e => 1; // constant cost // We want to use Dijkstra on this graph var dijkstra = new DijkstraShortestPathAlgorithm<TEdge, TEdge>(graph, edgeCost);

to the Dijkstra algorithm will let us build a predecessor tree. This tree is later used to build shortest paths.

// Attach a Vertex Predecessor Recorder Observer to give us the paths var predecessors = new VertexPredecessorRecorderObserver<TVertex, TEdge>(); using (predecessors.Attach(dijkstra)) // Run the algorithm with A set to be the source dijkstra.Compute("A");

The predecessors instance now contains a dictionary of distance from each vertex to the source:

foreach (var v in graph.Vertices) { double distance = 0; TVertex vertex = v; TEdge predecessor; while (predecessors.VertexPredecessors.TryGetValue(vertex, out predecessor)) { distance += edgeCost[predecessor]; vertex = predecessor.Source; } Console.WriteLine("A -> {0}: {1}", v, distance); }

Dictionary<TEdge, double> edgeCostDictionary = ... Func<TEdge,double> edgeCost = AlgorithmExtensions.GetIndexer(edgeCostDictionary); ...

Last edited Apr 26, 2009 at 7:34 AM by pelikhan, version 10

Another typo:

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edgeCost, root);

should be:

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathsDijkstra(edgeCost, root);

ALSO...

I finally got some code to compile but when run I get a run-time error because Comparer.Compare() is being used to compare vertices. My vertices are of type PointF which does not implement IComparable. My question is why do the vertices need to be ordered? I could imagine why they would need IEquatable but why IComparable?

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathDijkstra(edg

should be:

TryFunc<TVertex, TEdge> tryGetPaths = graph.ShortestPathsDijkstra(ed

ALSO...

I finally got some code to compile but when run I get a run-time error because Comparer.Compare() is being used to compare vertices. My vertices are of type PointF which does not implement IComparable. My question is why do the vertices need to be ordered? I could imagine why they would need IEquatable but why IComparable?

Typo:

var dijkstra = new DijkstraShortestPathAlgorithm<TEdge, TEdge>...

should be

var dijkstra = new DijkstraShortestPathAlgorithm<TVertex, TEdge>

var dijkstra = new DijkstraShortestPathAlgorithm<

should be

var dijkstra = new DijkstraShortestPathAlgorithm<