[8293] | 1 |
|
---|
[8314] | 2 | using System;
|
---|
[8509] | 3 | using System.Collections.Generic;
|
---|
[8316] | 4 | using System.Diagnostics;
|
---|
| 5 | using System.IO;
|
---|
[8509] | 6 | using System.Linq;
|
---|
[8315] | 7 | using System.Xml;
|
---|
[8314] | 8 | using HeuristicLab.Algorithms.GraphRouting;
|
---|
[8315] | 9 | using HeuristicLab.Problems.RoutePlanning.Graph;
|
---|
| 10 | using HeuristicLab.Problems.RoutePlanning.Osm;
|
---|
[8293] | 11 | using HeuristicLab.Problems.RoutePlanning.Osm.Data;
|
---|
| 12 | namespace HeuristicLab.Problems.RoutePlanning.Test {
|
---|
| 13 | class Program {
|
---|
| 14 | static void Main(string[] args) {
|
---|
[8408] | 15 | // For testing openstreetmap data is used
|
---|
| 16 | // http://www.openstreetmap.org
|
---|
| 17 | // Map data © OpenStreetMap contributors, CC BY-SA
|
---|
| 18 |
|
---|
[8316] | 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";
|
---|
[8462] | 25 | string file7 = @"C:\dev\osmfiles\austria.highway.osm";
|
---|
[8504] | 26 | string file8 = @"C:\dev\osmfiles\vorarlberg.highway.osm";
|
---|
[8314] | 27 |
|
---|
[8481] | 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 |
|
---|
[8504] | 31 | //IDataSource ds = TestLoad(typeof(XmlDataSource), file7);
|
---|
[8514] | 32 | //IDataSource ds = TestLoad(typeof(OsmDataSource), file6);
|
---|
[8509] | 33 | //OsmGraph graph = new OsmGraph(ds);
|
---|
| 34 |
|
---|
[8481] | 35 | //IGraph graphNew = TestGetRoutingGraph(ds);
|
---|
[8514] | 36 | //ExecuteBenchmark(graphNew, typeof(AStarAlgorithmV3), 262144, 20);
|
---|
[8481] | 37 |
|
---|
[8514] | 38 | //IRouter router = new AStarAlgorithmV3(graphNew);
|
---|
| 39 | //long[] r = router.Calculate(266733493, 986825165);
|
---|
| 40 | ////long[] r = router.Calculate(998717680, 986825165);
|
---|
| 41 |
|
---|
[8504] | 42 | //IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
|
---|
| 43 | //IDataSource ds = new OsmDataSource(file5);
|
---|
[8481] | 44 |
|
---|
[8509] | 45 | //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
|
---|
[8481] | 46 | //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
|
---|
[8509] | 47 | //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
|
---|
[8462] | 48 | //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
|
---|
[8509] | 49 | //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
|
---|
[8481] | 50 | //TestRouter(new BidrectionalDijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
|
---|
[8462] | 51 | //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
|
---|
[8509] | 52 | //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
|
---|
[8481] | 53 | //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
|
---|
[8408] | 54 |
|
---|
[8504] | 55 | //TestRouter(new AStarAlgorithmV2(graph), 763113382, 1078628481, false); // bregenz (bahnhofstr) - podersdorf (??)
|
---|
| 56 | //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
|
---|
[8462] | 57 | //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
|
---|
| 58 |
|
---|
[8504] | 59 | //TestRouter(new AStarAlgorithmV2(graph), 32044987, 261576106, false); //vorarblberg
|
---|
| 60 | //TestRouter(new AStarAlgorithmV3(graphNew), 32044987, 261576106, false); //vorarblberg
|
---|
| 61 |
|
---|
[8408] | 62 | //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
|
---|
| 63 | //TestLoadAndRouter(file6, typeof(AStarAlgorithm), 529102170, 31372732, false, false); // inz - hgb
|
---|
[8426] | 64 | //TestLoadAndRouter(file6, typeof(AStarAlgorithmV2), 529102170, 31372732, false, true); // inz - hgb
|
---|
[8408] | 65 |
|
---|
[8426] | 66 | //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
|
---|
[8462] | 67 | //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
|
---|
[8426] | 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 |
|
---|
[8423] | 72 | //TestLoadAndRouter(file5, typeof(DijkstraAlgorithm), 529102170, 1001363194, true, false);
|
---|
| 73 | //TestLoadAndRouter(file5, typeof(BidrectionalDijkstraAlgorithm), 529102170, 1001363194, true, true);
|
---|
[8426] | 74 | //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
|
---|
[8423] | 75 |
|
---|
[8514] | 76 | TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true); // inz - hgb
|
---|
[8481] | 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);
|
---|
[8462] | 80 |
|
---|
[8504] | 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 |
|
---|
[8509] | 84 | //TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true); //vorarblberg
|
---|
[8504] | 85 |
|
---|
[8314] | 86 | System.Console.Read();
|
---|
| 87 | }
|
---|
| 88 |
|
---|
[8408] | 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 |
|
---|
[8504] | 111 | private static IDataSource TestLoad(Type dsType, params string[] paths) {
|
---|
| 112 | FileInfo file = new FileInfo(paths[0]);
|
---|
[8408] | 113 | Console.WriteLine("Test Load Data BEGIN ------------------------------");
|
---|
[8316] | 114 | Console.WriteLine("File name: {0}", file.Name);
|
---|
| 115 | Console.WriteLine();
|
---|
[8314] | 116 | Console.Write("Loading data ... ");
|
---|
[8316] | 117 | var sw = Stopwatch.StartNew();
|
---|
[8504] | 118 | IDataSource ds = (IDataSource)Activator.CreateInstance(dsType, paths);
|
---|
[8316] | 119 | sw.Stop();
|
---|
[8314] | 120 | Console.WriteLine("done.");
|
---|
[8408] | 121 | Console.WriteLine("Time: {0}", sw.Elapsed);
|
---|
| 122 | Console.WriteLine();
|
---|
| 123 | Console.WriteLine("===================================================");
|
---|
| 124 | Console.WriteLine();
|
---|
[8504] | 125 | return ds;
|
---|
[8408] | 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.");
|
---|
[8316] | 138 | Console.WriteLine("Loading Time: {0}", sw.Elapsed);
|
---|
| 139 | Console.WriteLine();
|
---|
[8429] | 140 | OsmGraph graph = new OsmGraph(xmlDs);
|
---|
[8408] | 141 | IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
|
---|
[8314] | 142 | Console.Write("Calculate route ... ");
|
---|
[8316] | 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);
|
---|
[8314] | 148 | Console.WriteLine();
|
---|
[8316] | 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 | }
|
---|
[8408] | 162 | Console.WriteLine("===================================================");
|
---|
[8316] | 163 | Console.WriteLine();
|
---|
[8293] | 164 | }
|
---|
[8315] | 165 |
|
---|
[8481] | 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();
|
---|
[8514] | 173 | //XmlDataSource xmlDs = new XmlDataSource(filepath);
|
---|
| 174 | IDataSource xmlDs = new OsmDataSource(filepath);
|
---|
[8481] | 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 |
|
---|
[8429] | 205 | private static void WriteGPXFile(OsmGraph graph, long[] route, string file) {
|
---|
[8315] | 206 | XmlWriterSettings settings = new XmlWriterSettings();
|
---|
| 207 | settings.Indent = true;
|
---|
| 208 | settings.IndentChars = (" ");
|
---|
| 209 |
|
---|
[8316] | 210 | using (XmlWriter writer = XmlWriter.Create(file, settings)) {
|
---|
[8315] | 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) {
|
---|
[8434] | 216 | OsmVertex<Node> node = graph.GetVertex(nodeId);
|
---|
[8315] | 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 | }
|
---|
[8462] | 250 |
|
---|
[8481] | 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 |
|
---|
[8462] | 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 | }
|
---|
[8509] | 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 | }
|
---|
[8293] | 372 | }
|
---|
| 373 | }
|
---|