Raw Performance Boost vs. QuickGraph

Topics: graph
Jan 1, 2010 at 8:27 AM

I have a graph with  10649 Waypoints and 14158 connections and I'm currently using QuickGraph to calculate shortest route.

Currently it takes ~300 ms on my reference test machine and I need to find every ms i can....

I need to build the graph for each route since no two routes are based on the same net (and If they are, I'm caching the answer, so that quick enough).

 

AdjacencyGraph<string, Edge<string>> graph = new AdjacencyGraph<string, Edge<string>>(true);

I insert Vertexes with: (In a loop that desides what vertexes are valid for this graph)

 graph.AddVertex(p.PortID);

I add the connection (right now bi directionaly, but that might change in the future)
     Edge<string> e = new Edge<string>(C.FromID, C.ToID);
     graph.AddEdge(e);
     edgeCost.Add(e, C.Length); // Distance

     // to from -> from to
    Edge<string> e2 = new Edge<string>(C.ToID, C.FromID);
    graph.AddEdge(e2);
    edgeCost.Add(e2, C.Length); // Distance

Then I caluculate:
    DijkstraShortestPathAlgorithm<string, Edge<string>> dijkstra = new DijkstraShortestPathAlgorithm<string, Edge<string>>(graph, AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
    QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>> predecessorObserver = new QuickGraph.Algorithms.Observers.VertexPredecessorRecorderObserver<string, Edge<string>>();
    predecessorObserver.Attach(dijkstra);
    VertexDistanceRecorderObserver<string, Edge<string>> distObserver = new VertexDistanceRecorderObserver<string, Edge<string>>(AlgorithmExtensions.GetIndexer<Edge<string>, double>(edgeCost));
    distObserver.Attach(dijkstra);
    dijkstra.Compute(FromPort);


Then I get the route:
                predecessorObserver.TryGetPath(ToPort, out Path);

Is this, in a performance view, the fastest way to do this ? I was wondering if the boost library still had the upper hand performance wise ?

Happy New year :)

 

Feb 14, 2010 at 10:40 PM

Boost probably has the upper hand.

* you do not need the distObserver in your example, which might save some cycles.
* use integers instead of string as vertices which will save more cycles
* If you know the number of vertices before hand, use an ArrayAdjacencyGraph which is a more compact and efficient representation

Hope that helps.