spacenode.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
00117
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
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
00155
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
00180 workingSpace->status();
00181 if (copy == NULL && p != NULL && isOpen() &&
00182 p->copy != NULL && p->getNoOfOpenChildren() == 1 &&
00183 p->getParent() != NULL) {
00184
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
00197
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
00302 SpaceNode* p = getParent();
00303 if (p != NULL)
00304 p->closeChild(true, false);
00305 }
00306 break;
00307 case SS_SOLVED:
00308 {
00309
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