Changeset 8509

Timestamp:

08/20/12 17:32:19 (12 years ago)

Author:

spimming

Message:

#1894:
Dijkstra: get node with a specific rank
graph interface extended: get vertices
fixed bug in ReadData method
methods to perform routing algorithm benchmark added to test program

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning.Test/Program.cs (modified) (4 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Graph/IGraph.cs (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/OsmDataSource.cs (modified) (4 diffs)

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs

@@ -53 +53 @@
 
     #endregion
+
+    public long GetNodeIdWithRank(long sourceNodeId, int rank) {
+      visitedNodes = new HashSet<long>();        // visited
+      unvisitedNodes = new HashSet<long>();      // unvisited
+      distances = new Dictionary<long, float>();
+      predecessors = new Dictionary<long, long>();
+      int currentRank = 0;
+
+
+      long currentNode = sourceNodeId;
+      distances.Add(currentNode, 0);
+      unvisitedNodes.Add(currentNode);
+
+      while (unvisitedNodes.Count > 0) {
+        currentNode = GetMinimumDistance(unvisitedNodes);
+        visitedNodes.Add(currentNode);
+        unvisitedNodes.Remove(currentNode);
+        currentRank++;
+        if (currentRank == rank) {
+          break;
+        }
+        FindMinimalWeight(currentNode);
+      }
+      return currentNode;
+    }
 
     private long GetMinimumDistance(HashSet<long> nodeIds) {

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

@@ -1 +1 @@
 
 using System;
+using System.Collections.Generic;
 using System.Diagnostics;
 using System.IO;
+using System.Linq;
 using System.Xml;
 using HeuristicLab.Algorithms.GraphRouting;
@@ -28 +30 @@
 
       //IDataSource ds = TestLoad(typeof(XmlDataSource), file7);
-      IDataSource ds = TestLoad(typeof(OsmDataSource), file5);
-      OsmGraph graph = new OsmGraph(ds);
+      IDataSource ds = TestLoad(typeof(OsmDataSource), file6);
+      //OsmGraph graph = new OsmGraph(ds);
+
       //IGraph graphNew = TestGetRoutingGraph(ds);
+      //ExecuteBenchmark(graphNew, typeof(AStarAlgorithmV3), 2048, 1000);
 
       //IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
       //IDataSource ds = new OsmDataSource(file5);
 
-      TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
+      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
       //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
-      TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
       //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
       //TestRouter(new BidrectionalDijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
       //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
-      TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
       //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
 
@@ -73 +77 @@
       //TestLoadAndRouterNew(file7, typeof(AStarAlgorithmV3), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
 
-      TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
+      //TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
 
       System.Console.Read();
@@ -299 +303 @@
       return graph;
     }
+
+    private static List<Tuple<long, long>> GenerateSourceTargetPairs(IGraph graph, int locality, int noOfPairs) {
+      List<Tuple<long, long>> benchmarkPairs = new List<Tuple<long, long>>();
+      Random r = new Random();
+      DijkstraAlgorithmV2 dijkstra = new DijkstraAlgorithmV2(graph);
+      int vertexCount = graph.GetVertices().Count;
+
+      for (int i = 0; i < noOfPairs; i++) {
+        long startId = r.Next();
+        Vertex s = graph.GetVertex(startId);
+
+        while (s == null) {
+          startId = r.Next();
+          s = graph.GetVertex(startId);
+        }
+        long targetId = dijkstra.GetNodeIdWithRank(s.Id, locality);
+        Tuple<long, long> t = new Tuple<long, long>(startId, targetId);
+        benchmarkPairs.Add(t);
+      }
+      return benchmarkPairs;
+    }
+
+    private static void ExecuteBenchmark(IGraph graph, Type routerType, int locality, int noOfQueries) {
+      Console.WriteLine("Benchmark Routing Algrithm BEGIN ------------------");
+      Stopwatch sw;
+      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
+
+      Console.Write("Generate queries ... ");
+      List<Tuple<long, long>> queries = GenerateSourceTargetPairs(graph, locality, noOfQueries);
+      Console.WriteLine("done.");
+
+      Console.Write("Execute benchmark ... ");
+      List<TimeSpan> times = new List<TimeSpan>(noOfQueries);
+      foreach (Tuple<long, long> pair in queries) {
+        sw = Stopwatch.StartNew();
+        long[] result = router.Calculate(pair.Item1, pair.Item2);
+        sw.Stop();
+        times.Add(sw.Elapsed);
+      }
+      Console.WriteLine("done.\n");
+
+      Console.WriteLine("Results:");
+      PrintStatistics(times);
+
+      Console.WriteLine("===================================================");
+    }
+
+    private static void PrintStatistics(List<TimeSpan> times) {
+      long averageTicks = Convert.ToInt64(times.Average(timeSpan => timeSpan.Ticks));
+      TimeSpan avg = new TimeSpan(averageTicks);
+      TimeSpan min = times.Min();
+      TimeSpan max = times.Max();
+      TimeSpan total = times.Aggregate(TimeSpan.Zero, (sum, value) => sum.Add(value));
+
+      Console.WriteLine("Min:\t" + min);
+      Console.WriteLine("Max:\t" + max);
+      Console.WriteLine("Avg:\t" + avg);
+      Console.WriteLine("Total:\t" + total);
+      Console.WriteLine("Count:\t" + times.Count);
+
+    }
   }
 }

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

@@ -25 +25 @@
       vertices.TryGetValue(id, out vertex);
       return vertex;
+    }
+
+    public List<Vertex> GetVertices() {
+      return new List<Vertex>(vertices.Values);
     }
 

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/IGraph.cs

@@ -5 +5 @@
     void AddVertex(Vertex vertex);
     Vertex GetVertex(long id);
+    List<Vertex> GetVertices();
     void AddEdge(long startId, long endId);
     void AddEdge(Edge<Vertex> edge);

branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/OsmDataSource.cs

@@ -141 +141 @@
       NameTable nt = new NameTable();
       string osmName = nt.Add("osm");
-      string nodeName = nt.Add("node");
+      object nodeName = nt.Add("node");
       object tagName = nt.Add("tag");
       object wayName = nt.Add("way");
@@ -147 +147 @@
       string lonName = nt.Add("lon");
       string idName = nt.Add("id");
-      string ndName = nt.Add("nd");
+      object ndName = nt.Add("nd");
       string refName = nt.Add("ref");
       string kName = nt.Add("k");
@@ -166 +166 @@
 
           reader.Read();
-          if (reader.LocalName.Equals(tagName)) {
-            reader.ReadToFollowing(nodeName, ns);
-          }
-        }
-        while (reader.LocalName.Equals(wayName)) {
+          //if (reader.LocalName.Equals(tagName)) {
+          if (ReferenceEquals(tagName, reader.LocalName)) {
+            reader.ReadToFollowing((string)nodeName, ns);
+          }
+        }
+        //while (reader.LocalName.Equals(wayName)) {
+        while (ReferenceEquals(wayName, reader.LocalName)) {
           List<Vertex> way = new List<Vertex>();
           bool missingNodes = false;
@@ -177 +179 @@
 
           reader.Read();
-          while (reader.LocalName.Equals(nodeName) || reader.LocalName.Equals(tagName)) {
+          while (ReferenceEquals(ndName, reader.LocalName) || ReferenceEquals(tagName, reader.LocalName)) {
             if (reader.LocalName.Equals(ndName)) {
               long refNodeId = XmlConvert.ToInt64(reader.GetAttribute(refName, ns));