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/search.hh>
00041 #include <stack>
00042
00043 namespace Gecode { namespace Gist {
00044
00045
00046 enum BranchKind {
00047 BK_NORMAL, BK_SPECIAL_IN, BK_SPECIAL_OUT, BK_STEP
00048 };
00049
00051 class Branch {
00052 public:
00054 int alternative;
00056 SpaceNode* ownBest;
00057 const BranchKind branchKind;
00058 union {
00060 const SpecialDesc* special;
00062 const Choice* branch;
00064 const StepDesc* step;
00065 } desc;
00066
00068 Branch(int a, const Choice* c,
00069 SpaceNode* best = NULL, BranchKind bk = BK_NORMAL)
00070 : alternative(a), ownBest(best), branchKind(bk) {
00071 desc.branch = c;
00072 }
00073 Branch(int a, const SpecialDesc* d, BranchKind bk, SpaceNode* best = NULL)
00074 : alternative(a), ownBest(best), branchKind(bk) {
00075 desc.special = d;
00076 }
00077 Branch(int a, const StepDesc* d, BranchKind bk, SpaceNode* best = NULL)
00078 : alternative(a), ownBest(best), branchKind(bk) {
00079 desc.step = d;
00080 }
00081 };
00082
00083 StepDesc::StepDesc(int steps) : noOfSteps(steps), debug(false) { }
00084
00085 void
00086 StepDesc::toggleDebug(void) {
00087 debug = !debug;
00088 }
00089
00090 SpecialDesc::SpecialDesc(std::string varName, int rel0, int v0)
00091 : vn(varName), v(v0), rel(rel0) { }
00092
00093 BestNode::BestNode(SpaceNode* s0) : s(s0) {}
00094
00095 int
00096 SpaceNode::recompute(BestNode* curBest, int c_d, int a_d) {
00097 int rdist = 0;
00098
00099 if (workingSpace == NULL) {
00100 SpaceNode* curNode = this;
00101 SpaceNode* lastFixpoint = NULL;
00102
00103 if(curNode->getStatus() != SPECIAL && curNode->getStatus() != STEP) {
00104 lastFixpoint = curNode;
00105 }
00106
00107 std::stack<Branch> stck;
00108 bool specialNodeOnPath = false;
00109
00110 while (curNode->copy == NULL) {
00111 SpaceNode* parent = curNode->getParent();
00112 int alternative = curNode->getAlternative();
00113
00114 if (curNode->getStatus() == STEP) {
00115 Branch b(alternative, curNode->desc.step, BK_STEP);
00116 stck.push(b);
00117 if (lastFixpoint == NULL && parent->getStatus() == BRANCH) {
00118 lastFixpoint = parent;
00119 }
00120 } else if (curNode->getStatus() == SPECIAL) {
00121 Branch b(alternative, curNode->desc.special, BK_SPECIAL_IN);
00122 stck.push(b);
00123 if(lastFixpoint == NULL && parent->getStatus() == BRANCH) {
00124 lastFixpoint = parent;
00125 }
00126 specialNodeOnPath = true;
00127
00128 } else if (parent->getStatus() == SPECIAL || parent->getStatus() == STEP) {
00129 Branch b(alternative, curNode->desc.special, BK_SPECIAL_OUT);
00130 stck.push(b);
00131 } else {
00132 Branch b(alternative, parent->desc.branch,
00133 curBest == NULL ? NULL : curNode->ownBest);
00134 stck.push(b);
00135 }
00136
00137 curNode = parent;
00138 rdist++;
00139 }
00140 Space* curSpace = curNode->copy->clone();
00141 curNode->setDistance(0);
00142
00143 SpaceNode* lastBest = NULL;
00144 SpaceNode* middleNode = curNode;
00145 int curDist = 0;
00146
00147 while (!stck.empty()) {
00148 if (a_d >= 0 &&
00149 curDist > a_d &&
00150 middleNode->getStatus() != SPECIAL &&
00151 middleNode->getStatus() != STEP &&
00152 curDist == rdist / 2) {
00153 if (curSpace->status() == SS_FAILED) {
00154 workingSpace = curSpace;
00155 return rdist;
00156 } else {
00157 middleNode->copy = curSpace->clone();
00158 }
00159 }
00160 Branch b = stck.top(); stck.pop();
00161
00162 if(middleNode == lastFixpoint) {
00163 curSpace->status();
00164 }
00165
00166 switch (b.branchKind) {
00167 case BK_NORMAL:
00168 {
00169 curSpace->commit(*b.desc.branch, b.alternative);
00170 }
00171 break;
00172 case BK_STEP:
00173 {
00174 }
00175 break;
00176 case BK_SPECIAL_IN:
00177 {
00178 }
00179 break;
00180 case BK_SPECIAL_OUT:
00181
00182 break;
00183 }
00184
00185 if (b.ownBest != NULL && b.ownBest != lastBest) {
00186 b.ownBest->acquireSpace(curBest, c_d, a_d);
00187 if (b.ownBest->workingSpace->status() != SS_SOLVED) {
00188
00189
00190 Space* dfsSpace = Gecode::dfs(b.ownBest->workingSpace);
00191 delete b.ownBest->workingSpace;
00192 b.ownBest->workingSpace = dfsSpace;
00193 }
00194 curSpace->constrain(*b.ownBest->workingSpace);
00195 lastBest = b.ownBest;
00196 }
00197 curDist++;
00198 middleNode = middleNode->getChild(b.alternative);
00199 middleNode->setDistance(curDist);
00200 }
00201 workingSpace = curSpace;
00202
00203 }
00204 return rdist;
00205 }
00206
00207 void
00208 SpaceNode::acquireSpace(BestNode* curBest, int c_d, int a_d) {
00209 SpaceNode* p = getParent();
00210
00211 if (getStatus() == UNDETERMINED && curBest != NULL && ownBest == NULL &&
00212 p != NULL && curBest->s != p->ownBest) {
00213 ownBest = curBest->s;
00214 }
00215
00216 if (getStatus() != SPECIAL && getStatus() != STEP) {
00217 if (workingSpace == NULL && p != NULL && p->workingSpace != NULL) {
00218
00219 workingSpace = p->workingSpace;
00220 p->workingSpace = NULL;
00221 if (p->desc.branch != NULL)
00222 workingSpace->commit(*p->desc.branch, getAlternative());
00223
00224 if (ownBest != NULL) {
00225 ownBest->acquireSpace(curBest, c_d, a_d);
00226 if (ownBest->workingSpace->status() != SS_SOLVED) {
00227
00228
00229 Space* dfsSpace = Gecode::dfs(ownBest->workingSpace);
00230 delete ownBest->workingSpace;
00231 ownBest->workingSpace = dfsSpace;
00232 }
00233 workingSpace->constrain(*ownBest->workingSpace);
00234 }
00235 int d = p->getDistance()+1;
00236 if (d > c_d && c_d >= 0 &&
00237 getStatus() != SPECIAL && getStatus() != STEP &&
00238 workingSpace->status() == SS_BRANCH) {
00239 copy = workingSpace->clone();
00240 d = 0;
00241 }
00242 setDistance(d);
00243 }
00244 }
00245
00246 if (workingSpace == NULL) {
00247 if (recompute(curBest, c_d, a_d) > c_d && c_d >= 0 &&
00248 getStatus() != SPECIAL && getStatus() != STEP &&
00249 workingSpace->status() == SS_BRANCH) {
00250 copy = workingSpace->clone();
00251 setDistance(0);
00252 }
00253 }
00254
00255 if (getStatus() != SPECIAL && getStatus() != STEP) {
00256
00257 workingSpace->status();
00258 if (copy == NULL && p != NULL && isOpen() &&
00259 p->copy != NULL && p->getNoOfOpenChildren() == 1 &&
00260 p->getParent() != NULL) {
00261
00262 copy = p->copy;
00263 p->copy = NULL;
00264 setDistance(0);
00265 p->setDistance(p->getParent()->getDistance()+1);
00266
00267 if(p->desc.branch != NULL)
00268 copy->commit(*p->desc.branch, getAlternative());
00269
00270 if (ownBest != NULL) {
00271 ownBest->acquireSpace(curBest, c_d, a_d);
00272 if (ownBest->workingSpace->status() != SS_SOLVED) {
00273
00274
00275 Space* dfsSpace = Gecode::dfs(ownBest->workingSpace);
00276 delete ownBest->workingSpace;
00277 ownBest->workingSpace = dfsSpace;
00278 }
00279 copy->constrain(*ownBest->workingSpace);
00280 }
00281 if (copy->status() == SS_FAILED) {
00282 delete copy;
00283 copy = NULL;
00284 }
00285 }
00286 }
00287 }
00288
00289 void
00290 SpaceNode::closeChild(bool hadFailures, bool hadSolutions) {
00291 setHasFailedChildren(hasFailedChildren() || hadFailures);
00292 setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
00293
00294 bool allClosed = true;
00295 for (int i=getNumberOfChildren(); i--;) {
00296 if (static_cast<SpaceNode*>(getChild(i))->isOpen()) {
00297 allClosed = false;
00298 break;
00299 }
00300 }
00301
00302 if (allClosed) {
00303 setHasOpenChildren(false);
00304 for (unsigned int i=0; i<getNumberOfChildren(); i++)
00305 setHasSolvedChildren(hasSolvedChildren() ||
00306 static_cast<SpaceNode*>(getChild(i))->hasSolvedChildren());
00307 SpaceNode* p = static_cast<SpaceNode*>(getParent());
00308 if (p != NULL) {
00309 delete copy;
00310 copy = NULL;
00311 p->closeChild(hasFailedChildren(), hasSolvedChildren());
00312 }
00313 } else {
00314
00315 if (hadSolutions) {
00316 setHasSolvedChildren(true);
00317 SpaceNode* p = getParent();
00318 while (p != NULL && !p->hasSolvedChildren()) {
00319 p->setHasSolvedChildren(true);
00320 p = p->getParent();
00321 }
00322 }
00323 if (hadFailures) {
00324 SpaceNode* p = getParent();
00325 while (p != NULL && !p->hasFailedChildren()) {
00326 p->setHasFailedChildren(true);
00327 p = p->getParent();
00328 }
00329 }
00330 }
00331
00332 }
00333
00334 SpaceNode::SpaceNode(Space* root)
00335 : workingSpace(root), ownBest(NULL), nstatus(0) {
00336 desc.branch = NULL;
00337 if (root == NULL) {
00338 setStatus(FAILED);
00339 setHasSolvedChildren(false);
00340 setHasFailedChildren(true);
00341 setNumberOfChildren(0);
00342 copy = root;
00343 return;
00344 }
00345 if (!root->failed())
00346 copy = root->clone();
00347 else
00348 copy = root;
00349 setStatus(UNDETERMINED);
00350 setHasSolvedChildren(false);
00351 setHasFailedChildren(false);
00352 }
00353
00354 SpaceNode::~SpaceNode(void) {
00355 if(getStatus() == SPECIAL)
00356 delete desc.special;
00357 else if (getStatus() == STEP)
00358 delete desc.step;
00359 else
00360 delete desc.branch;
00361 delete copy;
00362 delete workingSpace;
00363 }
00364
00365
00366 int
00367 SpaceNode::getNumberOfChildNodes(NodeAllocator& na,
00368 BestNode* curBest, Statistics& stats,
00369 int c_d, int a_d) {
00370 int kids = 0;
00371 if (isUndetermined()) {
00372 stats.undetermined--;
00373 acquireSpace(curBest, c_d, a_d);
00374 switch (workingSpace->status(stats)) {
00375 case SS_FAILED:
00376 {
00377 purge();
00378 kids = 0;
00379 setHasOpenChildren(false);
00380 setHasSolvedChildren(false);
00381 setHasFailedChildren(true);
00382 setStatus(FAILED);
00383 stats.failures++;
00384
00385 SpaceNode* p = getParent();
00386 if (p != NULL)
00387 p->closeChild(true, false);
00388 }
00389 break;
00390 case SS_SOLVED:
00391 {
00392
00393 (void) workingSpace->choice();
00394 kids = 0;
00395 setStatus(SOLVED);
00396 setHasOpenChildren(false);
00397 setHasSolvedChildren(true);
00398 setHasFailedChildren(false);
00399 stats.solutions++;
00400 if (curBest != NULL) {
00401 curBest->s = this;
00402 }
00403 SpaceNode* p = getParent();
00404 if (p != NULL)
00405 p->closeChild(false, true);
00406 }
00407 break;
00408 case SS_BRANCH:
00409 desc.branch = workingSpace->choice();
00410 kids = desc.branch->alternatives();
00411 setHasOpenChildren(true);
00412 setStatus(BRANCH);
00413 stats.choices++;
00414 stats.undetermined += kids;
00415 break;
00416 }
00417 static_cast<VisualNode*>(this)->changedStatus();
00418 setNumberOfChildren(kids);
00419 for (int i=kids; i--;) {
00420 setChild(i, new (na) VisualNode());
00421 }
00422 } else {
00423 kids = getNumberOfChildren();
00424 }
00425 return kids;
00426 }
00427
00428 int
00429 SpaceNode::getNoOfOpenChildren(void) {
00430 if (!hasOpenChildren())
00431 return 0;
00432 int noOfOpenChildren = 0;
00433 for (int i=getNumberOfChildren(); i--;)
00434 noOfOpenChildren += (static_cast<SpaceNode*>(getChild(i))->isOpen());
00435 return noOfOpenChildren;
00436 }
00437
00438 }}
00439
00440