source: branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs @ 8509

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Xml;
using HeuristicLab.Algorithms.GraphRouting;
using HeuristicLab.Problems.RoutePlanning.Graph;
using HeuristicLab.Problems.RoutePlanning.Osm;
using HeuristicLab.Problems.RoutePlanning.Osm.Data;
namespace HeuristicLab.Problems.RoutePlanning.Test {
  class Program {
    static void Main(string[] args) {
      // For testing openstreetmap data is used
      // http://www.openstreetmap.org
      // Map data © OpenStreetMap contributors, CC BY-SA

      string file1 = @"..\..\OsmTestFiles\test.osm";
      string file2 = @"..\..\OsmTestFiles\testNode1.osm";
      string file3 = @"..\..\OsmTestFiles\testWay1.osm";
      string file4 = @"..\..\OsmTestFiles\testRelation1.osm";
      string file5 = @"..\..\OsmTestFiles\test_mid.osm";
      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(typeof(XmlDataSource), file7);
      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 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 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 AStarAlgorithmV2(graph), 32044987, 261576106, false);    //vorarblberg
      //TestRouter(new AStarAlgorithmV3(graphNew), 32044987, 261576106, false);    //vorarblberg

      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
      //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 31372732, false, false); // inz - hgb
      //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 31372732, false, true); // inz - hgb

      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
      //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 1001363194, true, false);
      //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 1001363194, true, false);
      //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, false);

      //TestLoadAndRouter(file5, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
      //TestLoadAndRouter(file5, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, true);
      //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);

      //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();
    }

    private static long[] TestRouter(IRouter router, long sourceNodeId, long targetNodeId, bool showResult) {
      Console.WriteLine("Test Router BEGIN ---------------------------------");
      Console.WriteLine("Type: " + router.GetType());

      Console.Write("Calculate route ... ");
      var 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();
      }
      Console.WriteLine("===================================================");
      Console.WriteLine();
      return result;
    }

    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);
      Console.WriteLine();
      Console.Write("Loading data ... ");
      var sw = Stopwatch.StartNew();
      IDataSource ds = (IDataSource)Activator.CreateInstance(dsType, paths);
      sw.Stop();
      Console.WriteLine("done.");
      Console.WriteLine("Time: {0}", sw.Elapsed);
      Console.WriteLine();
      Console.WriteLine("===================================================");
      Console.WriteLine();
      return ds;
    }

    private static void TestLoadAndRouter(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();
      OsmGraph graph = new OsmGraph(xmlDs);
      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);
        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("===================================================");
      Console.WriteLine();
    }

    private static void WriteGPXFile(OsmGraph 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) {
          OsmVertex<Node> node = graph.GetVertex(nodeId);
          writer.WriteStartElement("wpt");
          writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
          writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
          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 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 ------------------------");
      Console.WriteLine();
      Console.Write("Construct graph ... ");
      var sw = Stopwatch.StartNew();
      IGraph graph = ds.GetRoutingGraph();
      sw.Stop();
      Console.WriteLine("done.");
      Console.WriteLine("Time: {0}", sw.Elapsed);
      Console.WriteLine();
      Console.WriteLine("===================================================");
      Console.WriteLine();
      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);

    }
  }
}