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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : StableSetSub.hh
00004 //  Description      : The nodes of the Branchand Cut tree.
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of Heidelberg
00009 //  Created on       : Thu Apr 06 13:39:46 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 
00022 #ifndef STABLE_SET_SUB_HH
00023 #define STABLE_SET_SUB_HH
00024 
00025 #include "abacus/sub.h"
00026 #include <vector>
00027 
00028 using namespace std;
00029 
00030 class Clique;
00031 class EdgeProjection;
00032 class Graph;
00033 class MaxCliquesSeparator;
00034 class OddCyclesSeparator;
00035 class StableSetBranchRule;
00036 class StableSetMaster;
00037 class StableSetStatistics;
00038 
00039 
00040 
00048 class StableSetSub: public ABA_SUB {
00049 
00050 public:
00051 
00052     // -------------------------------------------------------------------------
00053     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
00054     // -------------------------------------------------------------------------
00066     StableSetSub(ABA_MASTER *master, Graph *theGraph, Clique *theClique,
00067                  EdgeProjection *anEdgeProjection,
00068                  StableSetStatistics *aStatistic);
00069 
00084     StableSetSub(ABA_MASTER *master, ABA_SUB *father,
00085                  ABA_BRANCHRULE *branchRule, Graph *theGraph, Clique *theClique,
00086                  EdgeProjection *anEdgeProjection,
00087                  StableSetStatistics *aStatistic);
00088 
00092     virtual ~StableSetSub();
00093 
00100     virtual bool feasible();
00101 
00109     virtual ABA_SUB *generateSon(ABA_BRANCHRULE *rule);
00110 
00119     virtual int improve(double &primalValue);
00120 
00127     virtual int separate();
00128 
00136     virtual int generateBranchRules(ABA_BUFFER<ABA_BRANCHRULE*> &rules);
00137 
00145     void setVertex(int vertex, bool i);
00146 
00147 
00148 private:
00149 
00150     // -------------------------------------------------------------------------
00151     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
00152     // -------------------------------------------------------------------------
00153 
00160     int increaseToMaximalClique(OddCyclesSeparator *oddCyclesSep);
00161 
00169     StableSetMaster *stableSetMaster();
00170 
00171     
00172     // -------------------------------------------------------------------------
00173     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
00174     // -------------------------------------------------------------------------
00175 
00180     Graph *itsGraph;
00181 
00185     Clique *maxCliques;
00186  
00190     EdgeProjection *theEdgeProjection;
00191     
00195     StableSetStatistics *theStatistics;
00196 
00200     bool violatedEdge;
00201 
00202 };
00203 
00204 #endif
00205 
00206 

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