- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Blis-0.91.2/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 Common 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-2009, 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
    00345     virtual int process(bool isRoot = false, bool rampUp = false) = 0;
    00346
    00356     virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> >
    00357         branch() = 0;
    00358
    00359  protected:
    00360
    00362     AlpsReturnStatus encodeAlps(AlpsEncoded *encoded) const;
    00363
    00365     AlpsReturnStatus decodeAlps(AlpsEncoded &encoded);
    00366
    00367 };
    00368 #endif