Changeset 8504

Timestamp:

08/20/12 11:39:25 (12 years ago)

Author:

spimming

Message:

#1894: new read data method using NameTable for better performance

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Problems.RoutePlanning.Test/Program.cs (modified) (6 diffs)
• HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/OsmDataSource.cs (modified) (2 diffs)

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

@@ -5 +5 @@
 using System.Xml;
 using HeuristicLab.Algorithms.GraphRouting;
-using HeuristicLab.Problems.RoutePlanning.DIMACS;
 using HeuristicLab.Problems.RoutePlanning.Graph;
 using HeuristicLab.Problems.RoutePlanning.Osm;
@@ -23 +22 @@
       string file6 = @"C:\dev\osmfiles\oberosterreich.highway.osm";
       string file7 = @"C:\dev\osmfiles\austria.highway.osm";
+      string file8 = @"C:\dev\osmfiles\vorarlberg.highway.osm";
 
       string fileNYArcs = @"C:\dev\DIMACSfiles\USA-road-t.NY.gr.gz";
       string fileNYCoords = @"C:\dev\DIMACSfiles\USA-road-d.NY.co.gz";
 
-      //IDataSource ds = TestLoad(file5);
-      //OsmGraph graph = new OsmGraph(ds);
+      //IDataSource ds = TestLoad(typeof(XmlDataSource), file7);
+      IDataSource ds = TestLoad(typeof(OsmDataSource), file5);
+      OsmGraph graph = new OsmGraph(ds);
       //IGraph graphNew = TestGetRoutingGraph(ds);
 
-      IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
-
-      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
+      //IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
+      //IDataSource ds = new OsmDataSource(file5);
+
+      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
 
+      //TestRouter(new AStarAlgorithmV2(graph), 763113382, 1078628481, false); // bregenz (bahnhofstr) - podersdorf (??)
+      //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
       //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
-      //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
+
+      //TestRouter(new AStarAlgorithmV2(graph), 32044987, 261576106, false);    //vorarblberg
+      //TestRouter(new AStarAlgorithmV3(graphNew), 32044987, 261576106, false);    //vorarblberg
 
       //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
@@ -64 +70 @@
       //TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true);
 
+      //TestLoadAndRouter(file7, typeof(AStarAlgorithmV2), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
+      //TestLoadAndRouterNew(file7, typeof(AStarAlgorithmV3), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
+
+      TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
+
       System.Console.Read();
     }
@@ -89 +100 @@
     }
 
-    private static IDataSource TestLoad(string filepath) {
-      FileInfo file = new FileInfo(filepath);
+    private static IDataSource TestLoad(Type dsType, params string[] paths) {
+      FileInfo file = new FileInfo(paths[0]);
       Console.WriteLine("Test Load Data BEGIN ------------------------------");
       Console.WriteLine("File name: {0}", file.Name);
@@ -96 +107 @@
       Console.Write("Loading data ... ");
       var sw = Stopwatch.StartNew();
-      XmlDataSource xmlDs = new XmlDataSource(filepath);
+      IDataSource ds = (IDataSource)Activator.CreateInstance(dsType, paths);
       sw.Stop();
       Console.WriteLine("done.");
@@ -103 +114 @@
       Console.WriteLine("===================================================");
       Console.WriteLine();
-      return xmlDs;
+      return ds;
     }
 

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

@@ -16 +16 @@
       vertices = new Dictionary<long, Vertex>();
 
-      ReadData();
+      ReadDataV2();
     }
 
@@ -134 +134 @@
       }
     }
+
+    private void ReadDataV2() {
+      XmlReaderSettings settings = new XmlReaderSettings();
+      settings.IgnoreComments = true;
+      settings.IgnoreWhitespace = true;
+      NameTable nt = new NameTable();
+      string osmName = nt.Add("osm");
+      string nodeName = nt.Add("node");
+      object tagName = nt.Add("tag");
+      object wayName = nt.Add("way");
+      string latName = nt.Add("lat");
+      string lonName = nt.Add("lon");
+      string idName = nt.Add("id");
+      string ndName = nt.Add("nd");
+      string refName = nt.Add("ref");
+      string kName = nt.Add("k");
+      string vName = nt.Add("v");
+      settings.NameTable = nt;
+      string ns = "";
+
+      using (XmlReader reader = XmlReader.Create(file.FullName, settings)) {
+        reader.ReadStartElement(osmName, ns);
+        reader.Read();
+        while (reader.LocalName.Equals(nodeName)) {
+          double lat = XmlConvert.ToDouble(reader.GetAttribute(latName, ns));
+          double lon = XmlConvert.ToDouble(reader.GetAttribute(lonName, ns));
+          long id = XmlConvert.ToInt64(reader.GetAttribute(idName, ns));
+
+          Vertex v = new Vertex(id, lon, lat);
+          vertices.Add(v.Id, v);
+
+          reader.Read();
+          if (reader.LocalName.Equals(tagName)) {
+            reader.ReadToFollowing(nodeName, ns);
+          }
+        }
+        while (reader.LocalName.Equals(wayName)) {
+          List<Vertex> way = new List<Vertex>();
+          bool missingNodes = false;
+          HighwayType category = HighwayType.null_type;
+          bool oneWayRoad = false;
+
+          reader.Read();
+          while (reader.LocalName.Equals(nodeName) || reader.LocalName.Equals(tagName)) {
+            if (reader.LocalName.Equals(ndName)) {
+              long refNodeId = XmlConvert.ToInt64(reader.GetAttribute(refName, ns));
+              Vertex vertex = GetVertex(refNodeId);
+              if (vertex != null) {
+                way.Add(vertex);
+              } else {
+                missingNodes = true;
+              }
+
+            } else if (reader.LocalName.Equals(tagName)) {
+              string key = reader.GetAttribute(kName, ns);
+              string value = reader.GetAttribute(vName, ns);
+
+              if (key == TagConstants.HighwayTagKey) {
+                if (Enum.IsDefined(typeof(HighwayType), value)) {
+                  HighwayType ht = (HighwayType)Enum.Parse(typeof(HighwayType), value, true);
+                  category = ht;
+                } else {
+                  category = HighwayType.null_type;
+                }
+              } else if (key == TagConstants.OneWayTag) {
+                oneWayRoad = value.Equals(TagConstants.YesValue);
+              }
+            }
+            reader.Read();
+          }
+          if (missingNodes) {
+            // TODO: Error/Trace output 
+            // if Way xxx has incomplete nodes. At least one node was missing in the data.
+          }
+          for (int i = 0; i < way.Count - 1; i++) {
+            Vertex v1 = way[i];
+            graph.AddVertex(v1);
+            Vertex v2 = way[i + 1];
+            graph.AddVertex(v2);
+            short vertexCategory = (short)category;
+            if (oneWayRoad) {
+              Edge<Vertex> edge = new Edge<Vertex>(v1, v2, vertexCategory);
+              graph.AddEdge(edge);
+            } else {
+              Edge<Vertex> edgeForward = new Edge<Vertex>(v1, v2, vertexCategory);
+              graph.AddEdge(edgeForward);
+
+              Edge<Vertex> edgeBackward = new Edge<Vertex>(v2, v1, vertexCategory);
+              graph.AddEdge(edgeBackward);
+            }
+          }
+          reader.Read();
+        }
+        reader.Close();
+      }
+    }
   }
 }