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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : ShortestPathCalculator.hh
00004 //  Description      :
00005 //  Author           : Marcus Oswald
00006 //  Email            : Marcus.Oswald@informatik.uni-heidelberg.de
00007 //  Copyright        : University of Heidelberg
00008 //  Created on       : Mon Jul 15 11:00:50 2002
00009 //  Last modified by : Rebennack
00010 //  Last modified on : 06.10.2005
00011 //  Update count     : 20
00012 //
00014 //
00015 //  Date        Name            Changes/Extensions
00016 //  ----        ----            ------------------
00017 //
00019 
00020 
00021 #ifndef SHORTEST_PATH_CALCULATOR_HH
00022 #define SHORTEST_PATH_CALCULATOR_HH
00023 
00024 
00025 
00030 class ShortestPathCalculator {
00031 
00032 public:
00033 
00034     // -------------------------------------------------------------------------
00035     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
00036     // -------------------------------------------------------------------------
00037 
00050     ShortestPathCalculator(int nNodes, int nEdges, int* adjPtr, int* adjList,
00051                            double* edgeWeight, double bound, double tol);
00052 
00056     ~ShortestPathCalculator();
00057 
00067     double calculateShortestPath(int startNode, int endNode, int* predNode);
00068 
00069 
00070 private:
00071 
00072     // -------------------------------------------------------------------------
00073     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
00074     // -------------------------------------------------------------------------
00075 
00081     void buildHeap(int startNode);
00082 
00088     int extractMin();
00089 
00096     void changeKey(int node, double label);
00097 
00098 
00099     // -------------------------------------------------------------------------
00100     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
00101     // -------------------------------------------------------------------------
00102 
00106     int m_nNodes;
00107 
00111     int m_nEdges;
00112 
00116     int* m_adjPtr;
00117 
00121     int* m_adjList;
00122 
00126     double* m_edgeWeight;
00127 
00131     double m_bound;
00132 
00136     double m_tol;
00137 
00141     int m_heapSize;
00142 
00146     int* m_heap;
00147 
00151     int* m_invHeap;
00152 
00156     double* m_nodeLabel;
00157 
00158 };// end: class shortestPathCalculator
00159 
00160 #endif
00161 
00162 

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