Generated on Tue Jul 27 2010 21:59:10 for Gecode by doxygen 1.7.1

spacenode.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2006
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-03-30 12:12:40 +0200 (Tue, 30 Mar 2010) $ by $Author: tack $
00011  *     $Revision: 10596 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  * Permission is hereby granted, free of charge, to any person obtaining
00018  * a copy of this software and associated documentation files (the
00019  * "Software"), to deal in the Software without restriction, including
00020  * without limitation the rights to use, copy, modify, merge, publish,
00021  * distribute, sublicense, and/or sell copies of the Software, and to
00022  * permit persons to whom the Software is furnished to do so, subject to
00023  * the following conditions:
00024  *
00025  * The above copyright notice and this permission notice shall be
00026  * included in all copies or substantial portions of the Software.
00027  *
00028  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/gist/spacenode.hh>
00039 #include <gecode/gist/visualnode.hh>
00040 #include <gecode/gist/stopbrancher.hh>
00041 #include <gecode/search.hh>
00042 #include <stack>
00043 
00044 namespace Gecode { namespace Gist {
00045 
00047   class Branch {
00048   public:
00050     int alternative;
00052     SpaceNode* ownBest;
00053     const Choice* choice;
00054 
00056     Branch(int a, const Choice* c, SpaceNode* best = NULL)
00057       : alternative(a), ownBest(best) {
00058         choice = c;
00059       }
00060   };
00061 
00062   BestNode::BestNode(SpaceNode* s0) : s(s0) {}
00063 
00064   int
00065   SpaceNode::recompute(BestNode* curBest, int c_d, int a_d) {
00066     int rdist = 0;
00067 
00068     if (workingSpace == NULL) {
00069       SpaceNode* curNode = this;
00070       SpaceNode* lastFixpoint = NULL;
00071 
00072       lastFixpoint = curNode;
00073 
00074       std::stack<Branch> stck;
00075 
00076       while (curNode->copy == NULL) {
00077         SpaceNode* parent = curNode->getParent();
00078         int alternative = curNode->getAlternative();
00079 
00080         Branch b(alternative, parent->choice,
00081                  curBest == NULL ? NULL : curNode->ownBest);
00082         stck.push(b);
00083 
00084         curNode = parent;
00085         rdist++;
00086       }
00087       Space* curSpace = curNode->copy->clone();
00088       curNode->setDistance(0);
00089 
00090       SpaceNode* lastBest = NULL;
00091       SpaceNode* middleNode = curNode;
00092       int curDist = 0;
00093 
00094       while (!stck.empty()) {
00095         if (a_d >= 0 &&
00096             curDist > a_d &&
00097             curDist == rdist / 2) {
00098             if (curSpace->status() == SS_FAILED) {
00099               workingSpace = curSpace;
00100               return rdist;
00101             } else {
00102               middleNode->copy = curSpace->clone();
00103             }
00104         }
00105         Branch b = stck.top(); stck.pop();
00106 
00107         if(middleNode == lastFixpoint) {
00108           curSpace->status();
00109         }
00110 
00111         curSpace->commit(*b.choice, b.alternative);
00112 
00113         if (b.ownBest != NULL && b.ownBest != lastBest) {
00114           b.ownBest->acquireSpace(curBest, c_d, a_d);
00115           if (b.ownBest->workingSpace->status() != SS_SOLVED) {
00116             // in the presence of weakly monotonic propagators, we may have to
00117             // use search to find the solution here
00118             Space* dfsSpace = Gecode::dfs(b.ownBest->workingSpace);
00119             delete b.ownBest->workingSpace;
00120             b.ownBest->workingSpace = dfsSpace;
00121           }
00122           curSpace->constrain(*b.ownBest->workingSpace);
00123           lastBest = b.ownBest;
00124         }
00125         curDist++;
00126         middleNode = middleNode->getChild(b.alternative);
00127         middleNode->setDistance(curDist);
00128       }
00129       workingSpace = curSpace;
00130 
00131     }
00132     return rdist;
00133   }
00134 
00135   void
00136   SpaceNode::acquireSpace(BestNode* curBest, int c_d, int a_d) {
00137     SpaceNode* p = getParent();
00138 
00139     if (getStatus() == UNDETERMINED && curBest != NULL && ownBest == NULL &&
00140         p != NULL && curBest->s != p->ownBest) {
00141           ownBest = curBest->s;
00142     }
00143 
00144     if (workingSpace == NULL && p != NULL && p->workingSpace != NULL) {
00145       // If parent has a working space, steal it
00146       workingSpace = p->workingSpace;
00147       p->workingSpace = NULL;
00148       if (p->choice != NULL)
00149         workingSpace->commit(*p->choice, getAlternative());
00150 
00151       if (ownBest != NULL) {
00152         ownBest->acquireSpace(curBest, c_d, a_d);
00153         if (ownBest->workingSpace->status() != SS_SOLVED) {
00154           // in the presence of weakly monotonic propagators, we may have to
00155           // use search to find the solution here
00156           Space* dfsSpace = Gecode::dfs(ownBest->workingSpace);
00157           delete ownBest->workingSpace;
00158           ownBest->workingSpace = dfsSpace;
00159         }
00160         workingSpace->constrain(*ownBest->workingSpace);
00161       }
00162       int d = p->getDistance()+1;
00163       if (d > c_d && c_d >= 0 &&
00164           workingSpace->status() == SS_BRANCH) {
00165         copy = workingSpace->clone();
00166         d = 0;
00167       }
00168       setDistance(d);
00169     }
00170 
00171     if (workingSpace == NULL) {
00172       if (recompute(curBest, c_d, a_d) > c_d && c_d >= 0 &&
00173           workingSpace->status() == SS_BRANCH) {
00174         copy = workingSpace->clone();
00175         setDistance(0);
00176       }
00177     }
00178 
00179     // always return a fixpoint
00180     workingSpace->status();
00181     if (copy == NULL && p != NULL && isOpen() &&
00182         p->copy != NULL && p->getNoOfOpenChildren() == 1 &&
00183         p->getParent() != NULL) {
00184       // last alternative optimization
00185       copy = p->copy;
00186       p->copy = NULL;
00187       setDistance(0);
00188       p->setDistance(p->getParent()->getDistance()+1);
00189       
00190       if(p->choice != NULL)
00191         copy->commit(*p->choice, getAlternative());
00192 
00193       if (ownBest != NULL) {
00194         ownBest->acquireSpace(curBest, c_d, a_d);
00195         if (ownBest->workingSpace->status() != SS_SOLVED) {
00196           // in the presence of weakly monotonic propagators, we may have to
00197           // use search to find the solution here
00198           Space* dfsSpace = Gecode::dfs(ownBest->workingSpace);
00199           delete ownBest->workingSpace;
00200           ownBest->workingSpace = dfsSpace;
00201         }
00202         copy->constrain(*ownBest->workingSpace);
00203       }
00204       if (copy->status() == SS_FAILED) {
00205         delete copy;
00206         copy = NULL;
00207       }
00208     }
00209   }
00210 
00211   void
00212   SpaceNode::closeChild(bool hadFailures, bool hadSolutions) {
00213     setHasFailedChildren(hasFailedChildren() || hadFailures);
00214     setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
00215 
00216     bool allClosed = true;
00217     for (int i=getNumberOfChildren(); i--;) {
00218       if (static_cast<SpaceNode*>(getChild(i))->isOpen()) {
00219         allClosed = false;
00220         break;
00221       }
00222     }
00223 
00224     if (allClosed) {
00225       setHasOpenChildren(false);
00226       for (unsigned int i=0; i<getNumberOfChildren(); i++)
00227         setHasSolvedChildren(hasSolvedChildren() ||
00228           static_cast<SpaceNode*>(getChild(i))->hasSolvedChildren());
00229       SpaceNode* p = static_cast<SpaceNode*>(getParent());
00230       if (p != NULL) {
00231         delete copy;
00232         copy = NULL;
00233         p->closeChild(hasFailedChildren(), hasSolvedChildren());
00234       }
00235     } else {
00236       
00237       if (hadSolutions) {
00238         setHasSolvedChildren(true);
00239         SpaceNode* p = getParent();
00240         while (p != NULL && !p->hasSolvedChildren()) {
00241           p->setHasSolvedChildren(true);
00242           p = p->getParent();
00243         }
00244       }
00245       if (hadFailures) {
00246         SpaceNode* p = getParent();
00247         while (p != NULL && !p->hasFailedChildren()) {
00248           p->setHasFailedChildren(true);
00249           p = p->getParent();
00250         }        
00251       }
00252     }
00253 
00254   }
00255 
00256   SpaceNode::SpaceNode(Space* root)
00257   : workingSpace(root), ownBest(NULL), nstatus(0) {
00258     choice = NULL;
00259     if (root == NULL) {
00260       setStatus(FAILED);
00261       setHasSolvedChildren(false);
00262       setHasFailedChildren(true);
00263       setNumberOfChildren(0);
00264       copy = root;
00265       return;
00266     }
00267     if (!root->failed())
00268       copy = root->clone();
00269     else
00270       copy = root;
00271     setStatus(UNDETERMINED);
00272     setHasSolvedChildren(false);
00273     setHasFailedChildren(false);
00274   }
00275 
00276   SpaceNode::~SpaceNode(void) {
00277     delete choice;
00278     delete copy;
00279     delete workingSpace;
00280   }
00281 
00282 
00283   int
00284   SpaceNode::getNumberOfChildNodes(NodeAllocator& na,
00285                                    BestNode* curBest, Statistics& stats,
00286                                    int c_d, int a_d) {
00287     int kids = 0;
00288     if (isUndetermined()) {
00289       stats.undetermined--;
00290       acquireSpace(curBest, c_d, a_d);
00291       switch (workingSpace->status(stats)) {
00292       case SS_FAILED:
00293         {
00294           purge();
00295           kids = 0;
00296           setHasOpenChildren(false);
00297           setHasSolvedChildren(false);
00298           setHasFailedChildren(true);
00299           setStatus(FAILED);
00300           stats.failures++;
00301           // stats.newDepth(getDepth());
00302           SpaceNode* p = getParent();
00303           if (p != NULL)
00304             p->closeChild(true, false);
00305         }
00306         break;
00307       case SS_SOLVED:
00308         {
00309           // Deletes all pending branchers
00310           (void) workingSpace->choice();
00311           kids = 0;
00312           setStatus(SOLVED);
00313           setHasOpenChildren(false);
00314           setHasSolvedChildren(true);
00315           setHasFailedChildren(false);
00316           stats.solutions++;
00317           if (curBest != NULL) {
00318             curBest->s = this;
00319           }
00320           SpaceNode* p = getParent();
00321           if (p != NULL)
00322             p->closeChild(false, true);
00323         }
00324         break;
00325       case SS_BRANCH:
00326         {
00327           choice = workingSpace->choice();
00328           kids = choice->alternatives();
00329           setHasOpenChildren(true);
00330           if (dynamic_cast<const StopChoice*>(choice)) {
00331             setStatus(STOP);
00332           } else {
00333             setStatus(BRANCH);
00334             stats.choices++;
00335           }
00336           stats.undetermined += kids;
00337         }
00338         break;
00339       }
00340       static_cast<VisualNode*>(this)->changedStatus();
00341       setNumberOfChildren(kids);
00342       for (int i=kids; i--;) {
00343         setChild(i, new (na) VisualNode());
00344       }
00345     } else {
00346       kids = getNumberOfChildren();
00347     }
00348     return kids;
00349   }
00350 
00351   int
00352   SpaceNode::getNoOfOpenChildren(void) {
00353     if (!hasOpenChildren())
00354       return 0;
00355     int noOfOpenChildren = 0;
00356     for (int i=getNumberOfChildren(); i--;)
00357       noOfOpenChildren += (static_cast<SpaceNode*>(getChild(i))->isOpen());
00358     return noOfOpenChildren;
00359   }
00360 
00361 }}
00362 
00363 // STATISTICS: gist-any