Generated on Fri Oct 19 11:25:00 2018 for Gecode by doxygen 1.6.3

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