Changeset 8539

Timestamp:

08/29/12 18:18:53 (12 years ago)

Author:

spimming

Message:

#1894:

• Dijkstra version with no decrease key
• used wrong index in BinHeap implementation
• implement interface in BinaryHeap

Location:

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3

Files:

• DijkstraNoDecAlgorithm.cs (added)
• HeuristicLab.Algorithms.GraphRouting.csproj (modified) (1 diff)
• PriorityQueues/BinHeap.cs (modified) (1 diff)
• PriorityQueues/BinaryHeap.cs (modified) (2 diffs)

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

@@ -61 +61 @@
     <Compile Include="AStarAlgorithmV4.cs" />
     <Compile Include="AStarAlgorithmV5.cs" />
+    <Compile Include="DijkstraNoDecAlgorithm.cs" />
     <Compile Include="DijkstraAlgorithmV2.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />

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

@@ -92 +92 @@
       while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
              (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
-        if ((right >= size - 1) || (data[idx].Key.CompareTo(data[right].Key) == -1)) {
+        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
           Swap(left, idx);
           idx = left;

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

@@ -1 +1 @@
 
 using System;
+using System.Collections.Generic;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
 namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
   // implementation based on C++ version from Peter Sanders
   // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
-  public sealed class BinaryHeap<K, V> where K : IComparable {
+  public sealed class BinaryHeap<K, V> : IHeap<K, V> where K : IComparable {
     private class KNElement {
       public K Key { get; set; }
@@ -31 +33 @@
     public int Size {
       get { return size; }
+    }
+
+    public KeyValuePair<K, V> PeekMin() {
+      if (size == 0) {
+        throw new InvalidOperationException("Heap is empty");
+      }
+      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
     }