Changeset 8640

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

Location:

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3

Files:

• AStarAlgorithmV3.cs (modified) (5 diffs)
• DijkstraAlgorithm.cs (added)
• DijkstraAlgorithmV2.cs (deleted)
• DijkstraNoDecAlgorithm.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.GraphRouting.csproj (modified) (1 diff)
• NaiveDijkstraAlgorithm.cs (added)
• PriorityQueues/FibonacciHeap.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));

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

@@ -3 +3 @@
 using System.Collections.Generic;
 using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+using HeuristicLab.Problems.RoutePlanning.Interfaces;
 using HeuristicLab.Algorithms.GraphRouting.PriorityQueues;
-using HeuristicLab.Problems.RoutePlanning.Interfaces;
 namespace HeuristicLab.Algorithms.GraphRouting {
   public class DijkstraNoDecAlgorithm : IRouter {
@@ -19 +19 @@
 
     public long[] Calculate(long sourceNodeId, long targetNodeId) {
-      unvisitedNodes = new BinHeap<float, long>(1000000);      // unvisited
+      unvisitedNodes = new NaivePriorityQueue<float, long>();
+      //unvisitedNodes = new BinaryHeap<float, long>(1000000);      // unvisited
       //unvisitedNodes = new BinomialHeap<float, long>();    // unvisited
-      //unvisitedNodes = new BinaryHeap<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new BinaryHeapV2<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new BinaryHeapV3<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new Heap4<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new FibonacciHeap<float, long>();   // unvisited
       distances = new Dictionary<long, float>();
       predecessors = new Dictionary<long, long>();
@@ -41 +45 @@
         currentWeight = data.Key;
 
+        //--------------
+        //Logger.LogToFile("cn = " + currentNode + " (" + currentWeight + ")");
+        //--------------
+
         if (currentNode == targetNodeId) {
           break;
@@ -49 +57 @@
           RelaxNeighbors(currentNode, currentWeight);
         }
+
+        //--------------
+        //Logger.LogToFile("");
+        //--------------
       }
 
@@ -67 +79 @@
           predecessors[neighbor.Key] = nodeId;
           unvisitedNodes.Insert(totalWeight, neighbor.Key);
+
+          //--------------
+          //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + totalWeight + ")");
+          //--------------
         }
       }

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

@@ -61 +61 @@
     <Compile Include="AStarAlgorithmV4.cs" />
     <Compile Include="AStarAlgorithmV5.cs" />
+    <Compile Include="DijkstraAlgorithm.cs" />
     <Compile Include="DijkstraNoDecAlgorithm.cs" />
-    <Compile Include="DijkstraAlgorithmV2.cs" />
+    <Compile Include="NaiveDijkstraAlgorithm.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />
     <Compile Include="Interfaces\IHeap.cs" />

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs

@@ -47 +47 @@
         min = n;
       } else {
+        // concateneate the root list (becoming left sibling of root)
         n.Right = min;
         n.Left = min.Left;
         n.Right.Left = n;
         n.Left.Right = n;
+        // update point of minimum if necessary
         if (n.Key.CompareTo(min.Key) < 0) {
           min = n;
@@ -103 +105 @@
 
     private void Link(HeapNode y, HeapNode z) {
+      // remove y from the root list
       y.Left.Right = y.Right;
       y.Right.Left = y.Left;
 
+      // make y a child of x, ...
       y.Parent = z;
       if (z.Child == null) {
@@ -117 +121 @@
         y.Right.Left = y;
       }
+
+      // ... incrementing degree[x]
       z.Degree++;
       y.Mark = false;
@@ -122 +128 @@
 
     private void Consolidate() {
-      //TODO: explain magic number
-      HeapNode[] A = new HeapNode[45];
+      int dn = (int)Math.Floor(Math.Log(size) / Math.Log(2)) + 1; // log2size[Heap]
+      HeapNode[] A = new HeapNode[dn];  // consolidation array
       HeapNode start = min;
       HeapNode w = min;
 
+      // for each node w in the root list
       do {
         HeapNode x = w;
@@ -157 +164 @@
       min = null;
 
-      for (int i = 0; i < 45; i++) {
+      // find the new minimum key
+      for (int i = 0; i < dn; i++) {
         if (A[i] != null) {
           HeapNode n = A[i];