- Timestamp:
- 07/27/12 16:34:45 (12 years ago)
- Location:
- branches/RoutePlanning
- Files:
-
- 1 added
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithm.cs
r8321 r8350 4 4 using HeuristicLab.Problems.RoutePlanning.Graph; 5 5 namespace HeuristicLab.Algorithms.GraphRouting { 6 class AStarAlgorithm : IRouter {6 public class AStarAlgorithm : IRouter { 7 7 private Graph graph; 8 8 … … 10 10 private Dictionary<long, long> predecessors; 11 11 private List<float> closedList = new List<float>(); 12 //private PriorityQueueOld<float, long> openList; 12 13 private PriorityQueue<float, long> openList; 13 14 … … 22 23 predecessors = new Dictionary<long, long>(); 23 24 closedList = new List<float>(); 24 openList = new PriorityQueue<float, long>(); 25 //openList = new PriorityQueueOld<float, long>(); 26 openList = new PriorityQueue<float, long>(new MyComparer()); 25 27 26 28 long currentNode = sourceNodeId; 27 29 28 openList.Enqueue(currentNode, 0); 30 //openList.Enqueue(currentNode, 0); 31 openList.Enqueue(0, currentNode); 29 32 distances.Add(currentNode, 0); 30 33 31 34 while (openList.Count > 0) { 32 currentNode = openList.Dequeue(); 35 //currentNode = openList.Dequeue(); 36 currentNode = openList.DequeueValue(); 33 37 if (currentNode == targetNodeId) { 34 38 return ReconstructPath(currentNode).ToArray(); … … 52 56 openList.Remove(neighbor.Key); 53 57 } 54 openList.Enqueue(neighbor.Key, f); 58 //openList.Enqueue(neighbor.Key, f); 59 openList.Enqueue(f, neighbor.Key); 55 60 } 56 61 } … … 85 90 } 86 91 } 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 } 87 101 } -
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj
r8321 r8350 64 64 <Compile Include="Plugin.cs" /> 65 65 <Compile Include="PriorityQueue.cs" /> 66 <Compile Include="PriorityQueueOld.cs" /> 66 67 <Compile Include="Properties\AssemblyInfo.cs" /> 67 68 </ItemGroup> -
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueue.cs
r8321 r8350 1 1 2 2 using System; 3 using System.Collections; 3 4 using System.Collections.Generic; 4 5 namespace 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; 8 10 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); 11 67 } 12 68 13 69 public int Count { 14 get { return list.Count; }70 get { return heap.Count; } 15 71 } 16 72 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; } 20 75 } 21 76 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; 26 92 } 27 93 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); 30 97 } 31 98 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 } 39 154 } 40 155 } 41 if (delete) {42 return list.Remove(toDelete.Key);43 }44 return false;45 156 } 46 157 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 47 180 } 48 181 } -
branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/HeuristicLab.Problems.RoutePlanning.Test.csproj
r8314 r8350 16 16 </PropertyGroup> 17 17 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' "> 18 <PlatformTarget> x86</PlatformTarget>18 <PlatformTarget>AnyCPU</PlatformTarget> 19 19 <DebugSymbols>true</DebugSymbols> 20 20 <DebugType>full</DebugType> … … 33 33 <ErrorReport>prompt</ErrorReport> 34 34 <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> 35 67 </PropertyGroup> 36 68 <ItemGroup> -
branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning.Test/Program.cs
r8316 r8350 37 37 Console.WriteLine(); 38 38 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); 40 41 Console.Write("Calculate route ... "); 41 42 sw = Stopwatch.StartNew(); -
branches/RoutePlanning/RoutePlanning.sln
r8302 r8350 40 40 {0C6B9F99-DBC1-49BE-B90A-36CB86DD1D0C}.Release|Mixed Platforms.Build.0 = Release|Any CPU 41 41 {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 43 44 {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Mixed Platforms.ActiveCfg = Debug|x86 44 45 {004241D1-2127-4489-9DFB-9F7707983371}.Debug|Mixed Platforms.Build.0 = Debug|x86
Note: See TracChangeset
for help on using the changeset viewer.