Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
12 kB · 380 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Guido Tack <tack@gecode.org> * * Copyright: * Guido Tack, 2006 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <gecode/gist/spacenode.hh>#include <gecode/gist/visualnode.hh>#include <gecode/gist/stopbrancher.hh>#include <gecode/search.hh>#include <stack>
#include <QString>#include <QVector>
namespace Gecode { namespace Gist {
/// \brief Representation of a branch in the search tree class Branch { public: /// Alternative number int alternative; /// The best space known when the branch was created SpaceNode* ownBest; const Choice* choice;
/// Constructor Branch(int a, const Choice* c, SpaceNode* best = nullptr) : alternative(a), ownBest(best) { choice = c; } };
BestNode::BestNode(SpaceNode* s0) : s(s0) {}
int SpaceNode::recompute(NodeAllocator& na, BestNode* curBest, int c_d, int a_d) { int rdist = 0;
if (copy == nullptr) { SpaceNode* curNode = this; SpaceNode* lastFixpoint = nullptr;
lastFixpoint = curNode;
std::stack<Branch> stck;
int idx = getIndex(na); while (curNode->copy == nullptr) { SpaceNode* parent = curNode->getParent(na); int parentIdx = curNode->getParent(); int alternative = curNode->getAlternative(na);
SpaceNode* ownBest = na.best(idx); Branch b(alternative, parent->choice, curBest == nullptr ? nullptr : ownBest); stck.push(b);
curNode = parent; idx = parentIdx; rdist++; }
Space* curSpace; if (Support::marked(curNode->copy)) { curSpace = static_cast<Space*>(Support::unmark(curNode->copy)); curNode->copy = nullptr; a_d = -1; } else { curSpace = curNode->copy->clone(); curNode->setDistance(0); }
SpaceNode* lastBest = nullptr; SpaceNode* middleNode = curNode; int curDist = 0;
while (!stck.empty()) { if (a_d >= 0 && curDist > a_d && curDist == rdist / 2) { if (curSpace->status() == SS_FAILED) { copy = static_cast<Space*>(Support::mark(curSpace)); return rdist; } else { middleNode->copy = curSpace->clone(); } } Branch b = stck.top(); stck.pop();
if(middleNode == lastFixpoint) { curSpace->status(); }
curSpace->commit(*b.choice, b.alternative);
if (b.ownBest != nullptr && b.ownBest != lastBest) { b.ownBest->acquireSpace(na,curBest, c_d, a_d); Space* ownBestSpace = static_cast<Space*>(Support::funmark(b.ownBest->copy)); if (ownBestSpace->status() != SS_SOLVED) { // in the presence of weakly monotonic propagators, we may have to // use search to find the solution here ownBestSpace = Gecode::dfs(ownBestSpace); if (Support::marked(b.ownBest->copy)) { delete static_cast<Space*>(Support::unmark(b.ownBest->copy)); b.ownBest->copy = static_cast<Space*>(Support::mark(ownBestSpace)); } else { delete b.ownBest->copy; b.ownBest->copy = ownBestSpace; } } curSpace->constrain(*ownBestSpace); lastBest = b.ownBest; } curDist++; middleNode = middleNode->getChild(na,b.alternative); middleNode->setDistance(curDist); } copy = static_cast<Space*>(Support::mark(curSpace));
} return rdist; }
void SpaceNode::acquireSpace(NodeAllocator& na, BestNode* curBest, int c_d, int a_d) { SpaceNode* p = getParent(na); int parentIdx = getParent(); int idx = getIndex(na);
if (getStatus() == UNDETERMINED && curBest != nullptr && na.best(idx) == nullptr && p != nullptr && curBest->s != na.best(parentIdx)) { na.setBest(idx, curBest->s->getIndex(na)); } SpaceNode* ownBest = na.best(idx);
if (copy == nullptr && p != nullptr && p->copy != nullptr && Support::marked(p->copy)) { // If parent has a working space, steal it copy = p->copy; p->copy = nullptr; if (p->choice != nullptr) static_cast<Space*>(Support::unmark(copy))-> commit(*p->choice, getAlternative(na));
if (ownBest != nullptr) { ownBest->acquireSpace(na,curBest, c_d, a_d); Space* ownBestSpace = static_cast<Space*>(Support::funmark(ownBest->copy)); if (ownBestSpace->status() != SS_SOLVED) { // in the presence of weakly monotonic propagators, we may have to // use search to find the solution here
ownBestSpace = Gecode::dfs(ownBestSpace); if (Support::marked(ownBest->copy)) { delete static_cast<Space*>(Support::unmark(ownBest->copy)); ownBest->copy = static_cast<Space*>(Support::mark(ownBestSpace)); } else { delete ownBest->copy; ownBest->copy = ownBestSpace; } } static_cast<Space*>(Support::unmark(copy))->constrain(*ownBestSpace); } int d = p->getDistance()+1; if (d > c_d && c_d >= 0 && static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) { copy = static_cast<Space*>(Support::unmark(copy)); d = 0; } setDistance(d); }
if (copy == nullptr) { if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 && static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) { copy = static_cast<Space*>(Support::unmark(copy)); setDistance(0); } }
// always return a fixpoint static_cast<Space*>(Support::funmark(copy))->status(); if (Support::marked(copy) && p != nullptr && isOpen() && p->copy != nullptr && p->getNoOfOpenChildren(na) == 1 && !p->isRoot()) { // last alternative optimization
copy = static_cast<Space*>(Support::unmark(copy)); delete static_cast<Space*>(Support::funmark(p->copy)); p->copy = nullptr; setDistance(0); p->setDistance(p->getParent(na)->getDistance()+1); } }
void SpaceNode::closeChild(const NodeAllocator& na, bool hadFailures, bool hadSolutions) { setHasFailedChildren(hasFailedChildren() || hadFailures); setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
bool allClosed = true; for (int i=getNumberOfChildren(); i--;) { if (getChild(na,i)->isOpen()) { allClosed = false; break; } }
if (allClosed) { setHasOpenChildren(false); for (unsigned int i=0; i<getNumberOfChildren(); i++) setHasSolvedChildren(hasSolvedChildren() || getChild(na,i)->hasSolvedChildren()); SpaceNode* p = getParent(na); if (p != nullptr) { delete static_cast<Space*>(Support::funmark(copy)); copy = nullptr; p->closeChild(na, hasFailedChildren(), hasSolvedChildren()); } } else {
if (hadSolutions) { setHasSolvedChildren(true); SpaceNode* p = getParent(na); while (p != nullptr && !p->hasSolvedChildren()) { p->setHasSolvedChildren(true); p = p->getParent(na); } } if (hadFailures) { SpaceNode* p = getParent(na); while (p != nullptr && !p->hasFailedChildren()) { p->setHasFailedChildren(true); p = p->getParent(na); } } }
}
SpaceNode::SpaceNode(Space* root) : Node(-1, root==nullptr), copy(root), choice(nullptr), nstatus(0) { if (root == nullptr) { setStatus(FAILED); setHasSolvedChildren(false); setHasFailedChildren(true); } else { setStatus(UNDETERMINED); setHasSolvedChildren(false); setHasFailedChildren(false); } }
void SpaceNode::dispose(void) { delete choice; delete static_cast<Space*>(Support::funmark(copy)); }
int SpaceNode::getNumberOfChildNodes(NodeAllocator& na, BestNode* curBest, Statistics& stats, int c_d, int a_d) { int kids = 0; if (isUndetermined()) { stats.undetermined--; acquireSpace(na, curBest, c_d, a_d); QVector<QString> labels; switch (static_cast<Space*>(Support::funmark(copy))->status(stats)) { case SS_FAILED: { purge(na); kids = 0; setHasOpenChildren(false); setHasSolvedChildren(false); setHasFailedChildren(true); setStatus(FAILED); stats.failures++; SpaceNode* p = getParent(na); if (p != nullptr) p->closeChild(na, true, false); } break; case SS_SOLVED: { // Deletes all pending branchers (void) static_cast<Space*>(Support::funmark(copy))->choice(); kids = 0; setStatus(SOLVED); setHasOpenChildren(false); setHasSolvedChildren(true); setHasFailedChildren(false); stats.solutions++; if (curBest != nullptr) { curBest->s = this; } SpaceNode* p = getParent(na); if (p != nullptr) p->closeChild(na, false, true); } break; case SS_BRANCH: { Space* s = static_cast<Space*>(Support::funmark(copy)); choice = s->choice(); kids = choice->alternatives(); setHasOpenChildren(true); if (dynamic_cast<const StopChoice*>(choice)) { setStatus(STOP); } else { setStatus(BRANCH); stats.choices++; } stats.undetermined += kids; for (int i=0; i<kids; i++) { std::ostringstream oss; s->print(*choice,i,oss); labels.push_back(QString(oss.str().c_str())); } } break; } static_cast<VisualNode*>(this)->changedStatus(na); setNumberOfChildren(kids, na); } else { kids = getNumberOfChildren(); } return kids; }
int SpaceNode::getNoOfOpenChildren(const NodeAllocator& na) { if (!hasOpenChildren()) return 0; int noOfOpenChildren = 0; for (int i=getNumberOfChildren(); i--;) noOfOpenChildren += (getChild(na,i)->isOpen()); return noOfOpenChildren; }
}}
// STATISTICS: gist-any