Changeset 8481

Timestamp:

08/13/12 17:37:05 (12 years ago)

Author:

spimming

Message:

#1894:

• adapted AStar and Dijkstra algorithms for new graph representation
• test program modified

Location:

branches/RoutePlanning

Files:

• HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV2.cs (modified) (1 diff)
• HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs (added)
• HeuristicLab.Algorithms.GraphRouting/3.3/BidirectionalDijkstraAlgorithmV2.cs (added)
• HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs (modified) (1 diff)
• HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj (modified) (1 diff)
• HeuristicLab.Problems.RoutePlanning.Test/Program.cs (modified) (5 diffs)

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

@@ -99 +99 @@
       return route;
     }
-  }
 
-  class NodeData : IComparable<NodeData> {
-    public long Node { get; set; }
-    public float Costs { get; set; }
+    private class NodeData : IComparable<NodeData> {
+      public long Node { get; set; }
+      public float Costs { get; set; }
 
-    public NodeData(long nodeId, float f) {
-      Node = nodeId;
-      Costs = f;
+      public NodeData(long nodeId, float f) {
+        Node = nodeId;
+        Costs = f;
+      }
+
+      #region IComparable<NodeData> Members
+
+      public int CompareTo(NodeData other) {
+        return this.Costs > other.Costs ? 1 : this.Costs < other.Costs ? -1 : 0;
+      }
+
+      #endregion
     }
-
-    #region IComparable<NodeData> Members
-
-    public int CompareTo(NodeData other) {
-      return this.Costs > other.Costs ? 1 : this.Costs < other.Costs ? -1 : 0;
-    }
-
-    #endregion
   }
 }

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

@@ -76 +76 @@
 
     private void FindMinimalWeight(long nodeId) {
+      //if (nodeId == 274265932) {
+      //  Console.WriteLine();
+      //}
       Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
       foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

@@ -60 +60 @@
     <Compile Include="AStarAlgorithmV2.cs" />
     <Compile Include="BidirectionalDijkstraAlgorithm.cs" />
+    <Compile Include="AStarAlgorithmV3.cs" />
+    <Compile Include="BidirectionalDijkstraAlgorithmV2.cs" />
     <Compile Include="DijkstraAlgorithmV2.cs" />
     <Compile Include="DijkstraAlgorithm.cs" />

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 +24 @@
       string file7 = @"C:\dev\osmfiles\austria.highway.osm";
 
-      IDataSource ds = TestLoad(file5);
-      OsmGraph graph = new OsmGraph(ds);
-      IGraph graphNew = TestGetRoutingGraph(ds);
-      TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
-      TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
+      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);
+      //IGraph graphNew = TestGetRoutingGraph(ds);
+
+      IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
+
+      //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 DijkstraAlgorithmV2(graphNew), 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 BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
+      //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
 
       //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
+      //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
 
       //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
@@ -50 +60 @@
       //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
 
-
-
-
+      //TestLoadAndRouterNew(file6, typeof(DijkstraAlgorithmV2), 529102170, 31372732, false, true);
+      //TestLoadAndRouterNew(file6, typeof(BidrectionalDijkstraAlgorithmV2), 529102170, 31372732, false, true);
+      //TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true);
 
       System.Console.Read();
@@ -129 +139 @@
         Console.WriteLine("Result file: {0}", resultFile);
         WriteGPXFile(graph, result, resultFile);
+      }
+      Console.WriteLine("===================================================");
+      Console.WriteLine();
+    }
+
+    private static void TestLoadAndRouterNew(string filepath, Type routerType, long sourceNodeId, long targetNodeId, bool showResult, bool writeResultFile) {
+      FileInfo file = new FileInfo(filepath);
+      Console.WriteLine("Test Load and Route BEGIN -------------------------");
+      Console.WriteLine("File name: {0}", file.Name);
+      Console.WriteLine();
+      Console.Write("Loading data ... ");
+      var sw = Stopwatch.StartNew();
+      XmlDataSource xmlDs = new XmlDataSource(filepath);
+      sw.Stop();
+      Console.WriteLine("done.");
+      Console.WriteLine("Loading Time: {0}", sw.Elapsed);
+      Console.WriteLine();
+      IGraph graph = xmlDs.GetRoutingGraph();
+      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
+      Console.Write("Calculate route ... ");
+      sw = Stopwatch.StartNew();
+      long[] result = router.Calculate(sourceNodeId, targetNodeId);
+      sw.Stop();
+      Console.WriteLine("done.");
+      Console.WriteLine("Execution Time: {0}", sw.Elapsed);
+      Console.WriteLine();
+      if (showResult) {
+        Console.WriteLine("Result: ");
+        foreach (long i in result) System.Console.Write(i + "; ");
+        Console.WriteLine();
+        Console.WriteLine();
+      }
+      if (writeResultFile) {
+        string dt = DateTime.Now.ToString("yyyyMMddhhmmss_");
+        string fn = Path.GetFileNameWithoutExtension(file.Name);
+        string resultFile = dt + fn + "_" + sourceNodeId + "-" + targetNodeId + ".gpx";
+        Console.WriteLine("Result file: {0}", resultFile);
+        WriteGPXFileNew(graph, result, resultFile);
       }
       Console.WriteLine("===================================================");
@@ -180 +228 @@
     }
 
+    private static void WriteGPXFileNew(IGraph graph, long[] route, string file) {
+      XmlWriterSettings settings = new XmlWriterSettings();
+      settings.Indent = true;
+      settings.IndentChars = ("   ");
+
+      using (XmlWriter writer = XmlWriter.Create(file, settings)) {
+        writer.WriteStartElement("gpx", "http://www.topografix.com/GPX/1/0");
+        writer.WriteAttributeString("version", "1.1");
+        writer.WriteAttributeString("creator", "cloudia");
+
+        foreach (long nodeId in route) {
+          Vertex node = graph.GetVertex(nodeId);
+          writer.WriteStartElement("wpt");
+          writer.WriteAttributeString("lat", XmlConvert.ToString(node.Latitude));
+          writer.WriteAttributeString("lon", XmlConvert.ToString(node.Logitude));
+          writer.WriteEndElement(); // wpt
+        }
+
+        //writer.WriteStartElement("rte");
+        //foreach (long nodeId in route) {
+        //  Vertex<Node> node = graph.GetVertex(nodeId);
+        //  writer.WriteStartElement("rtept");
+        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
+        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
+        //  writer.WriteEndElement(); // rtept
+        //}
+        //writer.WriteEndElement(); // rte
+
+        //writer.WriteStartElement("trk");
+        //writer.WriteElementString("name", "RoutePath");
+        ////writer.WriteEndElement(); // name
+        //writer.WriteStartElement("trkseq");
+        //foreach (long nodeId in route) {
+        //  Vertex<Node> node = graph.GetVertex(nodeId);
+        //  writer.WriteStartElement("trkpt");
+        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
+        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
+        //  writer.WriteEndElement(); // trkpt
+        //}
+        //writer.WriteEndElement(); // trkseq
+        //writer.WriteEndElement(); // trk
+
+        writer.WriteEndElement(); // gpx
+      }
+    }
+
     private static IGraph TestGetRoutingGraph(IDataSource ds) {
       Console.WriteLine("Test GetRoutingGraph BEGIN ------------------------");