Changeset 8362 for branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting

Timestamp:

07/30/12 17:33:52 (12 years ago)

Author:

spimming

Message:

#1894: use dictionary to check if closed list contains node

File:

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

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

@@ -10 +10 @@
     private Dictionary<long, long> predecessors;
     private List<long> closedList;
+    private HashSet<long> closedListLookup;
     //private PriorityQueueOld<float, long> openList;
     private PriorityQueue<float, long> openList;
@@ -23 +24 @@
       predecessors = new Dictionary<long, long>();
       closedList = new List<long>();
+      closedListLookup = new HashSet<long>();
+
       //openList = new PriorityQueueOld<float, long>();
-      openList = new PriorityQueue<float, long>(new MyComparer());
+      openList = new PriorityQueue<float, long>(new Comparer());
 
       long currentNode = sourceNodeId;
@@ -41 +44 @@
         Dictionary<long, float> currentNeighbors = graph.GetNeighbors(currentNode);
         foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
-          if (closedList.Contains(neighbor.Key))
+          //if (closedList.Contains(neighbor.Key))
+          //  continue;
+          if (closedListLookup.Contains(neighbor.Key))
             continue;
 
@@ -60 +65 @@
         }
         closedList.Add(currentNode);
+        closedListLookup.Add(currentNode);
       }
       throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
@@ -92 +98 @@
   }
 
-  class MyComparer : IComparer<float> {
+  class Comparer : IComparer<float> {
     public int Compare(float item1, float item2) {
       return item1 > item2 ? 1 : item1 < item2 ? -1 : 0;
-
-      // inverted comparison
-      //return item1 < item2 ? 1 : item1 > item2 ? -1 : 0;
     }
   }