Changeset 8362


Ignore:
Timestamp:
07/30/12 17:33:52 (7 years ago)
Author:
spimming
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithm.cs

    r8356 r8362  
    1010    private Dictionary<long, long> predecessors;
    1111    private List<long> closedList;
     12    private HashSet<long> closedListLookup;
    1213    //private PriorityQueueOld<float, long> openList;
    1314    private PriorityQueue<float, long> openList;
     
    2324      predecessors = new Dictionary<long, long>();
    2425      closedList = new List<long>();
     26      closedListLookup = new HashSet<long>();
     27
    2528      //openList = new PriorityQueueOld<float, long>();
    26       openList = new PriorityQueue<float, long>(new MyComparer());
     29      openList = new PriorityQueue<float, long>(new Comparer());
    2730
    2831      long currentNode = sourceNodeId;
     
    4144        Dictionary<long, float> currentNeighbors = graph.GetNeighbors(currentNode);
    4245        foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
    43           if (closedList.Contains(neighbor.Key))
     46          //if (closedList.Contains(neighbor.Key))
     47          //  continue;
     48          if (closedListLookup.Contains(neighbor.Key))
    4449            continue;
    4550
     
    6065        }
    6166        closedList.Add(currentNode);
     67        closedListLookup.Add(currentNode);
    6268      }
    6369      throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
     
    9298  }
    9399
    94   class MyComparer : IComparer<float> {
     100  class Comparer : IComparer<float> {
    95101    public int Compare(float item1, float item2) {
    96102      return item1 > item2 ? 1 : item1 < item2 ? -1 : 0;
    97 
    98       // inverted comparison
    99       //return item1 < item2 ? 1 : item1 > item2 ? -1 : 0;
    100103    }
    101104  }
Note: See TracChangeset for help on using the changeset viewer.