Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8509


Ignore:
Timestamp:
08/20/12 17:32:19 (10 years ago)
Author:
spimming
Message:

#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

Location:
branches/RoutePlanning
Files:
5 edited

Legend:

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

    r8481 r8509  
    5353
    5454    #endregion
     55
     56    public long GetNodeIdWithRank(long sourceNodeId, int rank) {
     57      visitedNodes = new HashSet<long>();        // visited
     58      unvisitedNodes = new HashSet<long>();      // unvisited
     59      distances = new Dictionary<long, float>();
     60      predecessors = new Dictionary<long, long>();
     61      int currentRank = 0;
     62
     63
     64      long currentNode = sourceNodeId;
     65      distances.Add(currentNode, 0);
     66      unvisitedNodes.Add(currentNode);
     67
     68      while (unvisitedNodes.Count > 0) {
     69        currentNode = GetMinimumDistance(unvisitedNodes);
     70        visitedNodes.Add(currentNode);
     71        unvisitedNodes.Remove(currentNode);
     72        currentRank++;
     73        if (currentRank == rank) {
     74          break;
     75        }
     76        FindMinimalWeight(currentNode);
     77      }
     78      return currentNode;
     79    }
    5580
    5681    private long GetMinimumDistance(HashSet<long> nodeIds) {
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

    r8504 r8509  
    11
    22using System;
     3using System.Collections.Generic;
    34using System.Diagnostics;
    45using System.IO;
     6using System.Linq;
    57using System.Xml;
    68using HeuristicLab.Algorithms.GraphRouting;
     
    2830
    2931      //IDataSource ds = TestLoad(typeof(XmlDataSource), file7);
    30       IDataSource ds = TestLoad(typeof(OsmDataSource), file5);
    31       OsmGraph graph = new OsmGraph(ds);
     32      IDataSource ds = TestLoad(typeof(OsmDataSource), file6);
     33      //OsmGraph graph = new OsmGraph(ds);
     34
    3235      //IGraph graphNew = TestGetRoutingGraph(ds);
     36      //ExecuteBenchmark(graphNew, typeof(AStarAlgorithmV3), 2048, 1000);
    3337
    3438      //IDataSource ds = new DIMACSDataSource(fileNYCoords, fileNYArcs);
    3539      //IDataSource ds = new OsmDataSource(file5);
    3640
    37       TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
     41      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 1001363194, true);
    3842      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 1001363194, true);
    39       TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
     43      //TestRouter(new DijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
    4044      //TestRouter(new DijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
    41       TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
     45      //TestRouter(new BidrectionalDijkstraAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
    4246      //TestRouter(new BidrectionalDijkstraAlgorithmV2(graphNew), 529102170, 31372732, false); // inz - hgb
    4347      //TestRouter(new AStarAlgorithm(graph), 529102170, 31372732, false); // inz - hgb
    44       TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
     48      //TestRouter(new AStarAlgorithmV2(graph), 529102170, 31372732, false); // inz - hgb
    4549      //TestRouter(new AStarAlgorithmV3(graphNew), 529102170, 31372732, false); // inz - hgb
    4650
     
    7377      //TestLoadAndRouterNew(file7, typeof(AStarAlgorithmV3), 346151602, 33196510, false, true); // bregenz (bahnhofstr) - wien (stepansplatz)
    7478
    75       TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
     79      //TestLoadAndRouter(file8, typeof(AStarAlgorithmV2), 32044987, 261576106, false, true);    //vorarblberg
    7680
    7781      System.Console.Read();
     
    299303      return graph;
    300304    }
     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    }
    301366  }
    302367}
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs

    r8479 r8509  
    2525      vertices.TryGetValue(id, out vertex);
    2626      return vertex;
     27    }
     28
     29    public List<Vertex> GetVertices() {
     30      return new List<Vertex>(vertices.Values);
    2731    }
    2832
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/IGraph.cs

    r8479 r8509  
    55    void AddVertex(Vertex vertex);
    66    Vertex GetVertex(long id);
     7    List<Vertex> GetVertices();
    78    void AddEdge(long startId, long endId);
    89    void AddEdge(Edge<Vertex> edge);
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Osm.Data/OsmDataSource.cs

    r8504 r8509  
    141141      NameTable nt = new NameTable();
    142142      string osmName = nt.Add("osm");
    143       string nodeName = nt.Add("node");
     143      object nodeName = nt.Add("node");
    144144      object tagName = nt.Add("tag");
    145145      object wayName = nt.Add("way");
     
    147147      string lonName = nt.Add("lon");
    148148      string idName = nt.Add("id");
    149       string ndName = nt.Add("nd");
     149      object ndName = nt.Add("nd");
    150150      string refName = nt.Add("ref");
    151151      string kName = nt.Add("k");
     
    166166
    167167          reader.Read();
    168           if (reader.LocalName.Equals(tagName)) {
    169             reader.ReadToFollowing(nodeName, ns);
    170           }
    171         }
    172         while (reader.LocalName.Equals(wayName)) {
     168          //if (reader.LocalName.Equals(tagName)) {
     169          if (ReferenceEquals(tagName, reader.LocalName)) {
     170            reader.ReadToFollowing((string)nodeName, ns);
     171          }
     172        }
     173        //while (reader.LocalName.Equals(wayName)) {
     174        while (ReferenceEquals(wayName, reader.LocalName)) {
    173175          List<Vertex> way = new List<Vertex>();
    174176          bool missingNodes = false;
     
    177179
    178180          reader.Read();
    179           while (reader.LocalName.Equals(nodeName) || reader.LocalName.Equals(tagName)) {
     181          while (ReferenceEquals(ndName, reader.LocalName) || ReferenceEquals(tagName, reader.LocalName)) {
    180182            if (reader.LocalName.Equals(ndName)) {
    181183              long refNodeId = XmlConvert.ToInt64(reader.GetAttribute(refName, ns));
Note: See TracChangeset for help on using the changeset viewer.