Free cookie consent management tool by TermsFeed Policy Generator

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

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

#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

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