Free cookie consent management tool by TermsFeed Policy Generator

source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV5.cs @ 14604

Last change on this file since 14604 was 8527, checked in by spimming, 12 years ago

#1894:

  • introduced heap interface
  • various heap implementation used as priority queues
  • very simple logger added
  • various versions of Astar algorithm
File size: 4.4 KB
Line 
1
2using System;
3using System.Collections.Generic;
4using HeuristicLab.Algorithms.GraphRouting.Interfaces;
5using HeuristicLab.Algorithms.GraphRouting.PriorityQueues;
6using HeuristicLab.Problems.RoutePlanning.Interfaces;
7using HeuristicLab.Problems.RoutePlanning.RoutingGraph;
8namespace HeuristicLab.Algorithms.GraphRouting {
9  public class AStarAlgorithmV5 : IRouter {
10    private IGraph graph;
11    private ICostCalculator costCalculator;
12
13    private Dictionary<long, float> distances;
14    private Dictionary<long, long> predecessors;
15    private List<long> closedList;
16    private HashSet<long> closedListLookup;
17
18    private HashSet<long> openListLookup;
19    private IHeap<float, long> openList;
20
21    public AStarAlgorithmV5(IGraph graph)
22      : this(graph, new TravelTimeCostCalculator()) {
23    }
24
25    public AStarAlgorithmV5(IGraph graph, ICostCalculator costCalc) {
26      this.graph = graph;
27      this.costCalculator = costCalc;
28    }
29
30    #region IRouter Members
31
32    public long[] Calculate(long sourceNodeId, long targetNodeId) {
33      distances = new Dictionary<long, float>();
34      predecessors = new Dictionary<long, long>();
35
36      closedList = new List<long>();
37      closedListLookup = new HashSet<long>();
38
39      //openList = new BinHeap<float, long>(300000);
40      openList = new BinomialHeap<float, long>();
41      //openList = new NaivePriorityQueue<float, long>();
42      openListLookup = new HashSet<long>();
43
44      long currentNode = sourceNodeId;
45
46      openList.Insert(0, currentNode);
47      openListLookup.Add(currentNode);
48      distances.Add(currentNode, 0);
49
50      while (openList.Size > 0) {
51        // get the node form the open list having the lowest score
52
53        //long dataId = openList.PeekMinValue();
54        //float dataF = openList.PeekMinKey();
55
56        KeyValuePair<float, long> data = openList.PeekMin();
57        long dataId = data.Value;
58        float dataF = data.Key;
59        currentNode = dataId;
60
61        if (currentNode == targetNodeId) {
62          return ReconstructPath(currentNode).ToArray();
63        }
64
65        // remove current from open list
66        openList.RemoveMin();
67        openListLookup.Remove(currentNode);
68
69        // add current to closed list
70        closedList.Add(currentNode);
71        closedListLookup.Add(currentNode);
72
73        //--------------
74        //Logger.LogToFile("cn = " + currentNode + " (" + dataF + ")");
75        //--------------
76
77        Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(currentNode);
78        foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
79          if (closedListLookup.Contains(neighbor.Key))
80            continue;
81
82          Vertex vn = graph.GetVertex(neighbor.Key);
83          Vertex vt = graph.GetVertex(targetNodeId);
84          float costsFromStart = GetDistance(currentNode) + neighbor.Value;
85          float f = costsFromStart + costCalculator.EstimatedCosts(vn, vt);
86
87          //--------------
88          //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + costsFromStart + " / " + f + ")");
89          //--------------
90
91          bool isInOpenList = openListLookup.Contains(neighbor.Key);
92          if (!isInOpenList || costsFromStart < GetDistance(neighbor.Key)) {
93            if (!isInOpenList) {
94              openList.Insert(f, neighbor.Key);
95              openListLookup.Add(neighbor.Key);
96            } else {
97              openList.DecreaseKey(f, neighbor.Key);
98            }
99            distances[neighbor.Key] = costsFromStart;
100            predecessors[neighbor.Key] = currentNode;
101          }
102        }
103        //--------------
104        //Logger.LogToFile("");
105        //--------------
106      }
107      throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
108    }
109
110    #endregion
111
112    private float GetDistance(long id) {
113      float d;
114      if (distances.TryGetValue(id, out d)) {
115        return d;
116      } else { return float.MaxValue; }
117    }
118
119    private List<long> ReconstructPath(long nodeId) {
120      List<long> route = new List<long>();
121      long current = nodeId;
122      long next;
123
124      if (!predecessors.TryGetValue(current, out next)) {
125        return null;
126      }
127      route.Add(current);
128      while (predecessors.TryGetValue(current, out next)) {
129        current = predecessors[current];
130        route.Add(current);
131      }
132      route.Reverse();
133      return route;
134    }
135  }
136}
Note: See TracBrowser for help on using the repository browser.