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