/home/coin/SVN-release/OS-2.1.1/Bcp/src/TM/BCP_tm_trimming.cpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #include <cstdio>
00004 #include "BCP_tm.hpp"
00005 #include "BCP_tm_functions.hpp"
00006 
00007 static int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
00008                             const bool between_phases);
00009 
00010 //#############################################################################
00011 // For now we'll trim the tree only between phases when nothing is processed.
00012 // Reason: It's kinda ugly to cut off a subtree when several of its nodes
00013 // might be processed. Nevertheless, this should be done sooner or later.
00014 //
00015 // *THINK*
00016 //#############################################################################
00017 
00018 void BCP_tm_trim_tree_wrapper(BCP_tm_prob& p, const bool between_phases)
00019 {
00020     BCP_tree& tree = p.search_tree;
00021     BCP_tm_node* root = tree.root();
00022     tree.enumerate_leaves(root, p.ub() - p.granularity());
00023     const int trimmed =
00024         BCP_tm_trim_tree(p, root, true /* called between phases */);
00025     if (p.param(BCP_tm_par::TmVerb_TrimmedNum)) {
00026         printf("\
00027 TM: before starting the new phase, \n\
00028     %i nodes were trimmed from the tree.\n", trimmed);
00029     }
00030 
00031     BCP_vec<BCP_tm_node*>::iterator nodep;
00032     BCP_vec<BCP_tm_node*>::const_iterator lastnodep;
00033     BCP_tm_node * node;
00034 
00035     // clean up the next phase nodes
00036     nodep = p.next_phase_nodes.begin();
00037     lastnodep = p.next_phase_nodes.end();
00038     while (nodep != lastnodep) {
00039         if ((*nodep)->index() == -1) {
00040             *nodep = *--lastnodep;
00041             p.next_phase_nodes.pop_back();
00042         } else {
00043             ++nodep;
00044         }
00045     }
00046 
00047     // FIXME: Why is this block necessary?
00048     // clean up the list of candidates
00049     if (! p.candidate_list.empty()) {
00050         BCP_vec<BCP_tm_node*> cands;
00051         while (! p.candidate_list.empty()) {
00052             CoinTreeNode* coinnode = p.candidate_list.top();
00053             node = dynamic_cast<BCP_tm_node*>(coinnode);
00054             if (node->index() != -1)
00055                 cands.push_back(node);
00056             p.candidate_list.pop();
00057         }
00058         lastnodep = cands.end();
00059         for (nodep = cands.begin(); nodep != lastnodep; ++nodep)
00060             p.candidate_list.push(*nodep);
00061     }
00062 
00063     // clean up the tree
00064     nodep = p.search_tree.begin();
00065     lastnodep = p.search_tree.end();
00066     while (nodep != lastnodep) {
00067         node = *nodep;
00068         if (node->index() == -1) {
00069             // The search tree node is in a subtree that is trimmed
00070 #ifdef BCP_DEBUG
00071             if (node->lp != -1 || node->cg != -1 || node->vg != -1)
00072                 throw BCP_fatal_error("\
00073 TM: At least on of lp/cg/vg of a trimmed node is non-0.\n");
00074 #endif
00075             if (node->cp != -1 && node->child_num() == 0) {
00076                 BCP_vec< std::pair<int, int> >::iterator proc =
00077                     BCP_tm_identify_process(p.leaves_per_cp, node->cp);
00078 #ifdef BCP_DEBUG
00079                 if (proc == p.leaves_per_cp.end())
00080                     throw BCP_fatal_error("\
00081 TM: non-existing CP is assigned to a leaf.\n");
00082 #endif
00083                 --proc->second;
00084             }
00085             if (node->vp != -1 && node->child_num() == 0) {
00086                 BCP_vec< std::pair<int, int> >::iterator proc =
00087                     BCP_tm_identify_process(p.leaves_per_vp, node->vp);
00088 #ifdef BCP_DEBUG
00089                 if (proc == p.leaves_per_vp.end())
00090                     throw BCP_fatal_error("\
00091 TM: non-existing VP is assigned to a leaf.\n");
00092 #endif
00093                 --proc->second;
00094             }
00095             delete node;
00096             *nodep = 0;
00097         }
00098         ++nodep;
00099     }
00100 
00101 #if ! defined(BCP_ONLY_LP_PROCESS_HANDLING_WORKS)
00102     // scan through the CP and VP list to mark the free ones
00103     BCP_vec< std::pair<int, int> >::iterator proc;
00104     BCP_vec< std::pair<int, int> >::iterator lastproc;
00105 
00106     lastproc = p.leaves_per_cp.end();
00107     for (proc = p.leaves_per_cp.begin(); proc != lastproc; ++proc)
00108         if (proc->second == 0)
00109             p.slaves.cp->set_proc_free(proc->first);
00110 
00111     lastproc = p.leaves_per_vp.end();
00112     for (proc = p.leaves_per_vp.begin(); proc != lastproc; ++proc)
00113         if (proc->second == 0)
00114             p.slaves.vp->set_proc_free(proc->first);
00115 #endif
00116 }
00117 
00118 //#############################################################################
00119 // We will trim very conservatively
00120 
00121 int BCP_tm_trim_tree(BCP_tm_prob& p, BCP_tm_node* node,
00122                      const bool between_phases)
00123 {
00124     bool trim = true;
00125     int trimmed = 0;
00126 
00127     if (node->_processed_leaf_num > 0) {
00128         // if there is a node currently processed in the subtree then don't
00129         // trim here
00130         trim = false;
00131     } else if (node->child_num() == 0) {
00132         // if this is a leaf then there is no point in trimming
00133         trim = false;
00134     } else if (node->_leaf_num - node->_pruned_leaf_num <= 2) {
00135         // if there are no more than 2 nodes further down that have to be taken
00136         // care of then don't trim
00137         trim = false;
00138     } else if (node->getTrueLB() < p.ub() - p.granularity()) {
00139         // don't trim if the gap at this node is not below the granularity
00140         trim = false;
00141     }
00142 
00143     if (trim) {
00144         trimmed = node->mark_descendants_for_deletion();
00145         if (node->cp != -1) {
00146             BCP_vec< std::pair<int, int> >::iterator proc =
00147                 BCP_tm_identify_process(p.leaves_per_cp, node->cp);
00148 #ifdef BCP_DEBUG
00149             if (proc == p.leaves_per_cp.end())
00150                 throw BCP_fatal_error("\
00151 TM: An internal node is assigned to a non-existing CP.\n");
00152 #endif
00153             ++proc->second;
00154         }
00155         if (node->vp != -1) {
00156             BCP_vec< std::pair<int, int> >::iterator proc =
00157                 BCP_tm_identify_process(p.leaves_per_vp, node->vp);
00158 #ifdef BCP_DEBUG
00159             if (proc == p.leaves_per_vp.end())
00160                 throw BCP_fatal_error("\
00161 TM: An internal node is assigned to a non-existing VP.\n");
00162 #endif
00163             ++proc->second;
00164         }
00165     } else {
00166         // try to trim at the children
00167         BCP_vec<BCP_tm_node*>::iterator child;
00168         BCP_vec<BCP_tm_node*>::const_iterator lastchild =
00169             node->_children.end();
00170         for (child = node->_children.begin(); child != lastchild; ++child)
00171             trimmed += BCP_tm_trim_tree(p, *child, between_phases);
00172     }
00173 
00174     return trimmed;
00175 }
00176 
00177 //#############################################################################
00178 // This routine will delete a node (which must be a leaf)
00179 
00180 void BCP_tm_remove_explored(BCP_tm_prob& p, BCP_tm_node* node)
00181 {
00182     if (! p.param(BCP_tm_par::RemoveExploredBranches))
00183         return;
00184 
00185     if (node->child_num() == 0) {
00186         BCP_tm_node* parent = node->parent();
00187         p.search_tree.remove(node->index());
00188         delete node;
00189 
00190         if (parent) {
00191             parent->remove_child(node);
00192             BCP_tm_remove_explored(p, parent);
00193         }
00194     }
00195 }
00196 
00197 //#############################################################################

Generated on Mon May 3 03:05:13 2010 by  doxygen 1.4.7