00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00014
00015
00016
00017
00019
00020
00021 #include "ShortestPathCalculator.hh"
00022 #include "StableSetSub.hh"
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 ShortestPathCalculator::ShortestPathCalculator(int nNodes, int nEdges,
00037 int* adjPtr, int* adjList,
00038 double* edgeWeight, double bound,
00039 double tol)
00040 {
00041
00042 int i, j;
00043
00044 m_nNodes = nNodes;
00045 m_nEdges = nEdges;
00046
00047 m_adjPtr = new int[m_nNodes+1];
00048 for(i=0; i<m_nNodes+1; i++) m_adjPtr[i] = adjPtr[i];
00049
00050 m_adjList = new int[m_nEdges];
00051 for(j=0; j<m_nEdges; j++) m_adjList[j] = adjList[j];
00052
00053 m_edgeWeight = new double[m_nEdges];
00054 for(j=0; j<m_nEdges; j++) m_edgeWeight[j] = edgeWeight[j];
00055
00056 m_bound = bound;
00057 m_tol = tol;
00058
00059 m_heap = new int[m_nNodes];
00060 m_invHeap = new int[m_nNodes];
00061 m_nodeLabel = new double[m_nNodes];
00062
00063 }
00064
00065
00066
00067
00068
00069 ShortestPathCalculator::~ShortestPathCalculator() {
00070 delete[] m_adjPtr;
00071 delete[] m_adjList;
00072 delete[] m_edgeWeight;
00073
00074 delete[] m_heap;
00075 delete[] m_invHeap;
00076 delete[] m_nodeLabel;
00077 }
00078
00079
00080
00081
00082
00083 double ShortestPathCalculator::calculateShortestPath(int startNode, int endNode,
00084 int* predNode)
00085 {
00086
00087 int i, j;
00088 int currentNode = startNode;
00089 int nextNode;
00090 int child;
00091 int parent;
00092 double minLabel = 0.0;
00093 double nextLabel;
00094
00095 buildHeap(startNode);
00096
00097
00098 while (minLabel < m_bound-m_tol && currentNode!=endNode) {
00099
00100
00101 for (j=m_adjPtr[currentNode]; j<m_adjPtr[currentNode+1]; j++) {
00102 nextNode = m_adjList[j];
00103
00104 if(m_invHeap[nextNode] < m_heapSize) {
00105 nextLabel = minLabel + m_edgeWeight[j];
00106 if(nextLabel < m_nodeLabel[nextNode]) {
00107
00108
00109
00110 child = m_invHeap[nextNode];
00111
00112 while (child != 0) {
00113 parent = (child-1)/2;
00114 if(nextLabel < m_nodeLabel[m_heap[parent]]) {
00115 m_heap[child] = m_heap[parent];
00116 m_invHeap[m_heap[parent]] = child;
00117 child = parent;
00118 }
00119 else break;
00120 }
00121 m_heap[child] = nextNode;
00122 m_invHeap[nextNode] = child;
00123 m_nodeLabel[nextNode] = nextLabel;
00124
00125 predNode[nextNode] = currentNode;
00126 }
00127 }
00128 }
00129
00130 currentNode = extractMin();
00131 minLabel = m_nodeLabel[currentNode];
00132
00133 }
00134
00135 if (currentNode == endNode) {
00136 return minLabel;
00137 }
00138 else {
00139 return m_bound;
00140 }
00141
00142 }
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154 void ShortestPathCalculator::buildHeap(int startNode)
00155 {
00156 int i;
00157
00158 m_heapSize = m_nNodes-1;
00159
00160 for (i=0; i<m_heapSize; i++) {
00161 m_heap[i] = i;
00162 m_invHeap[i] = i;
00163 }
00164 m_heap[m_heapSize] = startNode;
00165 m_heap[startNode] = m_heapSize;
00166 m_invHeap[m_heapSize] = startNode;
00167 m_invHeap[startNode] = m_heapSize;
00168
00169 for (i=0; i<m_nNodes; i++) {
00170 m_nodeLabel[i] = m_bound;
00171 }
00172
00173
00174 }
00175
00176
00177
00178
00179
00180 int ShortestPathCalculator::extractMin() {
00181
00182 m_heapSize--;
00183
00184 int min = m_heap[0];
00185
00186 int insertNode = m_heap[m_heapSize];
00187 double insertLabel = m_nodeLabel[insertNode];
00188
00189 m_heap[m_heapSize] = min;
00190 m_invHeap[min] = m_heapSize;
00191
00192 int parent,firstChild,secondChild,minChild;
00193 double firstLabel,secondLabel,minLabel;
00194
00195 parent = 0;
00196 firstChild = 1;
00197 while(firstChild<m_heapSize) {
00198 firstLabel = m_nodeLabel[m_heap[firstChild]];
00199 secondChild = firstChild+1;
00200 if(secondChild==m_heapSize) {
00201 minChild = firstChild;
00202 minLabel = firstLabel;
00203 }
00204 else {
00205 secondLabel = m_nodeLabel[m_heap[secondChild]];
00206 if(firstLabel < secondLabel) {
00207 minChild = firstChild;
00208 minLabel = firstLabel;
00209 }
00210 else {
00211 minChild = secondChild;
00212 minLabel = secondLabel;
00213 }
00214 }
00215
00216 if(insertLabel < minLabel) break;
00217 else {
00218 m_heap[parent] = m_heap[minChild];
00219 m_invHeap[m_heap[minChild]] = parent;
00220 parent = minChild;
00221 firstChild = 2*parent+1;
00222 }
00223
00224 }
00225
00226 m_heap[parent] = insertNode;
00227 m_invHeap[insertNode] = parent;
00228
00229 return min;
00230
00231 }
00232
00233
00234
00235
00236
00237 void ShortestPathCalculator::changeKey(int node, double label)
00238 {
00239
00240 int child,parent;
00241
00242 child = m_invHeap[node];
00243
00244 while(child != 0) {
00245 parent = (child-1)/2;
00246 if(label < m_nodeLabel[m_heap[parent]]) {
00247 m_heap[child] = m_heap[parent];
00248 m_invHeap[m_heap[parent]] = child;
00249 child = parent;
00250 }
00251 else break;
00252 }
00253 m_heap[child] = node;
00254 m_invHeap[node] = child;
00255 m_nodeLabel[node] = label;
00256
00257 }
00258
00259