AlpsTreeNode.h

Go to the documentation of this file.

/*===========================================================================*
 * This file is part of the Abstract Library for Parallel Search (ALPS).     *
 *                                                                           *
 * ALPS is distributed under the Eclipse Public License as part of the       *
 * COIN-OR repository (http://www.coin-or.org).                              *
 *                                                                           *
 * Authors:                                                                  *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *                                                                           *
 * Conceptual Design:                                                        *
 *                                                                           *
 *          Yan Xu, Lehigh University                                        *
 *          Ted Ralphs, Lehigh University                                    *
 *          Laszlo Ladanyi, IBM T.J. Watson Research Center                  *
 *          Matthew Saltzman, Clemson University                             *
 *                                                                           * 
 *                                                                           *
 * Copyright (C) 2001-2013, Lehigh University, Yan Xu, and Ted Ralphs.       *
 *===========================================================================*/

#ifndef AlpsTreeNode_h_
#define AlpsTreeNode_h_

#include <algorithm>
#include <utility>
#include <vector>

#include "CoinError.hpp"
#include "CoinSort.hpp"

#include "Alps.h"
#include "AlpsKnowledge.h"
#include "AlpsNodeDesc.h"

typedef int AlpsNodeIndex_t;

class AlpsKnowledgeBroker;
class AlpsSubTree;

//#############################################################################
//#############################################################################

class AlpsTreeNode : public AlpsKnowledge { 
 private:
    AlpsTreeNode(const AlpsTreeNode&);
    AlpsTreeNode& operator=(const AlpsTreeNode&);

 protected:
    //AlpsSubTree*       subTree_;
    
    bool               active_;

    AlpsNodeIndex_t    index_;

    int                depth_;

    double             solEstimate_;

    double             quality_;
    
    AlpsTreeNode*      parent_;

    AlpsNodeIndex_t    parentIndex_;

    int                numChildren_;
   
#if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?

    AlpsTreeNode*      children_[ALPS_MAX_CHILD_NUM];
#else
    AlpsTreeNode**     children_;
#endif

    int                explicit_;
    
    AlpsNodeDesc*      desc_;

    AlpsNodeStatus     status_;

    // Need broker to get incumbent value and add solution when process().
    AlpsKnowledgeBroker*  knowledgeBroker_;
    
    // 0: default; 1: in subtree to be sent: 2: in subtree's node pool 
    int sentMark_;   
    
 public:
    AlpsTreeNode() 
        :
        active_(false),
        index_(-1),
        depth_(-1),
        solEstimate_(ALPS_OBJ_MAX),
        quality_(ALPS_OBJ_MAX),   // Smaller than default incumbentValue
        parent_(0),
        parentIndex_(-1),
        numChildren_(0),
#if defined(ALPS_MAX_CHILD_NUM) // *FIXME* : Do we want ifdefs?
        // AlpsTreeNode*     children_[ALPS_MAX_CHILD_NUM];
#else
        children_(0),
#endif
        explicit_(0),
        desc_(0),
        status_(AlpsNodeStatusCandidate),
        knowledgeBroker_(0),
        sentMark_(0)
        { setType(AlpsKnowledgeTypeNode); }
    
    virtual ~AlpsTreeNode() {
        assert(numChildren_ == 0);
        //std::cout << "---- delete Alps part of node " << index_ << std::endl;
#if ! defined(ALPS_MAX_CHILD_NUM)
        if (children_ != 0) {
            delete [] children_;
            children_ = 0;
        }
#endif
        if (desc_ != 0) {
            delete desc_;  
            desc_ = 0;
        }
    }
    
    bool operator<(const AlpsTreeNode& compNode)
        { return quality_ < compNode.getQuality(); }
    
    AlpsNodeDesc* modifyDesc() { return desc_; }
    AlpsNodeDesc* getDesc() const { return desc_; }
    void setDesc(AlpsNodeDesc* desc) { desc_ = desc; }    

    inline AlpsKnowledgeBroker*  getKnowledgeBroker() const 
        { return knowledgeBroker_; }
    inline void setKnowledgeBroker(AlpsKnowledgeBroker* kb) 
        { knowledgeBroker_ = kb; }

