#include <ShortestPathCalculator.hh>
Public Member Functions | |
ShortestPathCalculator (int nNodes, int nEdges, int *adjPtr, int *adjList, double *edgeWeight, double bound, double tol) | |
~ShortestPathCalculator () | |
double | calculateShortestPath (int startNode, int endNode, int *predNode) |
Definition at line 30 of file ShortestPathCalculator.hh.
|
Constructor.
Definition at line 36 of file ShortestPathCalculator.cpp. 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 }
|
|
Destructor. Definition at line 69 of file ShortestPathCalculator.cpp. 00069 { 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 }
|
|
Calculate the shortest path.
Definition at line 83 of file ShortestPathCalculator.cpp. 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(..)
|