/home/coin/Bcp-1.0.0/Bcp/src/include/BCP_tm_node.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _BCP_TM_NODE
00004 #define _BCP_TM_NODE
00005 
00006 #include <cfloat>
00007 
00008 #include "BCP_vector.hpp"
00009 
00010 
00013 enum BCP_tm_node_status{
00015     BCP_DefaultNode,
00017     BCP_ProcessedNode,
00019     BCP_ActiveNode,
00021     BCP_PrunedNode_OverUB,
00023     BCP_PrunedNode_Infeas,
00025     BCP_PrunedNode_Discarded,
00027     BCP_CandidateNode,
00029     BCP_NextPhaseNode_OverUB,
00031     BCP_NextPhaseNode_Infeas
00032 };
00033 
00034 //#############################################################################
00035 
00036 class BCP_proc_id;
00037 class BCP_node_change;
00038 class BCP_user_data;
00039 
00040 class BCP_tm_node;
00041 class BCP_tm_prob;
00042 
00043 //#############################################################################
00044 
00047 class BCP_tm_node {
00048 private:
00052     BCP_tm_node(const BCP_tm_node&);
00054     BCP_tm_node& operator=(const BCP_tm_node&);
00057     // NOTE: deleting a tree_node deletes the whole subtree below!
00058 public:
00060     // *FIXME* break into groups 
00063     BCP_tm_node_status status;
00065     int _index;
00067     int _level;
00069     double _quality;
00071     double _true_lower_bound;
00073     BCP_node_change* _desc;
00075     BCP_tm_node* _parent;
00077     BCP_user_data* _user_data;
00079     int _birth_index;
00081     BCP_vec<BCP_tm_node*> _children;
00083     BCP_proc_id* lp;
00085     BCP_proc_id* cg;
00087     BCP_proc_id* cp;
00089     BCP_proc_id* vg;
00091     BCP_proc_id* vp;
00093     int _processed_leaf_num;
00095     int _pruned_leaf_num;
00097     int _tobepriced_leaf_num;
00099     int _leaf_num;
00102 public:
00106     BCP_tm_node(int level, BCP_node_change* desc) :
00107         status(BCP_DefaultNode),
00108         _index(0),
00109         _level(level),
00110         _quality(-DBL_MAX),
00111         _true_lower_bound(-DBL_MAX),
00112         _desc(desc),
00113         _parent(0),
00114         _user_data(0),
00115         _birth_index(-1),
00116         _children(),
00117         lp(0), cg(0), cp(0), vg(0), vp(0),
00118         _processed_leaf_num(0),
00119         _pruned_leaf_num(0),
00120         _tobepriced_leaf_num(0),
00121         _leaf_num(0)
00122     {}
00123 
00125     BCP_tm_node(int level, BCP_node_change* desc,
00126                 BCP_tm_node* parent, int index) :
00127         status(BCP_DefaultNode),
00128         _index(0),
00129         _level(level),
00130         _quality(-DBL_MAX),
00131         _true_lower_bound(-DBL_MAX),
00132         _desc(desc),
00133         _parent(0),
00134         _user_data(0),
00135         _birth_index(-1),
00136         _children(),
00137         lp(0), cg(0), cp(0), vg(0), vp(0),
00138         _processed_leaf_num(0),
00139         _pruned_leaf_num(0),
00140         _tobepriced_leaf_num(0),
00141         _leaf_num(0)
00142     {}
00143 
00145     ~BCP_tm_node();
00151     inline int index() const { return _index; }
00153     inline int level() const { return _level; }
00155     inline int child_num() const { return _children.size(); }
00157     inline double quality() const { return _quality; }
00159     inline double true_lower_bound() const { return _true_lower_bound; }
00161     inline int birth_index() const { return _birth_index; }
00162 
00164     inline BCP_user_data* user_data() { return _user_data; }
00166     inline BCP_tm_node* child(int ind) { return _children[ind]; }
00168     inline BCP_tm_node* parent() { return _parent; }
00169 
00171     inline const BCP_user_data* user_data() const { return _user_data; }
00173     inline const BCP_tm_node* child(int ind) const { return _children[ind]; }
00175     inline const BCP_tm_node* parent() const { return _parent; }
00182     // Marking the descendants for deletion means that their _index fields are
00183     // set to -1. The reason is that some book-keeping must be one with the CP,
00184     // VP processes; with the next phase list, with the priority queue of the
00185     // current phase (and maybe sthing else?). So this function only marks, and
00186     // the data will be deleted later.
00187     int mark_descendants_for_deletion();
00189     void remove_child(BCP_tm_node* node);
00191     inline void reserve_child_num(int num) { _children.reserve(num); }
00193     inline void new_child(BCP_tm_node* node) { _children.push_back(node); }
00195 };
00196 
00197 //#############################################################################
00198 
00201 class BCP_tree {
00202 private:
00204     BCP_vec<BCP_tm_node*> _tree;
00206     int maxdepth_;
00207     int processed_;
00208 
00209 public:
00213     BCP_tree() : _tree(), maxdepth_(0), processed_(0) {}
00215     ~BCP_tree() {
00216         for (int i = _tree.size() - 1; i >= 0; --i) {
00217             delete _tree[i];
00218         }
00219     }
00225     inline BCP_vec<BCP_tm_node*>::iterator begin() { return _tree.begin(); }
00227     inline BCP_vec<BCP_tm_node*>::iterator end()   { return _tree.end(); }
00228 
00230     inline BCP_tm_node* root() { return _tree.front(); }
00232     inline BCP_tm_node* operator[](int index) { return _tree[index]; }
00234     inline size_t size() const { return _tree.size(); }
00236     inline int maxdepth() const { return maxdepth_; }
00238     inline int processed() const { return processed_; }
00239     inline void increase_processed() { ++processed_; }
00245     double true_lower_bound(const BCP_tm_node* node) const;
00247     void enumerate_leaves(BCP_tm_node* node, const double obj_limit);
00249     inline void insert(BCP_tm_node* node) {
00250         node->_index = _tree.size();
00251         _tree.push_back(node);
00252         if (node->_level > maxdepth_)
00253             maxdepth_ = node->_level;
00254     }
00255     inline void remove(int index) {
00256         _tree[index] = 0;
00257     }
00259 };
00260 
00261 //#############################################################################
00262 
00263 class BCP_node_queue {
00264 private:
00265     BCP_node_queue();
00266     BCP_node_queue(const BCP_node_queue&);
00267     BCP_node_queue& operator=(const BCP_node_queue&);
00268 
00269 private:
00274     BCP_tm_prob& _p;
00279     BCP_vec<BCP_tm_node*> _pq;
00282 public:
00286     BCP_node_queue(BCP_tm_prob& p) : _p(p), _pq() { _pq.push_back(NULL); }
00288     ~BCP_node_queue() {}
00292     inline bool empty() const { return _pq.size() == 1; }
00293 
00295     BCP_tm_node* top() const { return _pq[1]; }
00296 
00298     void pop();
00299 
00301     void insert(BCP_tm_node* node);
00302 
00305     void compare_to_UB(int& quality_above_UB, int& quality_below_UB);
00306 };
00307 
00308 //#############################################################################
00309 
00310 #endif

Generated on Wed Aug 22 03:00:54 2007 for coin-Bcp by  doxygen 1.4.7