    /* FIXME: I think that we probably want the argument to be a diff'd
       description, but this is open to debate. Maybe we should
       overload this method and have a version that creates a diff'd
       description, as well as one that creates an explicit
       description. */
    virtual AlpsTreeNode* createNewTreeNode(AlpsNodeDesc*& desc) const = 0;

    inline AlpsNodeStatus getStatus() const { return status_; }
    inline void setStatus(const AlpsNodeStatus stat) { status_ = stat; }
    
    inline bool isCandidate() const {
        return status_ == AlpsNodeStatusCandidate; }
    inline bool isEvaluated() const {
        return status_ == AlpsNodeStatusEvaluated; }
    inline bool isPregnant() const  {
        return status_ == AlpsNodeStatusPregnant; }
    inline bool isBranched() const  {
        return status_ == AlpsNodeStatusBranched; }
    inline bool isFathomed() const  {
        return status_ == AlpsNodeStatusFathomed; }
    inline bool isDiscarded() const  {
        return status_ == AlpsNodeStatusDiscarded; }
    
    inline bool isActive() const { return active_; }
    inline void setActive(const bool yesno) { active_ = yesno; }

    inline AlpsNodeIndex_t getIndex() const { return index_; }
    inline void setIndex(const AlpsNodeIndex_t index) { index_ = index; }
   
    inline int getDepth() const { return depth_; }
    inline void setDepth(const int depth) { depth_ = depth; }

    inline double getSolEstimate() const { return solEstimate_; }
    inline void setSolEstimate(double est) { solEstimate_ = est; }

    inline double getQuality() const { return quality_; }
    inline void setQuality(double quality) { quality_ = quality; }

    inline int getNumChildren() const { return numChildren_; }
    inline void setNumChildren(const int numChildren) {
        numChildren_ = numChildren;
#if ! defined(ALPS_MAX_CHILD_NUM)
        if (children_ != 0) {
            delete [] children_;
            children_ = 0;
        }
        children_ = new AlpsTreeNode*[numChildren_];
#endif
    }
    // Change by s
    inline void modifyNumChildren(const int s) { numChildren_ += s; }

    // *FIXME* : Sanity check. Maybe we should check that the argument is in
    // the correct range, but how do we do that? This makes the code
    // inefficient so it should be done with #ifdefs so it can be compiled
    // out. But in that case, we should move this code to the implementation
    // file and it won't get inlined anymore.

    inline AlpsTreeNode* getChild(const int i) const { return children_[i]; }
 
    //FIXME: Compiler complains about this second declaration. Not sure how to
    //declare a const and a non-const version of a function with the same
    //arguments...
    // /** Returns a const pointer to the ith child. */
    // const AlpsTreeNode* getChild(const int i) const { return children_[i]; }
    inline void setChild(const int i, AlpsTreeNode* node)
        { children_[i] = node; }

    void removeChild(AlpsTreeNode*& child);

    void addChild(AlpsTreeNode*& child);

    void removeDescendants();

    //inline AlpsSubTree* getSubTree() const { return subTree_; }
    //inline void setSubTree(AlpsSubTree* tree) { subTree_ = tree; }
    
    inline AlpsTreeNode* getParent() const { return parent_; }
    inline void setParent(AlpsTreeNode* parent) { parent_ = parent; }

    inline AlpsNodeIndex_t getParentIndex() const { return parentIndex_; }
    inline void setParentIndex(AlpsNodeIndex_t index) 
        { parentIndex_ = index; }

    inline int getExplicit() const { return explicit_; }
    inline void setExplicit(int fp) { explicit_ = fp; }

    virtual void convertToExplicit() {}
    virtual void convertToRelative() {}

    inline int getSentMark() const { return sentMark_; }
    inline void setSentMark(const int tf) { sentMark_ = tf; }

    virtual int process(bool isRoot = false, bool rampUp = false) = 0;
    
    virtual std::vector< CoinTriple<AlpsNodeDesc*, AlpsNodeStatus, double> > 
        branch() = 0;

 protected:
    
    AlpsReturnStatus encodeAlps(AlpsEncoded *encoded) const;
    
    AlpsReturnStatus decodeAlps(AlpsEncoded &encoded);

};
#endif