Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/27/12 16:34:45 (12 years ago)
Author:
spimming
Message:

#1894:

  • new implementation for priority queue
  • based on heap data structure
  • allow multiple keys
  • adapted test program
Location:
branches/RoutePlanning
Files:
1 added
6 edited

Legend:

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

    r8321 r8350  
    44using HeuristicLab.Problems.RoutePlanning.Graph;
    55namespace HeuristicLab.Algorithms.GraphRouting {
    6   class AStarAlgorithm : IRouter {
     6  public class AStarAlgorithm : IRouter {
    77    private Graph graph;
    88
     
    1010    private Dictionary<long, long> predecessors;
    1111    private List<float> closedList = new List<float>();
     12    //private PriorityQueueOld<float, long> openList;
    1213    private PriorityQueue<float, long> openList;
    1314
     
    2223      predecessors = new Dictionary<long, long>();
    2324      closedList = new List<float>();
    24       openList = new PriorityQueue<float, long>();
     25      //openList = new PriorityQueueOld<float, long>();
     26      openList = new PriorityQueue<float, long>(new MyComparer());
    2527
    2628      long currentNode = sourceNodeId;
    2729
    28       openList.Enqueue(currentNode, 0);
     30      //openList.Enqueue(currentNode, 0);
     31      openList.Enqueue(0, currentNode);
    2932      distances.Add(currentNode, 0);
    3033
    3134      while (openList.Count > 0) {
    32         currentNode = openList.Dequeue();
     35        //currentNode = openList.Dequeue();
     36        currentNode = openList.DequeueValue();
    3337        if (currentNode == targetNodeId) {
    3438          return ReconstructPath(currentNode).ToArray();
     
    5256            openList.Remove(neighbor.Key);
    5357          }
    54           openList.Enqueue(neighbor.Key, f);
     58          //openList.Enqueue(neighbor.Key, f);
     59          openList.Enqueue(f, neighbor.Key);
    5560        }
    5661      }
     
    8590    }
    8691  }
     92
     93  class MyComparer : IComparer<float> {
     94    public int Compare(float item1, float item2) {
     95      return item1 > item2 ? 1 : item1 < item2 ? -1 : 0;
     96
     97      // inverted comparison
     98      //return item1 < item2 ? 1 : item1 > item2 ? -1 : 0;
     99    }
     100  }
    87101}
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

    r8321 r8350  
    6464    <Compile Include="Plugin.cs" />
    6565    <Compile Include="PriorityQueue.cs" />
     66    <Compile Include="PriorityQueueOld.cs" />
    6667    <Compile Include="Properties\AssemblyInfo.cs" />
    6768  </ItemGroup>
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueue.cs

    r8321 r8350  
    11
    22using System;
     3using System.Collections;
    34using System.Collections.Generic;
    45namespace HeuristicLab.Algorithms.GraphRouting {
    5   public class PriorityQueue<P, T> where P : IComparable {
    6     SortedList<Pair<P>, T> list;
    7     P dummy;
     6  public class PriorityQueue<TPriority, TValue> : ICollection<KeyValuePair<TPriority, TValue>> {
     7    private List<KeyValuePair<TPriority, TValue>> heap;
     8    private Dictionary<TValue, KeyValuePair<TPriority, TValue>> values;
     9    private IComparer<TPriority> comparer;
    810
    9     public PriorityQueue() {
    10       list = new SortedList<Pair<P>, T>(new PairComparer<P>());
     11    #region Constructors
     12
     13    public PriorityQueue(IComparer<TPriority> comparer) {
     14      if (comparer == null)
     15        throw new ArgumentNullException();
     16
     17      heap = new List<KeyValuePair<TPriority, TValue>>();
     18      values = new Dictionary<TValue, KeyValuePair<TPriority, TValue>>();
     19      this.comparer = comparer;
     20    }
     21
     22    #endregion
     23
     24    #region Priority queue methods
     25
     26    public void Enqueue(TPriority priority, TValue value) {
     27      Insert(priority, value);
     28    }
     29
     30    public KeyValuePair<TPriority, TValue> Dequeue() {
     31      if (Count != 0) {
     32        KeyValuePair<TPriority, TValue> item = heap[0];
     33        RemoveRoot();
     34        return item;
     35      } else {
     36        throw new InvalidOperationException("Priority queue is empty");
     37      }
     38    }
     39
     40    public TValue DequeueValue() {
     41      return Dequeue().Value;
     42    }
     43
     44    #endregion
     45
     46    #region ICollection members
     47
     48    public void Add(KeyValuePair<TPriority, TValue> item) {
     49      Enqueue(item.Key, item.Value);
     50    }
     51
     52    public void Clear() {
     53      heap.Clear();
     54      values.Clear();
     55    }
     56
     57    public bool Contains(KeyValuePair<TPriority, TValue> item) {
     58      return heap.Contains(item);
     59    }
     60
     61    public bool Contains(TValue value) {
     62      return values.ContainsKey(value);
     63    }
     64
     65    public void CopyTo(KeyValuePair<TPriority, TValue>[] array, int arrayIndex) {
     66      heap.CopyTo(array, arrayIndex);
    1167    }
    1268
    1369    public int Count {
    14       get { return list.Count; }
     70      get { return heap.Count; }
    1571    }
    1672
    17     public void Enqueue(T item, P priority) {
    18       list.Add(new Pair<P>(priority, dummy), item);
    19       //count++;
     73    public bool IsReadOnly {
     74      get { return false; }
    2075    }
    2176
    22     public T Dequeue() {
    23       T item = list[list.Keys[0]];
    24       list.RemoveAt(0);
    25       return item;
     77    public bool Remove(KeyValuePair<TPriority, TValue> item) {
     78      int idx = heap.IndexOf(item);
     79      if (idx < 0) {
     80        return false;
     81      }
     82
     83      values.Remove(item.Value);
     84
     85      heap[idx] = heap[heap.Count - 1];
     86      heap.RemoveAt(heap.Count - 1);
     87
     88      HeapUp(idx);
     89      HeapDown(idx);
     90
     91      return true;
    2692    }
    2793
    28     public bool Contains(T item) {
    29       return list.ContainsValue(item);
     94    public bool Remove(TValue value) {
     95      KeyValuePair<TPriority, TValue> item = values[value];
     96      return Remove(item);
    3097    }
    3198
    32     public bool Remove(T item) {
    33       bool delete = false;
    34       KeyValuePair<Pair<P>, T> toDelete = new KeyValuePair<Pair<P>, T>();
    35       foreach (var pair in list) {
    36         if (pair.Value.Equals(item)) {
    37           delete = true;
    38           toDelete = pair;
     99    #endregion
     100
     101    #region IEnumerable Members
     102
     103    public IEnumerator<KeyValuePair<TPriority, TValue>> GetEnumerator() {
     104      return heap.GetEnumerator();
     105    }
     106
     107    IEnumerator IEnumerable.GetEnumerator() {
     108      return this.GetEnumerator();
     109    }
     110
     111    #endregion
     112
     113    #region Private methods
     114
     115    private void SwapElements(int pos1, int pos2) {
     116      KeyValuePair<TPriority, TValue> element = heap[pos1];
     117      heap[pos1] = heap[pos2];
     118      heap[pos2] = element;
     119    }
     120
     121    private void Insert(TPriority priority, TValue value) {
     122      KeyValuePair<TPriority, TValue> element = new KeyValuePair<TPriority, TValue>(priority, value);
     123      heap.Add(element);
     124      values.Add(value, element);
     125
     126      HeapUp(heap.Count - 1);
     127    }
     128
     129    private void RemoveRoot() {
     130      if (heap.Count <= 1) {
     131        heap.Clear();
     132        values.Clear();
     133      } else {
     134        KeyValuePair<TPriority, TValue> item = heap[0];
     135        values.Remove(item.Value);
     136
     137        heap[0] = heap[heap.Count - 1];
     138        heap.RemoveAt(heap.Count - 1);
     139
     140        HeapDown(0);
     141      }
     142    }
     143
     144    private void HeapUp(int pos) {
     145      if (pos < heap.Count) {
     146        while (pos > 0) {
     147          int parent = (pos - 1) / 2;
     148          if (comparer.Compare(heap[parent].Key, heap[pos].Key) > 0) {
     149            SwapElements(parent, pos);
     150            pos = parent;
     151          } else {
     152            break;
     153          }
    39154        }
    40155      }
    41       if (delete) {
    42         return list.Remove(toDelete.Key);
    43       }
    44       return false;
    45156    }
    46157
     158    private void HeapDown(int pos) {
     159      while (true) {
     160        int smallest = pos;
     161        int left = 2 * pos + 1;
     162        int right = 2 * pos + 2;
     163        if (left < heap.Count && comparer.Compare(heap[smallest].Key, heap[left].Key) > 0) {
     164          smallest = left;
     165        }
     166        if (right < heap.Count && comparer.Compare(heap[smallest].Key, heap[right].Key) > 0) {
     167          smallest = right;
     168        }
     169
     170        if (smallest != pos) {
     171          SwapElements(smallest, pos);
     172          pos = smallest;
     173        } else {
     174          break;
     175        }
     176      }
     177    }
     178
     179    #endregion
    47180  }
    48181}
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/HeuristicLab.Problems.RoutePlanning.Test.csproj

    r8314 r8350  
    1616  </PropertyGroup>
    1717  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' ">
    18     <PlatformTarget>x86</PlatformTarget>
     18    <PlatformTarget>AnyCPU</PlatformTarget>
    1919    <DebugSymbols>true</DebugSymbols>
    2020    <DebugType>full</DebugType>
     
    3333    <ErrorReport>prompt</ErrorReport>
    3434    <WarningLevel>4</WarningLevel>
     35  </PropertyGroup>
     36  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|AnyCPU'">
     37    <DebugSymbols>true</DebugSymbols>
     38    <OutputPath>bin\Debug\</OutputPath>
     39    <DefineConstants>DEBUG;TRACE</DefineConstants>
     40    <DebugType>full</DebugType>
     41    <PlatformTarget>AnyCPU</PlatformTarget>
     42    <CodeAnalysisLogFile>bin\Debug\HeuristicLab.Problems.RoutePlanning.Test.exe.CodeAnalysisLog.xml</CodeAnalysisLogFile>
     43    <CodeAnalysisUseTypeNameInSuppression>true</CodeAnalysisUseTypeNameInSuppression>
     44    <CodeAnalysisModuleSuppressionsFile>GlobalSuppressions.cs</CodeAnalysisModuleSuppressionsFile>
     45    <ErrorReport>prompt</ErrorReport>
     46    <CodeAnalysisRuleSet>MinimumRecommendedRules.ruleset</CodeAnalysisRuleSet>
     47    <CodeAnalysisRuleSetDirectories>;C:\Program Files (x86)\Microsoft Visual Studio 10.0\Team Tools\Static Analysis Tools\\Rule Sets</CodeAnalysisRuleSetDirectories>
     48    <CodeAnalysisIgnoreBuiltInRuleSets>true</CodeAnalysisIgnoreBuiltInRuleSets>
     49    <CodeAnalysisRuleDirectories>;C:\Program Files (x86)\Microsoft Visual Studio 10.0\Team Tools\Static Analysis Tools\FxCop\\Rules</CodeAnalysisRuleDirectories>
     50    <CodeAnalysisIgnoreBuiltInRules>true</CodeAnalysisIgnoreBuiltInRules>
     51  </PropertyGroup>
     52  <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|AnyCPU'">
     53    <OutputPath>bin\Release\</OutputPath>
     54    <DefineConstants>TRACE</DefineConstants>
     55    <Optimize>true</Optimize>
     56    <DebugType>pdbonly</DebugType>
     57    <PlatformTarget>AnyCPU</PlatformTarget>
     58    <CodeAnalysisLogFile>bin\Release\HeuristicLab.Problems.RoutePlanning.Test.exe.CodeAnalysisLog.xml</CodeAnalysisLogFile>
     59    <CodeAnalysisUseTypeNameInSuppression>true</CodeAnalysisUseTypeNameInSuppression>
     60    <CodeAnalysisModuleSuppressionsFile>GlobalSuppressions.cs</CodeAnalysisModuleSuppressionsFile>
     61    <ErrorReport>prompt</ErrorReport>
     62    <CodeAnalysisRuleSet>MinimumRecommendedRules.ruleset</CodeAnalysisRuleSet>
     63    <CodeAnalysisRuleSetDirectories>;C:\Program Files (x86)\Microsoft Visual Studio 10.0\Team Tools\Static Analysis Tools\\Rule Sets</CodeAnalysisRuleSetDirectories>
     64    <CodeAnalysisIgnoreBuiltInRuleSets>true</CodeAnalysisIgnoreBuiltInRuleSets>
     65    <CodeAnalysisRuleDirectories>;C:\Program Files (x86)\Microsoft Visual Studio 10.0\Team Tools\Static Analysis Tools\FxCop\\Rules</CodeAnalysisRuleDirectories>
     66    <CodeAnalysisIgnoreBuiltInRules>true</CodeAnalysisIgnoreBuiltInRules>
    3567  </PropertyGroup>
    3668  <ItemGroup>
  • branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs

    r8316 r8350  
    3737      Console.WriteLine();
    3838      Graph.Graph graph = new Graph.Graph(xmlDs);
    39       IRouter router = new DijkstraAlgorithm(graph);
     39      //IRouter router = new DijkstraAlgorithm(graph);
     40      IRouter router = new AStarAlgorithm(graph);
    4041      Console.Write("Calculate route ... ");
    4142      sw = Stopwatch.StartNew();
  • branches/RoutePlanning/RoutePlanning.sln

    r8302 r8350  
    4040    {0C6B9F99-DBC1-49BE-B90A-36CB86DD1D0C}.Release|Mixed Platforms.Build.0 = Release|Any CPU
    4141    {0C6B9F99-DBC1-49BE-B90A-36CB86DD1D0C}.Release|x86.ActiveCfg = Release|Any CPU
    42     {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Any CPU.ActiveCfg = Debug|x86
     42    {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     43    {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Any CPU.Build.0 = Debug|Any CPU
    4344    {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Mixed Platforms.ActiveCfg = Debug|x86
    4445    {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Mixed Platforms.Build.0 = Debug|x86
Note: See TracChangeset for help on using the changeset viewer.