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