Changeset 8640 for branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs

Timestamp:

09/13/12 10:34:51 (12 years ago)

Author:

spimming

Message:

#1894:

• Included costCalculator in a star search
• restructured and renamed Dijkstra algorithm
• Added code comments to FibonacciHeap

File:

• branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs (modified) (5 diffs)

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs

@@ -4 +4 @@
 using HeuristicLab.Algorithms.GraphRouting.Interfaces;
 using HeuristicLab.Problems.RoutePlanning.Interfaces;
+using HeuristicLab.Problems.RoutePlanning.RoutingGraph;
 namespace HeuristicLab.Algorithms.GraphRouting {
   public class AStarAlgorithmV3 : IRouter {
     private IGraph graph;
+    private ICostCalculator costCalculator;
 
     private Dictionary<long, float> distances;
@@ -15 +17 @@
     private Dictionary<long, NodeData> openListLookup;
 
-    public AStarAlgorithmV3(IGraph graph) {
+    public AStarAlgorithmV3(IGraph graph)
+      : this(graph, new TravelTimeCostCalculator()) {
+    }
+
+    public AStarAlgorithmV3(IGraph graph, ICostCalculator costCalc) {
       this.graph = graph;
+      this.costCalculator = costCalc;
     }
 
@@ -36 +43 @@
       distances.Add(currentNode, 0);
 
+      int i = 0;
       while (openList.Count > 0) {
+
         NodeData data = openList.Min;
+        //Console.Write(i + ": (" + openList.Count + "/");
         openList.Remove(data);
+        //Console.Write(openList.Count + ") - (" + openListLookup.Count + "/");
         openListLookup.Remove(data.Node);
+        //Console.WriteLine(openListLookup.Count + ")");
         currentNode = data.Node;
         if (currentNode == targetNodeId) {
           return ReconstructPath(currentNode).ToArray();
         }
+
+        //if (openList.Count != openListLookup.Count) {
+        //  Console.WriteLine();
+        //} else {
+        //  Console.Write(".");
+        //}
 
         Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(currentNode);
@@ -58 +76 @@
           predecessors[neighbor.Key] = currentNode;
 
-          float f = costsFromStart + graph.EstimatedCosts(neighbor.Key, targetNodeId);
+          Vertex vertNeigh = graph.GetVertex(neighbor.Key);
+          Vertex vertTarget = graph.GetVertex(targetNodeId);
+          float f = costsFromStart + costCalculator.EstimatedCosts(vertNeigh, vertTarget);
 
           if (openListLookup.ContainsKey(neighbor.Key)) {
@@ -66 +86 @@
 
           NodeData newNode = new NodeData(neighbor.Key, f);
-          openList.Add(newNode);
+          openList.Add(newNode);  // wenn f bereits vorhanden -> kein add: openList.Contains(new NodeData(123, 0.2973786f))
           openListLookup.Add(newNode.Node, newNode);
         }
         closedList.Add(currentNode);
         closedListLookup.Add(currentNode);
+        i++;
       }
       throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));