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-08-11 15:13:48 +0200 (Wed, 11 Aug 2010) $ by $Author: tack $ 00011 * $Revision: 11343 $ 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(NodeAllocator& na, 00066 BestNode* curBest, int c_d, int a_d) { 00067 int rdist = 0; 00068 00069 if (copy == NULL) { 00070 SpaceNode* curNode = this; 00071 SpaceNode* lastFixpoint = NULL; 00072 00073 lastFixpoint = curNode; 00074 00075 std::stack<Branch> stck; 00076 00077 int idx = getIndex(na); 00078 while (curNode->copy == NULL) { 00079 SpaceNode* parent = curNode->getParent(na); 00080 int parentIdx = curNode->getParent(); 00081 int alternative = curNode->getAlternative(na); 00082 00083 SpaceNode* ownBest = na.best(idx); 00084 Branch b(alternative, parent->choice, 00085 curBest == NULL ? NULL : ownBest); 00086 stck.push(b); 00087 00088 curNode = parent; 00089 idx = parentIdx; 00090 rdist++; 00091 } 00092 Space* curSpace = curNode->copy->clone(); 00093 curNode->setDistance(0); 00094 00095 SpaceNode* lastBest = NULL; 00096 SpaceNode* middleNode = curNode; 00097 int curDist = 0; 00098 00099 while (!stck.empty()) { 00100 if (a_d >= 0 && 00101 curDist > a_d && 00102 curDist == rdist / 2) { 00103 if (curSpace->status() == SS_FAILED) { 00104 copy = static_cast<Space*>(Support::mark(curSpace)); 00105 return rdist; 00106 } else { 00107 middleNode->copy = curSpace->clone(); 00108 } 00109 } 00110 Branch b = stck.top(); stck.pop(); 00111 00112 if(middleNode == lastFixpoint) { 00113 curSpace->status(); 00114 } 00115 00116 curSpace->commit(*b.choice, b.alternative); 00117 00118 if (b.ownBest != NULL && b.ownBest != lastBest) { 00119 b.ownBest->acquireSpace(na,curBest, c_d, a_d); 00120 Space* ownBestSpace = 00121 static_cast<Space*>(Support::funmark(b.ownBest->copy)); 00122 if (ownBestSpace->status() != SS_SOLVED) { 00123 // in the presence of weakly monotonic propagators, we may have to 00124 // use search to find the solution here 00125 ownBestSpace = Gecode::dfs(ownBestSpace); 00126 if (Support::marked(b.ownBest->copy)) { 00127 delete static_cast<Space*>(Support::unmark(b.ownBest->copy)); 00128 b.ownBest->copy = 00129 static_cast<Space*>(Support::mark(ownBestSpace)); 00130 } else { 00131 delete b.ownBest->copy; 00132 b.ownBest->copy = ownBestSpace; 00133 } 00134 } 00135 curSpace->constrain(*ownBestSpace); 00136 lastBest = b.ownBest; 00137 } 00138 curDist++; 00139 middleNode = middleNode->getChild(na,b.alternative); 00140 middleNode->setDistance(curDist); 00141 } 00142 copy = static_cast<Space*>(Support::mark(curSpace)); 00143 00144 } 00145 return rdist; 00146 } 00147 00148 void 00149 SpaceNode::acquireSpace(NodeAllocator& na, 00150 BestNode* curBest, int c_d, int a_d) { 00151 SpaceNode* p = getParent(na); 00152 int parentIdx = getParent(); 00153 int idx = getIndex(na); 00154 00155 if (getStatus() == UNDETERMINED && curBest != NULL && 00156 na.best(idx) == NULL && 00157 p != NULL && curBest->s != na.best(parentIdx)) { 00158 na.setBest(idx, curBest->s->getIndex(na)); 00159 } 00160 SpaceNode* ownBest = na.best(idx); 00161 00162 if (copy == NULL && p != NULL && p->copy != NULL && 00163 Support::marked(p->copy)) { 00164 // If parent has a working space, steal it 00165 copy = p->copy; 00166 p->copy = NULL; 00167 if (p->choice != NULL) 00168 static_cast<Space*>(Support::unmark(copy))-> 00169 commit(*p->choice, getAlternative(na)); 00170 00171 if (ownBest != NULL) { 00172 ownBest->acquireSpace(na,curBest, c_d, a_d); 00173 Space* ownBestSpace = 00174 static_cast<Space*>(Support::funmark(ownBest->copy)); 00175 if (ownBestSpace->status() != SS_SOLVED) { 00176 // in the presence of weakly monotonic propagators, we may have to 00177 // use search to find the solution here 00178 00179 ownBestSpace = Gecode::dfs(ownBestSpace); 00180 if (Support::marked(ownBest->copy)) { 00181 delete static_cast<Space*>(Support::unmark(ownBest->copy)); 00182 ownBest->copy = 00183 static_cast<Space*>(Support::mark(ownBestSpace)); 00184 } else { 00185 delete ownBest->copy; 00186 ownBest->copy = ownBestSpace; 00187 } 00188 } 00189 static_cast<Space*>(Support::unmark(copy))->constrain(*ownBestSpace); 00190 } 00191 int d = p->getDistance()+1; 00192 if (d > c_d && c_d >= 0 && 00193 static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) { 00194 copy = static_cast<Space*>(Support::unmark(copy)); 00195 d = 0; 00196 } 00197 setDistance(d); 00198 } 00199 00200 if (copy == NULL) { 00201 if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 && 00202 static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) { 00203 copy = static_cast<Space*>(Support::unmark(copy)); 00204 setDistance(0); 00205 } 00206 } 00207 00208 // always return a fixpoint 00209 static_cast<Space*>(Support::funmark(copy))->status(); 00210 if (Support::marked(copy) && p != NULL && isOpen() && 00211 p->copy != NULL && p->getNoOfOpenChildren(na) == 1 && 00212 !p->isRoot()) { 00213 // last alternative optimization 00214 00215 // If p->copy was a working space, we would have stolen it by now 00216 assert(!Support::marked(p->copy)); 00217 00218 copy = static_cast<Space*>(Support::unmark(copy)); 00219 delete p->copy; 00220 p->copy = NULL; 00221 setDistance(0); 00222 p->setDistance(p->getParent(na)->getDistance()+1); 00223 } 00224 } 00225 00226 void 00227 SpaceNode::closeChild(const NodeAllocator& na, 00228 bool hadFailures, bool hadSolutions) { 00229 setHasFailedChildren(hasFailedChildren() || hadFailures); 00230 setHasSolvedChildren(hasSolvedChildren() || hadSolutions); 00231 00232 bool allClosed = true; 00233 for (int i=getNumberOfChildren(); i--;) { 00234 if (getChild(na,i)->isOpen()) { 00235 allClosed = false; 00236 break; 00237 } 00238 } 00239 00240 if (allClosed) { 00241 setHasOpenChildren(false); 00242 for (unsigned int i=0; i<getNumberOfChildren(); i++) 00243 setHasSolvedChildren(hasSolvedChildren() || 00244 getChild(na,i)->hasSolvedChildren()); 00245 SpaceNode* p = getParent(na); 00246 if (p != NULL) { 00247 delete copy; 00248 copy = NULL; 00249 p->closeChild(na, hasFailedChildren(), hasSolvedChildren()); 00250 } 00251 } else { 00252 00253 if (hadSolutions) { 00254 setHasSolvedChildren(true); 00255 SpaceNode* p = getParent(na); 00256 while (p != NULL && !p->hasSolvedChildren()) { 00257 p->setHasSolvedChildren(true); 00258 p = p->getParent(na); 00259 } 00260 } 00261 if (hadFailures) { 00262 SpaceNode* p = getParent(na); 00263 while (p != NULL && !p->hasFailedChildren()) { 00264 p->setHasFailedChildren(true); 00265 p = p->getParent(na); 00266 } 00267 } 00268 } 00269 00270 } 00271 00272 SpaceNode::SpaceNode(Space* root) 00273 : Node(-1, root==NULL), 00274 copy(root), choice(NULL), nstatus(0) { 00275 if (root == NULL) { 00276 setStatus(FAILED); 00277 setHasSolvedChildren(false); 00278 setHasFailedChildren(true); 00279 } else { 00280 setStatus(UNDETERMINED); 00281 setHasSolvedChildren(false); 00282 setHasFailedChildren(false); 00283 } 00284 } 00285 00286 void 00287 SpaceNode::dispose(void) { 00288 delete choice; 00289 delete static_cast<Space*>(Support::funmark(copy)); 00290 } 00291 00292 00293 int 00294 SpaceNode::getNumberOfChildNodes(NodeAllocator& na, 00295 BestNode* curBest, Statistics& stats, 00296 int c_d, int a_d) { 00297 int kids = 0; 00298 if (isUndetermined()) { 00299 stats.undetermined--; 00300 acquireSpace(na, curBest, c_d, a_d); 00301 switch (static_cast<Space*>(Support::funmark(copy))->status(stats)) { 00302 case SS_FAILED: 00303 { 00304 purge(na); 00305 kids = 0; 00306 setHasOpenChildren(false); 00307 setHasSolvedChildren(false); 00308 setHasFailedChildren(true); 00309 setStatus(FAILED); 00310 stats.failures++; 00311 SpaceNode* p = getParent(na); 00312 if (p != NULL) 00313 p->closeChild(na, true, false); 00314 } 00315 break; 00316 case SS_SOLVED: 00317 { 00318 // Deletes all pending branchers 00319 (void) static_cast<Space*>(Support::funmark(copy))->choice(); 00320 kids = 0; 00321 setStatus(SOLVED); 00322 setHasOpenChildren(false); 00323 setHasSolvedChildren(true); 00324 setHasFailedChildren(false); 00325 stats.solutions++; 00326 if (curBest != NULL) { 00327 curBest->s = this; 00328 } 00329 SpaceNode* p = getParent(na); 00330 if (p != NULL) 00331 p->closeChild(na, false, true); 00332 } 00333 break; 00334 case SS_BRANCH: 00335 { 00336 choice = static_cast<Space*>(Support::funmark(copy))->choice(); 00337 kids = choice->alternatives(); 00338 setHasOpenChildren(true); 00339 if (dynamic_cast<const StopChoice*>(choice)) { 00340 setStatus(STOP); 00341 } else { 00342 setStatus(BRANCH); 00343 stats.choices++; 00344 } 00345 stats.undetermined += kids; 00346 } 00347 break; 00348 } 00349 static_cast<VisualNode*>(this)->changedStatus(na); 00350 setNumberOfChildren(kids, na); 00351 } else { 00352 kids = getNumberOfChildren(); 00353 } 00354 return kids; 00355 } 00356 00357 int 00358 SpaceNode::getNoOfOpenChildren(const NodeAllocator& na) { 00359 if (!hasOpenChildren()) 00360 return 0; 00361 int noOfOpenChildren = 0; 00362 for (int i=getNumberOfChildren(); i--;) 00363 noOfOpenChildren += (getChild(na,i)->isOpen()); 00364 return noOfOpenChildren; 00365 } 00366 00367 }} 00368 00369 // STATISTICS: gist-any