/usr/src/RPM/BUILD/CoinAlps-1.4.4/Alps/src/AlpsTreeNode.h
Go to the documentation of this file.
00001 /*===========================================================================*
00002  * This file is part of the Abstract Library for Parallel Search (ALPS).     *
00003  *                                                                           *
00004  * ALPS is distributed under the Eclipse Public License as part of the       *
00005  * COIN-OR repository (http://www.coin-or.org).                              *
00006  *                                                                           *
00007  * Authors:                                                                  *
00008  *                                                                           *
00009  *          Yan Xu, Lehigh University                                        *
00010  *          Ted Ralphs, Lehigh University                                    *
00011  *                                                                           *
00012  * Conceptual Design:                                                        *
00013  *                                                                           *
00014  *          Yan Xu, Lehigh University                                        *
00015  *          Ted Ralphs, Lehigh University                                    *
00016  *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
00017  *          Matthew Saltzman, Clemson University                             *
00018  *                                                                           * 
00019  *                                                                           *
00020  * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
00021  *===========================================================================*/
00022 
00023 #ifndef AlpsTreeNode_h_
00024 #define AlpsTreeNode_h_
00025 
00026 #include <algorithm>
00027 #include <utility>
00028 #include <vector>
00029 
00030 #include "CoinError.hpp"
00031 #include "CoinSort.hpp"
00032 
00033 #include "Alps.h"
00034 #include "AlpsKnowledge.h"
00035 #include "AlpsNodeDesc.h"
00036 
00037 typedef int AlpsNodeIndex_t;
00038 
00039 class AlpsKnowledgeBroker;
00040 class AlpsSubTree;
00041 
00042 //#############################################################################
00048 //#############################################################################
00049 
00050 class AlpsTreeNode : public AlpsKnowledge { 
00051  private:
00052     AlpsTreeNode(const AlpsTreeNode&);
00053     AlpsTreeNode& operator=(const AlpsTreeNode&);
00054 
00055  protected:
00057     //AlpsSubTree*       subTree_;
00058     
00060     bool               active_;
00061 
00063     AlpsNodeIndex_t    index_;
00064 
00066     int                depth_;
00067 
00069     double             solEstimate_;
00070 
00072     double             quality_;
00073     
00075     AlpsTreeNode*      parent_;
00076 
00078     AlpsNodeIndex_t    parentIndex_;
00079 
00081     int                numChildren_;
00082    
00083 #if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
00084 
00085     AlpsTreeNode*      children_[ALPS_MAX_CHILD_NUM];
00086 #else
00087     AlpsTreeNode**     children_;
00088 #endif
00089 
00092     int                explicit_;
00093     
00095     AlpsNodeDesc*      desc_;
00096 
00098     AlpsNodeStatus     status_;
00099 
00102     // Need broker to get incumbent value and add solution when process().
00103     AlpsKnowledgeBroker*  knowledgeBroker_;
00104     
00106     // 0: default; 1: in subtree to be sent: 2: in subtree's node pool 
00107     int sentMark_;   
00108     
00110     bool diving_;
00111     
00112  public:
00113     AlpsTreeNode() 
00114         :
00115         active_(false),
00116         index_(-1),
00117         depth_(-1),
00118         solEstimate_(ALPS_OBJ_MAX),
00119         quality_(ALPS_OBJ_MAX),   // Smaller than default incumbentValue
00120         parent_(0),
00121         parentIndex_(-1),
00122         numChildren_(0),
00123 #if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
00124         // AlpsTreeNode*     children_[ALPS_MAX_CHILD_NUM];
00125 #else
00126         children_(0),
00127 #endif
00128         explicit_(0),
00129         desc_(0),
00130         status_(AlpsNodeStatusCandidate),
00131         knowledgeBroker_(0),
00132         sentMark_(0),
00133         diving_(false)
00134         { setType(AlpsKnowledgeTypeNode); }
00135     
00136     virtual ~AlpsTreeNode() {
00137         assert(numChildren_ == 0);
00138         //std::cout << "---- delete Alps part of node " << index_ << std::endl;
00139 #if ! defined(ALPS_MAX_CHILD_NUM)
00140         if (children_ != 0) {
00141             delete [] children_;
00142             children_ = 0;
00143         }
00144 #endif
00145         if (desc_ != 0) {
00146             delete desc_;  
00147             desc_ = 0;
00148         }
00149     }
00150     
00151     bool operator<(const AlpsTreeNode& compNode)
00152         { return quality_ < compNode.getQuality(); }
00153     
00155     AlpsNodeDesc* modifyDesc() { return desc_; }
00156     AlpsNodeDesc* getDesc() const { return desc_; }
00157     void setDesc(AlpsNodeDesc* desc) { desc_ = desc; }    
00158 
00160     inline AlpsKnowledgeBroker*  getKnowledgeBroker() const 
00161         { return knowledgeBroker_; }
00162     inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) 
00163         { knowledgeBroker_ = kb; }
00164 
00167     /* FIXME: I think that we probably want the argument to be a diff'd
00168        description, but this is open to debate. Maybe we should
00169        overload this method and have a version that creates a diff'd
00170        description, as well as one that creates an explicit
00171        description. */
00172     virtual AlpsTreeNode* createNewTreeNode(AlpsNodeDesc*& desc) const = 0;
00173 
00175 
00176     inline AlpsNodeStatus getStatus() const { return status_; }
00177     inline void setStatus(const AlpsNodeStatus stat) { status_ = stat; }
00179     
00181 
00182     inline bool isCandidate() const {
00183         return status_ == AlpsNodeStatusCandidate; }
00184     inline bool isEvaluated() const {
00185         return status_ == AlpsNodeStatusEvaluated; }
00186     inline bool isPregnant() const  {
00187         return status_ == AlpsNodeStatusPregnant; }
00188     inline bool isBranched() const  {
00189         return status_ == AlpsNodeStatusBranched; }
00190     inline bool isFathomed() const  {
00191         return status_ == AlpsNodeStatusFathomed; }
00192     inline bool isDiscarded() const  {
00193         return status_ == AlpsNodeStatusDiscarded; }
00195     
00197 
00198     inline bool isActive() const { return active_; }
00199     inline void setActive(const bool yesno) { active_ = yesno; }
00201 
00203 
00204     inline AlpsNodeIndex_t getIndex() const { return index_; }
00205     inline void setIndex(const AlpsNodeIndex_t index) { index_ = index; }
00207    
00209 
00210     inline int getDepth() const { return depth_; }
00211     inline void setDepth(const int depth) { depth_ = depth; }
00213 
00215 
00216     inline double getSolEstimate() const { return solEstimate_; }
00217     inline void setSolEstimate(double est) { solEstimate_ = est; }
00219 
00221 
00222     inline double getQuality() const { return quality_; }
00223     inline void setQuality(double quality) { quality_ = quality; }
00225 
00227 
00228     inline int getNumChildren() const { return numChildren_; }
00229     inline void setNumChildren(const int numChildren) {
00230         numChildren_ = numChildren;
00231 #if ! defined(ALPS_MAX_CHILD_NUM)
00232         if (children_ != 0) {
00233             delete [] children_;
00234             children_ = 0;
00235         }
00236         children_ = new AlpsTreeNode*[numChildren_];
00237 #endif
00238     }
00239     // Change by s
00240     inline void modifyNumChildren(const int s) { numChildren_ += s; }
00242 
00243     // *FIXME* : Sanity check. Maybe we should check that the argument is in
00244     // the correct range, but how do we do that? This makes the code
00245     // inefficient so it should be done with #ifdefs so it can be compiled
00246     // out. But in that case, we should move this code to the implementation
00247     // file and it won't get inlined anymore.
00248 
00250 
00251     inline AlpsTreeNode* getChild(const int i) const { return children_[i]; }
00252  
00253     //FIXME: Compiler complains about this second declaration. Not sure how to
00254     //declare a const and a non-const version of a function with the same
00255     //arguments...
00256     // /** Returns a const pointer to the ith child. */
00257     // const AlpsTreeNode* getChild(const int i) const { return children_[i]; }
00258     inline void setChild(const int i, AlpsTreeNode* node)
00259         { children_[i] = node; }
00261 
00265     void removeChild(AlpsTreeNode*& child);
00266 
00268     void addChild(AlpsTreeNode*& child);
00269 
00273     void removeDescendants();
00274 
00276     //inline AlpsSubTree* getSubTree() const { return subTree_; }
00277     //inline void setSubTree(AlpsSubTree* tree) { subTree_ = tree; }
00278     
00280 
00281     inline AlpsTreeNode* getParent() const { return parent_; }
00282     inline void setParent(AlpsTreeNode* parent) { parent_ = parent; }
00284 
00286 
00287     inline AlpsNodeIndex_t getParentIndex() const { return parentIndex_; }
00288     inline void setParentIndex(AlpsNodeIndex_t index) 
00289         { parentIndex_ = index; }
00291 
00294 
00295     inline int getExplicit() const { return explicit_; }
00296     inline void setExplicit(int fp) { explicit_ = fp; }
00298 
00300 
00301     virtual void convertToExplicit() {}
00302     virtual void convertToRelative() {}
00304 
00306 
00307     inline int getDiving() const { return diving_; }
00308     inline void setDiving(const bool d) { diving_ = d; }
00310 
00312 
00313     inline int getSentMark() const { return sentMark_; }
00314     inline void setSentMark(const int tf) { sentMark_ = tf; }
00316 
00346     virtual int process(bool isRoot = false, bool rampUp = false) = 0;
00347     
00357     virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> > 
00358         branch() = 0;
00359 
00360  protected:
00361     
00363     AlpsReturnStatus encodeAlps(AlpsEncoded *encoded) const;
00364     
00366     AlpsReturnStatus decodeAlps(AlpsEncoded &encoded);
00367 
00368 };
00369 #endif