C:/Programme/home/Administrator/CD/stableSetCode/ShortestPathCalculator.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : ShortestPathCalculator.cpp
00004 //  Description      :
00005 //  Author           : Marcus Oswald
00006 //  Email            : Marcus.Oswald@informatik.uni-heidelberg.de
00007 //  Copyright        : University of Heidelberg
00008 //  Created on       : Wed Jul 17 10:39:08 2002
00009 //  Last modified by : rebennack
00010 //  Last modified on : 06.10.2005
00011 //  Update count     : 67
00012 //
00014 //
00015 //  Date        Name            Changes/Extensions
00016 //  ----        ----            ------------------
00017 //
00019 
00020 
00021 #include "ShortestPathCalculator.hh"
00022 #include "StableSetSub.hh"
00023 
00024 
00025 
00026 // -----------------------------------------------------------------------------
00027 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00028 // -----------------------------------------------------------------------------
00029 
00030 
00031 // -----------------------------------------------------------------------------
00032 // C o n s t r u c t o r
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;     // Loop variables.
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 // Destructor.
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 // c a l c u l a t e S h o r t e s t P a t h
00082 // -----------------------------------------------------------------------------
00083 double ShortestPathCalculator::calculateShortestPath(int startNode, int endNode,
00084                                                      int* predNode)
00085 {
00086 
00087     int    i, j;                        // Loop variables.
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     // terminate if bound is violated or if shortest path is found
00098     while (minLabel < m_bound-m_tol && currentNode!=endNode) {
00099 
00100         // look at each neighbour of current node
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           //changeKey(nextNode,nextLabel);
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 } // end double calculateShortestPath(..)
00143 
00144 
00145 
00146 // -----------------------------------------------------------------------------
00147 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00148 // -----------------------------------------------------------------------------
00149 
00150 
00151 // -----------------------------------------------------------------------------
00152 // b u i l d H e a p
00153 // -----------------------------------------------------------------------------
00154 void ShortestPathCalculator::buildHeap(int startNode)
00155 {
00156     int i;   // Loop variable.
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     //m_nodeLabel[startNode] = 0.0;
00174 }
00175 
00176 
00177 // -----------------------------------------------------------------------------
00178 // e x t r a c t M i n
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 }// end: int extractMin()
00232 
00233 
00234 // -----------------------------------------------------------------------------
00235 // c h a n g e K e y
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 }// end: void changeKey(..)
00258 
00259 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO