Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8481


Ignore:
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:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV2.cs

    r8429 r8481  
    9999      return route;
    100100    }
    101   }
    102101
    103   class NodeData : IComparable<NodeData> {
    104     public long Node { get; set; }
    105     public float Costs { get; set; }
     102    private class NodeData : IComparable<NodeData> {
     103      public long Node { get; set; }
     104      public float Costs { get; set; }
    106105
    107     public NodeData(long nodeId, float f) {
    108       Node = nodeId;
    109       Costs = f;
     106      public NodeData(long nodeId, float f) {
     107        Node = nodeId;
     108        Costs = f;
     109      }
     110
     111      #region IComparable<NodeData> Members
     112
     113      public int CompareTo(NodeData other) {
     114        return this.Costs > other.Costs ? 1 : this.Costs < other.Costs ? -1 : 0;
     115      }
     116
     117      #endregion
    110118    }
    111 
    112     #region IComparable<NodeData> Members
    113 
    114     public int CompareTo(NodeData other) {
    115       return this.Costs > other.Costs ? 1 : this.Costs < other.Costs ? -1 : 0;
    116     }
    117 
    118     #endregion
    119119  }
    120120}
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs

    r8461 r8481  
    7676
    7777    private void FindMinimalWeight(long nodeId) {
     78      //if (nodeId == 274265932) {
     79      //  Console.WriteLine();
     80      //}
    7881      Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
    7982      foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

    r8461 r8481  
    6060    <Compile Include="AStarAlgorithmV2.cs" />
    6161    <Compile Include="BidirectionalDijkstraAlgorithm.cs" />
     62    <Compile Include="AStarAlgorithmV3.cs" />
     63    <Compile Include="BidirectionalDijkstraAlgorithmV2.cs" />
    6264    <Compile Include="DijkstraAlgorithmV2.cs" />
    6365    <Compile Include="DijkstraAlgorithm.cs" />
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

    r8462 r8481  
    55using System.Xml;
    66using HeuristicLab.Algorithms.GraphRouting;
     7using HeuristicLab.Problems.RoutePlanning.DIMACS;
    78using HeuristicLab.Problems.RoutePlanning.Graph;
    89using HeuristicLab.Problems.RoutePlanning.Osm;
     
    2324      string file7 = @"C:\dev\osmfiles\austria.highway.osm";
    2425
    25       IDataSource ds = TestLoad(file5);
    26       OsmGraph graph = new OsmGraph(ds);
    27       IGraph graphNew = TestGetRoutingGraph(ds);
    28       TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
    29       TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
     26      string fileNYArcs = @"C:\dev\DIMACSfiles\USA-road-t.NY.gr.gz";
     27      string fileNYCoords = @"C:\dev\DIMACSfiles\USA-road-d.NY.co.gz";
     28
     29      //IDataSource ds = TestLoad(file5);
     30      //OsmGraph graph = new OsmGraph(ds);
     31      //IGraph graphNew = TestGetRoutingGraph(ds);
     32
     33      IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
     34
     35      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
     36      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
    3037      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
    3138      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
     39      //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
     40      //TestRouter(new BidrectionalDijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
    3241      //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
    3342      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
    34       //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
     43      //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
    3544
    3645      //TestRouter(new AStarAlgorithmV2(graph), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
     46      //TestRouter(new AStarAlgorithmV3(graphNew), 346151602, 33196510, false); // bregenz (bahnhofstr) - wien (stepansplatz)
    3747
    3848      //TestLoadAndRouter(file6, typeof(DijkstraAlgorithm), 529102170, 31372732, false, false); // inz - hgb
     
    5060      //TestLoadAndRouter(file6, typeof(BidrectionalDijkstraAlgorithm), 529102170, 31372732, false, true); // inz - hgb
    5161
    52 
    53 
    54 
     62      //TestLoadAndRouterNew(file6, typeof(DijkstraAlgorithmV2), 529102170, 31372732, false, true);
     63      //TestLoadAndRouterNew(file6, typeof(BidrectionalDijkstraAlgorithmV2), 529102170, 31372732, false, true);
     64      //TestLoadAndRouterNew(file6, typeof(AStarAlgorithmV3), 529102170, 31372732, false, true);
    5565
    5666      System.Console.Read();
     
    129139        Console.WriteLine("Result file: {0}", resultFile);
    130140        WriteGPXFile(graph, result, resultFile);
     141      }
     142      Console.WriteLine("===================================================");
     143      Console.WriteLine();
     144    }
     145
     146    private static void TestLoadAndRouterNew(string filepath, Type routerType, long sourceNodeId, long targetNodeId, bool showResult, bool writeResultFile) {
     147      FileInfo file = new FileInfo(filepath);
     148      Console.WriteLine("Test Load and Route BEGIN -------------------------");
     149      Console.WriteLine("File name: {0}", file.Name);
     150      Console.WriteLine();
     151      Console.Write("Loading data ... ");
     152      var sw = Stopwatch.StartNew();
     153      XmlDataSource xmlDs = new XmlDataSource(filepath);
     154      sw.Stop();
     155      Console.WriteLine("done.");
     156      Console.WriteLine("Loading Time: {0}", sw.Elapsed);
     157      Console.WriteLine();
     158      IGraph graph = xmlDs.GetRoutingGraph();
     159      IRouter router = (IRouter)Activator.CreateInstance(routerType, graph);
     160      Console.Write("Calculate route ... ");
     161      sw = Stopwatch.StartNew();
     162      long[] result = router.Calculate(sourceNodeId, targetNodeId);
     163      sw.Stop();
     164      Console.WriteLine("done.");
     165      Console.WriteLine("Execution Time: {0}", sw.Elapsed);
     166      Console.WriteLine();
     167      if (showResult) {
     168        Console.WriteLine("Result: ");
     169        foreach (long i in result) System.Console.Write(i + "; ");
     170        Console.WriteLine();
     171        Console.WriteLine();
     172      }
     173      if (writeResultFile) {
     174        string dt = DateTime.Now.ToString("yyyyMMddhhmmss_");
     175        string fn = Path.GetFileNameWithoutExtension(file.Name);
     176        string resultFile = dt + fn + "_" + sourceNodeId + "-" + targetNodeId + ".gpx";
     177        Console.WriteLine("Result file: {0}", resultFile);
     178        WriteGPXFileNew(graph, result, resultFile);
    131179      }
    132180      Console.WriteLine("===================================================");
     
    180228    }
    181229
     230    private static void WriteGPXFileNew(IGraph graph, long[] route, string file) {
     231      XmlWriterSettings settings = new XmlWriterSettings();
     232      settings.Indent = true;
     233      settings.IndentChars = ("   ");
     234
     235      using (XmlWriter writer = XmlWriter.Create(file, settings)) {
     236        writer.WriteStartElement("gpx", "http://www.topografix.com/GPX/1/0");
     237        writer.WriteAttributeString("version", "1.1");
     238        writer.WriteAttributeString("creator", "cloudia");
     239
     240        foreach (long nodeId in route) {
     241          Vertex node = graph.GetVertex(nodeId);
     242          writer.WriteStartElement("wpt");
     243          writer.WriteAttributeString("lat", XmlConvert.ToString(node.Latitude));
     244          writer.WriteAttributeString("lon", XmlConvert.ToString(node.Logitude));
     245          writer.WriteEndElement(); // wpt
     246        }
     247
     248        //writer.WriteStartElement("rte");
     249        //foreach (long nodeId in route) {
     250        //  Vertex<Node> node = graph.GetVertex(nodeId);
     251        //  writer.WriteStartElement("rtept");
     252        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
     253        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
     254        //  writer.WriteEndElement(); // rtept
     255        //}
     256        //writer.WriteEndElement(); // rte
     257
     258        //writer.WriteStartElement("trk");
     259        //writer.WriteElementString("name", "RoutePath");
     260        ////writer.WriteEndElement(); // name
     261        //writer.WriteStartElement("trkseq");
     262        //foreach (long nodeId in route) {
     263        //  Vertex<Node> node = graph.GetVertex(nodeId);
     264        //  writer.WriteStartElement("trkpt");
     265        //  writer.WriteAttributeString("lat", XmlConvert.ToString(node.Node.Latitude));
     266        //  writer.WriteAttributeString("lon", XmlConvert.ToString(node.Node.Longitude));
     267        //  writer.WriteEndElement(); // trkpt
     268        //}
     269        //writer.WriteEndElement(); // trkseq
     270        //writer.WriteEndElement(); // trk
     271
     272        writer.WriteEndElement(); // gpx
     273      }
     274    }
     275
    182276    private static IGraph TestGetRoutingGraph(IDataSource ds) {
    183277      Console.WriteLine("Test GetRoutingGraph BEGIN ------------------------");
Note: See TracChangeset for help on using the changeset viewer.