Changeset 8640 for branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues

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/PriorityQueues/FibonacciHeap.cs (modified) (5 diffs)

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];