Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 8514 was 8514, checked in by spimming, 10 years ago

#1894: experimented with different settings in cost and heuristic function

File size: 17.2 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using System.Diagnostics;
5using System.IO;
6using System.Linq;
7using System.Xml;
8using HeuristicLab.Algorithms.GraphRouting;
9using HeuristicLab.Problems.RoutePlanning.Graph;
10using HeuristicLab.Problems.RoutePlanning.Osm;
11using HeuristicLab.Problems.RoutePlanning.Osm.Data;
12namespace HeuristicLab.Problems.RoutePlanning.Test {
13  class Program {
14    static void Main(string[] args) {
15      // For testing openstreetmap data is used
16      // http://www.openstreetmap.org
17      // Map data © OpenStreetMap contributors, CC BY-SA
18
19      string file1 = @"..\..\OsmTestFiles\test.osm";
20      string file2 = @"..\..\OsmTestFiles\testNode1.osm";
21      string file3 = @"..\..\OsmTestFiles\testWay1.osm";
22      string file4 = @"..\..\OsmTestFiles\testRelation1.osm";
23      string file5 = @"..\..\OsmTestFiles\test_mid.osm";
24      string file6 = @"C:\dev\osmfiles\oberosterreich.highway.osm";
25      string file7 = @"C:\dev\osmfiles\austria.highway.osm";
26      string file8 = @"C:\dev\osmfiles\vorarlberg.highway.osm";
27
28      string fileNYArcs = @"C:\dev\DIMACSfiles\USA-road-t.NY.gr.gz";
29      string fileNYCoords = @"C:\dev\DIMACSfiles\USA-road-d.NY.co.gz";
30
31      //IDataSource ds = TestLoad(typeof(XmlDataSource), file7);
32      //IDataSource ds = TestLoad(typeof(OsmDataSource), file6);
33      //OsmGraph graph = new OsmGraph(ds);
34
35      //IGraph graphNew = TestGetRoutingGraph(ds);
36      //ExecuteBenchmark(graphNew, typeof(AStarAlgorithmV3), 262144, 20);
37
38      //IRouter router = new AStarAlgorithmV3(graphNew);
39      //long[] r = router.Calculate(266733493, 986825165);
40      ////long[] r = router.Calculate(998717680, 986825165);
41
42      //IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
43      //IDataSource ds = new OsmDataSource(file5);
44
45      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
46      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
47      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
48      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
49      //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
50      //TestRouter(new BidrectionalDijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
51      //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
52      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
53      //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
54
55      //TestRouter(new AStarAlgorithmV2(graph), 763113382, 1078628481, false); // bregenz (bahnhofstr) - podersdorf (??)
56      //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
57      //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
58
59      //TestRouter(new AStarAlgorithmV2(graph), 32044987, 261576106, false);    //vorarblberg
60      //TestRouter(new AStarAlgorithmV3(graphNew), 32044987, 261576106, false);    //vorarblberg
61
62      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
63      //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 31372732, false, false); // inz - hgb
64      //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 31372732, false, true); // inz - hgb
65
66      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
67      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
68      //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 1001363194, true, false);
69      //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 1001363194, true, false);
70      //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, false);
71
72      //TestLoadAndRouter(file5, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
73      //TestLoadAndRouter(file5, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, true);
74      //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
75
76      TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true); // inz - hgb
77      //TestLoadAndRouterNew(file6, typeof(DijkstraAlgorithmV2), 529102170, 31372732, false, true);
78      //TestLoadAndRouterNew(file6, typeof(BidrectionalDijkstraAlgorithmV2), 529102170, 31372732, false, true);
79      //TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true);
80
81      //TestLoadAndRouter(file7, typeof(AStarAlgorithmV2), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
82      //TestLoadAndRouterNew(file7, typeof(AStarAlgorithmV3), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
83
84      //TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
85
86      System.Console.Read();
87    }
88
89    private static long[] TestRouter(IRouter router, long sourceNodeId, long targetNodeId, bool showResult) {
90      Console.WriteLine("Test Router BEGIN ---------------------------------");
91      Console.WriteLine("Type: " + router.GetType());
92
93      Console.Write("Calculate route ... ");
94      var sw = Stopwatch.StartNew();
95      long[] result = router.Calculate(sourceNodeId, targetNodeId);
96      sw.Stop();
97      Console.WriteLine("done.");
98      Console.WriteLine("Execution Time: {0}", sw.Elapsed);
99      Console.WriteLine();
100      if (showResult) {
101        Console.WriteLine("Result: ");
102        foreach (long i in result) System.Console.Write(i + "; ");
103        Console.WriteLine();
104        Console.WriteLine();
105      }
106      Console.WriteLine("===================================================");
107      Console.WriteLine();
108      return result;
109    }
110
111    private static IDataSource TestLoad(Type dsType, params string[] paths) {
112      FileInfo file = new FileInfo(paths[0]);
113      Console.WriteLine("Test Load Data BEGIN ------------------------------");
114      Console.WriteLine("File name: {0}", file.Name);
115      Console.WriteLine();
116      Console.Write("Loading data ... ");
117      var sw = Stopwatch.StartNew();
118      IDataSource ds = (IDataSource)Activator.CreateInstance(dsType, paths);
119      sw.Stop();
120      Console.WriteLine("done.");
121      Console.WriteLine("Time: {0}", sw.Elapsed);
122      Console.WriteLine();
123      Console.WriteLine("===================================================");
124      Console.WriteLine();
125      return ds;
126    }
127
128    private static void TestLoadAndRouter(string filepath, Type routerType, long sourceNodeId, long targetNodeId, bool showResult, bool writeResultFile) {
129      FileInfo file = new FileInfo(filepath);
130      Console.WriteLine("Test Load and Route BEGIN -------------------------");
131      Console.WriteLine("File name: {0}", file.Name);
132      Console.WriteLine();
133      Console.Write("Loading data ... ");
134      var sw = Stopwatch.StartNew();
135      XmlDataSource xmlDs = new XmlDataSource(filepath);
136      sw.Stop();
137      Console.WriteLine("done.");
138      Console.WriteLine("Loading Time: {0}", sw.Elapsed);
139      Console.WriteLine();
140      OsmGraph graph = new OsmGraph(xmlDs);
141      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
142      Console.Write("Calculate route ... ");
143      sw = Stopwatch.StartNew();
144      long[] result = router.Calculate(sourceNodeId, targetNodeId);
145      sw.Stop();
146      Console.WriteLine("done.");
147      Console.WriteLine("Execution Time: {0}", sw.Elapsed);
148      Console.WriteLine();
149      if (showResult) {
150        Console.WriteLine("Result: ");
151        foreach (long i in result) System.Console.Write(i + "; ");
152        Console.WriteLine();
153        Console.WriteLine();
154      }
155      if (writeResultFile) {
156        string dt = DateTime.Now.ToString("yyyyMMddhhmmss_");
157        string fn = Path.GetFileNameWithoutExtension(file.Name);
158        string resultFile = dt + fn + "_" + sourceNodeId + "-" + targetNodeId + ".gpx";
159        Console.WriteLine("Result file: {0}", resultFile);
160        WriteGPXFile(graph, result, resultFile);
161      }
162      Console.WriteLine("===================================================");
163      Console.WriteLine();
164    }
165
166    private static void TestLoadAndRouterNew(string filepath, Type routerType, long sourceNodeId, long targetNodeId, bool showResult, bool writeResultFile) {
167      FileInfo file = new FileInfo(filepath);
168      Console.WriteLine("Test Load and Route BEGIN -------------------------");
169      Console.WriteLine("File name: {0}", file.Name);
170      Console.WriteLine();
171      Console.Write("Loading data ... ");
172      var sw = Stopwatch.StartNew();
173      //XmlDataSource xmlDs = new XmlDataSource(filepath);
174      IDataSource xmlDs = new OsmDataSource(filepath);
175      sw.Stop();
176      Console.WriteLine("done.");
177      Console.WriteLine("Loading Time: {0}", sw.Elapsed);
178      Console.WriteLine();
179      IGraph graph = xmlDs.GetRoutingGraph();
180      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
181      Console.Write("Calculate route ... ");
182      sw = Stopwatch.StartNew();
183      long[] result = router.Calculate(sourceNodeId, targetNodeId);
184      sw.Stop();
185      Console.WriteLine("done.");
186      Console.WriteLine("Execution Time: {0}", sw.Elapsed);
187      Console.WriteLine();
188      if (showResult) {
189        Console.WriteLine("Result: ");
190        foreach (long i in result) System.Console.Write(i + "; ");
191        Console.WriteLine();
192        Console.WriteLine();
193      }
194      if (writeResultFile) {
195        string dt = DateTime.Now.ToString("yyyyMMddhhmmss_");
196        string fn = Path.GetFileNameWithoutExtension(file.Name);
197        string resultFile = dt + fn + "_" + sourceNodeId + "-" + targetNodeId + ".gpx";
198        Console.WriteLine("Result file: {0}", resultFile);
199        WriteGPXFileNew(graph, result, resultFile);
200      }
201      Console.WriteLine("===================================================");
202      Console.WriteLine();
203    }
204
205    private static void WriteGPXFile(OsmGraph graph, long[] route, string file) {
206      XmlWriterSettings settings = new XmlWriterSettings();
207      settings.Indent = true;
208      settings.IndentChars = ("   ");
209
210      using (XmlWriter writer = XmlWriter.Create(file, settings)) {
211        writer.WriteStartElement("gpx", "http://www.topografix.com/GPX/1/0");
212        writer.WriteAttributeString("version", "1.1");
213        writer.WriteAttributeString("creator", "cloudia");
214
215        foreach (long nodeId in route) {
216          OsmVertex<Node> node = graph.GetVertex(nodeId);
217          writer.WriteStartElement("wpt");
218          writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
219          writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
220          writer.WriteEndElement(); // wpt
221        }
222
223        //writer.WriteStartElement("rte");
224        //foreach (long nodeId in route) {
225        //  Vertex<Node> node = graph.GetVertex(nodeId);
226        //  writer.WriteStartElement("rtept");
227        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
228        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
229        //  writer.WriteEndElement(); // rtept
230        //}
231        //writer.WriteEndElement(); // rte
232
233        //writer.WriteStartElement("trk");
234        //writer.WriteElementString("name", "RoutePath");
235        ////writer.WriteEndElement(); // name
236        //writer.WriteStartElement("trkseq");
237        //foreach (long nodeId in route) {
238        //  Vertex<Node> node = graph.GetVertex(nodeId);
239        //  writer.WriteStartElement("trkpt");
240        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
241        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
242        //  writer.WriteEndElement(); // trkpt
243        //}
244        //writer.WriteEndElement(); // trkseq
245        //writer.WriteEndElement(); // trk
246
247        writer.WriteEndElement(); // gpx
248      }
249    }
250
251    private static void WriteGPXFileNew(IGraph graph, long[] route, string file) {
252      XmlWriterSettings settings = new XmlWriterSettings();
253      settings.Indent = true;
254      settings.IndentChars = ("   ");
255
256      using (XmlWriter writer = XmlWriter.Create(file, settings)) {
257        writer.WriteStartElement("gpx", "http://www.topografix.com/GPX/1/0");
258        writer.WriteAttributeString("version", "1.1");
259        writer.WriteAttributeString("creator", "cloudia");
260
261        foreach (long nodeId in route) {
262          Vertex node = graph.GetVertex(nodeId);
263          writer.WriteStartElement("wpt");
264          writer.WriteAttributeString("lat", XmlConvert.ToString(node.Latitude));
265          writer.WriteAttributeString("lon", XmlConvert.ToString(node.Logitude));
266          writer.WriteEndElement(); // wpt
267        }
268
269        //writer.WriteStartElement("rte");
270        //foreach (long nodeId in route) {
271        //  Vertex<Node> node = graph.GetVertex(nodeId);
272        //  writer.WriteStartElement("rtept");
273        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
274        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
275        //  writer.WriteEndElement(); // rtept
276        //}
277        //writer.WriteEndElement(); // rte
278
279        //writer.WriteStartElement("trk");
280        //writer.WriteElementString("name", "RoutePath");
281        ////writer.WriteEndElement(); // name
282        //writer.WriteStartElement("trkseq");
283        //foreach (long nodeId in route) {
284        //  Vertex<Node> node = graph.GetVertex(nodeId);
285        //  writer.WriteStartElement("trkpt");
286        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
287        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
288        //  writer.WriteEndElement(); // trkpt
289        //}
290        //writer.WriteEndElement(); // trkseq
291        //writer.WriteEndElement(); // trk
292
293        writer.WriteEndElement(); // gpx
294      }
295    }
296
297    private static IGraph TestGetRoutingGraph(IDataSource ds) {
298      Console.WriteLine("Test GetRoutingGraph BEGIN ------------------------");
299      Console.WriteLine();
300      Console.Write("Construct graph ... ");
301      var sw = Stopwatch.StartNew();
302      IGraph graph = ds.GetRoutingGraph();
303      sw.Stop();
304      Console.WriteLine("done.");
305      Console.WriteLine("Time: {0}", sw.Elapsed);
306      Console.WriteLine();
307      Console.WriteLine("===================================================");
308      Console.WriteLine();
309      return graph;
310    }
311
312    private static List<Tuple<long, long>> GenerateSourceTargetPairs(IGraph graph, int locality, int noOfPairs) {
313      List<Tuple<long, long>> benchmarkPairs = new List<Tuple<long, long>>();
314      Random r = new Random();
315      DijkstraAlgorithmV2 dijkstra = new DijkstraAlgorithmV2(graph);
316      int vertexCount = graph.GetVertices().Count;
317
318      for (int i = 0; i < noOfPairs; i++) {
319        long startId = r.Next();
320        Vertex s = graph.GetVertex(startId);
321
322        while (s == null) {
323          startId = r.Next();
324          s = graph.GetVertex(startId);
325        }
326        long targetId = dijkstra.GetNodeIdWithRank(s.Id, locality);
327        Tuple<long, long> t = new Tuple<long, long>(startId, targetId);
328        benchmarkPairs.Add(t);
329      }
330      return benchmarkPairs;
331    }
332
333    private static void ExecuteBenchmark(IGraph graph, Type routerType, int locality, int noOfQueries) {
334      Console.WriteLine("Benchmark Routing Algrithm BEGIN ------------------");
335      Stopwatch sw;
336      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
337
338      Console.Write("Generate queries ... ");
339      List<Tuple<long, long>> queries = GenerateSourceTargetPairs(graph, locality, noOfQueries);
340      Console.WriteLine("done.");
341
342      Console.Write("Execute benchmark ... ");
343      List<TimeSpan> times = new List<TimeSpan>(noOfQueries);
344      foreach (Tuple<long, long> pair in queries) {
345        sw = Stopwatch.StartNew();
346        long[] result = router.Calculate(pair.Item1, pair.Item2);
347        sw.Stop();
348        times.Add(sw.Elapsed);
349      }
350      Console.WriteLine("done.\n");
351
352      Console.WriteLine("Results:");
353      PrintStatistics(times);
354
355      Console.WriteLine("===================================================");
356    }
357
358    private static void PrintStatistics(List<TimeSpan> times) {
359      long averageTicks = Convert.ToInt64(times.Average(timeSpan => timeSpan.Ticks));
360      TimeSpan avg = new TimeSpan(averageTicks);
361      TimeSpan min = times.Min();
362      TimeSpan max = times.Max();
363      TimeSpan total = times.Aggregate(TimeSpan.Zero, (sum, value) => sum.Add(value));
364
365      Console.WriteLine("Min:\t" + min);
366      Console.WriteLine("Max:\t" + max);
367      Console.WriteLine("Avg:\t" + avg);
368      Console.WriteLine("Total:\t" + total);
369      Console.WriteLine("Count:\t" + times.Count);
370
371    }
372  }
373}
Note: See TracBrowser for help on using the repository browser.