ShortestPathCalculator Class Reference

#include <ShortestPathCalculator.hh>

List of all members.

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)


Detailed Description

This class realizes the exact calculation of shortest paths by dijkstra with heaps.

Definition at line 30 of file ShortestPathCalculator.hh.


Constructor & Destructor Documentation

ShortestPathCalculator::ShortestPathCalculator int  nNodes,
int  nEdges,
int *  adjPtr,
int *  adjList,
double *  edgeWeight,
double  bound,
double  tol
 

Constructor.

Parameters:
nNodes Number of nodes.
nEdges Number of edges.
*adjPtr Pointer of indizes to the adjaznes list. It is the start index to all the adjazent node.
*adjList Pointer of adjazens list.
*edgeWeight 
bound 
tol 

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 }

ShortestPathCalculator::~ShortestPathCalculator  ) 
 

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 }


Member Function Documentation

double ShortestPathCalculator::calculateShortestPath int  startNode,
int  endNode,
int *  predNode
 

Calculate the shortest path.

Parameters:
startNode Node to start the path.
endNode Node to end the path.
*predNode Nodes of the path.
Returns:
Weight of shortes 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(..)


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:01 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO