spacenode.cpp
Go to the documentation of this file.
/* -*- 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 {
class Branch {
public:
int alternative;
SpaceNode* ownBest;
const Choice* choice;
Branch(int a, const Choice* c, SpaceNode* best = NULL)
: 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 == NULL) {
SpaceNode* curNode = this;
SpaceNode* lastFixpoint = NULL;
lastFixpoint = curNode;
std::stack<Branch> stck;
int idx = getIndex(na);
while (curNode->copy == NULL) {
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 == NULL ? NULL : 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 = NULL;
a_d = -1;
} else {
curSpace = curNode->copy->clone();
curNode->setDistance(0);
}
SpaceNode* lastBest = NULL;
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 != NULL && 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 != NULL &&
na.best(idx) == NULL &&
p != NULL && curBest->s != na.best(parentIdx)) {
na.setBest(idx, curBest->s->getIndex(na));
}
SpaceNode* ownBest = na.best(idx);
if (copy == NULL && p != NULL && p->copy != NULL &&
Support::marked(p->copy)) {
// If parent has a working space, steal it
copy = p->copy;
p->copy = NULL;
if (p->choice != NULL)
static_cast<Space*>(Support::unmark(copy))->
commit(*p->choice, getAlternative(na));
if (ownBest != NULL) {
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 == NULL) {
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 != NULL && isOpen() &&
p->copy != NULL && 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 = NULL;
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 != NULL) {
delete static_cast<Space*>(Support::funmark(copy));
copy = NULL;
p->closeChild(na, hasFailedChildren(), hasSolvedChildren());
}
} else {
if (hadSolutions) {
setHasSolvedChildren(true);
SpaceNode* p = getParent(na);
while (p != NULL && !p->hasSolvedChildren()) {
p->setHasSolvedChildren(true);
p = p->getParent(na);
}
}
if (hadFailures) {
SpaceNode* p = getParent(na);
while (p != NULL && !p->hasFailedChildren()) {
p->setHasFailedChildren(true);
p = p->getParent(na);
}
}
}
}
SpaceNode::SpaceNode(Space* root)
: Node(-1, root==NULL),
copy(root), choice(NULL), nstatus(0) {
if (root == NULL) {
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 != NULL)
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 != NULL) {
curBest->s = this;
}
SpaceNode* p = getParent(na);
if (p != NULL)
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
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::Gist::BestNode
Static reference to the currently best space.
Definition spacenode.hh:80
Gecode::Gist::BestNode::BestNode
BestNode(SpaceNode *s0)
Constructor.
Definition spacenode.cpp:61
Gecode::Gist::BestNode::s
SpaceNode * s
The currently best node found, or NULL.
Definition spacenode.hh:83
Gecode::Gist::Branch
Representation of a branch in the search tree.
Definition spacenode.cpp:46
Gecode::Gist::Branch::choice
const Choice * choice
Definition spacenode.cpp:52
Gecode::Gist::Branch::ownBest
SpaceNode * ownBest
The best space known when the branch was created.
Definition spacenode.cpp:51
Gecode::Gist::Branch::alternative
int alternative
Alternative number.
Definition spacenode.cpp:49
Gecode::Gist::Branch::Branch
Branch(int a, const Choice *c, SpaceNode *best=NULL)
Constructor.
Definition spacenode.cpp:55
Gecode::Gist::NodeAllocatorBase::best
T * best(int i) const
Return index of best node before i.
Definition node.hpp:97
Gecode::Gist::NodeAllocatorBase::setBest
void setBest(int i, int b)
Set index of best node before i to b.
Definition node.hpp:106
Gecode::Gist::Node::NodeAllocator
NodeAllocatorBase< VisualNode > NodeAllocator
Definition node.hh:143
Gecode::Gist::Node::setNumberOfChildren
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
Definition node.cpp:42
Gecode::Gist::Node::getNumberOfChildren
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition node.hpp:214
Gecode::Gist::Node::Node
Node(int p, bool failed=false)
Construct node with parent p.
Definition node.hpp:175
Gecode::Gist::Node::getParent
int getParent(void) const
Return the parent.
Definition node.hpp:182
Gecode::Gist::Node::isUndetermined
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition node.hpp:192
Gecode::Gist::Node::getChild
int getChild(int n) const
Return index of child no n.
Definition node.hpp:195
Gecode::Gist::Node::isRoot
bool isRoot(void) const
Check if this node is the root of a tree.
Definition node.hpp:211
Gecode::Gist::Node::getIndex
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition node.hpp:227
Gecode::Gist::SpaceNode
A node of a search tree of Gecode spaces.
Definition spacenode.hh:89
Gecode::Gist::SpaceNode::copy
Space * copy
A copy used for recomputation, or NULL.
Definition spacenode.hh:96
Gecode::Gist::SpaceNode::choice
const Choice * choice
Definition spacenode.hh:98
Gecode::Gist::SpaceNode::getDistance
unsigned int getDistance(void) const
Return distance from copy.
Definition spacenode.hpp:84
Gecode::Gist::SpaceNode::nstatus
unsigned int nstatus
Status of the node.
Definition spacenode.hh:106
Gecode::Gist::SpaceNode::setStatus
void setStatus(NodeStatus s)
Set status to s.
Definition spacenode.hpp:65
Gecode::Gist::SpaceNode::hasFailedChildren
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
Definition spacenode.hpp:144
Gecode::Gist::SpaceNode::dispose
void dispose(void)
Free allocated memory.
Definition spacenode.cpp:291
Gecode::Gist::SpaceNode::acquireSpace
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
Definition spacenode.cpp:156
Gecode::Gist::SpaceNode::getNumberOfChildNodes
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
Definition spacenode.cpp:298
Gecode::Gist::SpaceNode::hasSolvedChildren
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Definition spacenode.hpp:149
Gecode::Gist::SpaceNode::getAlternative
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
Definition spacenode.hpp:169
Gecode::Gist::SpaceNode::isOpen
bool isOpen(void)
Return whether this node still has open children.
Definition spacenode.hpp:138
Gecode::Gist::SpaceNode::getStatus
NodeStatus getStatus(void) const
Return current status of the node.
Definition spacenode.hpp:71
Gecode::Gist::SpaceNode::SpaceNode
SpaceNode(int p)
Construct node with parent p.
Definition spacenode.hpp:89
Gecode::Gist::SpaceNode::purge
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
Definition spacenode.hpp:120
Gecode::Gist::SpaceNode::setDistance
void setDistance(unsigned int d)
Set distance from copy.
Definition spacenode.hpp:76
Gecode::Gist::SpaceNode::hasOpenChildren
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
Definition spacenode.hpp:154
Gecode::Gist::SpaceNode::getNoOfOpenChildren
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
Definition spacenode.cpp:369
Gecode::Gist::Statistics
Statistics about the search tree
Definition spacenode.hh:59
Gecode::Gist::Statistics::choices
int choices
Number of choice nodes.
Definition spacenode.hh:66
Gecode::Gist::Statistics::failures
int failures
Number of failures.
Definition spacenode.hh:64
Gecode::Gist::Statistics::solutions
int solutions
Number of solutions.
Definition spacenode.hh:62
Gecode::Gist::Statistics::undetermined
int undetermined
Number of open, undetermined nodes.
Definition spacenode.hh:68
Gecode::Gist::StopChoice
Choice for StopBrancher
Definition stopbrancher.hh:40
Gecode::Gist::VisualNode
Node class that supports visual layout
Definition visualnode.hh:125
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::constrain
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
Gecode::Space::print
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:655
Gecode::Space::choice
const Choice * choice(void)
Create new choice for current brancher.
Definition core.cpp:537
Gecode::Space::commit
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3232
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::Space::clone
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
Gecode::SS_BRANCH
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
Gecode::SS_SOLVED
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Gist
The Gecode Interactive Search Tool.
Gecode::Gist::UNDETERMINED
@ UNDETERMINED
Node that has not been explored yet.
Definition spacenode.hh:48
Gecode::Gist::FAILED
@ FAILED
Node representing failure.
Definition spacenode.hh:46
Gecode::Gist::STOP
@ STOP
Node representing stop point.
Definition spacenode.hh:49
Gecode::Gist::SOLVED
@ SOLVED
Node representing a solution.
Definition spacenode.hh:45
Gecode::Gist::BRANCH
@ BRANCH
Node representing a branch.
Definition spacenode.hh:47
Gecode::Support::unmark
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
Definition marked-pointer.hpp:63
Gecode::Support::funmark
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
Definition marked-pointer.hpp:72
Gecode::Support::mark
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Definition marked-pointer.hpp:58
Gecode::Support::marked
bool marked(void *p)
Check whether p is marked.
Definition marked-pointer.hpp:54
Gecode
Gecode toplevel namespace
Gecode::dfs
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73
Test::Float::Arithmetic::b
Gecode::FloatVal b(9, 12)
search.hh
spacenode.hh
stopbrancher.hh
visualnode.hh