64 SpaceNode::recompute(NodeAllocator& na,
65 BestNode* curBest,
int c_d,
int a_d) {
72 lastFixpoint = curNode;
74 std::stack<Branch> stck;
77 while (curNode->
copy == NULL) {
84 curBest == NULL ? NULL : ownBest);
106 while (!stck.empty()) {
109 curDist == rdist / 2) {
114 middleNode->copy = curSpace->
clone();
117 Branch
b = stck.top(); stck.pop();
119 if(middleNode == lastFixpoint) {
123 curSpace->
commit(*
b.choice,
b.alternative);
125 if (
b.ownBest != NULL &&
b.ownBest != lastBest) {
126 b.ownBest->acquireSpace(na,curBest, c_d, a_d);
127 Space* ownBestSpace =
129 if (ownBestSpace->status() !=
SS_SOLVED) {
138 delete b.ownBest->copy;
139 b.ownBest->copy = ownBestSpace;
143 lastBest =
b.ownBest;
146 middleNode = middleNode->getChild(na,
b.alternative);
147 middleNode->setDistance(curDist);
157 BestNode* curBest,
int c_d,
int a_d) {
163 na.
best(idx) == NULL &&
164 p != NULL && curBest->
s != na.
best(parentIdx)) {
169 if (
copy == NULL && p != NULL && p->
copy != NULL &&
178 if (ownBest != NULL) {
180 Space* ownBestSpace =
192 delete ownBest->
copy;
193 ownBest->
copy = ownBestSpace;
199 if (d > c_d && c_d >= 0 &&
208 if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 &&
231 SpaceNode::closeChild(
const NodeAllocator& na,
232 bool hadFailures,
bool hadSolutions) {
236 bool allClosed =
true;
245 setHasOpenChildren(
false);
258 setHasSolvedChildren(
true);
260 while (p != NULL && !p->hasSolvedChildren()) {
261 p->setHasSolvedChildren(
true);
262 p = p->getParent(na);
267 while (p != NULL && !p->hasFailedChildren()) {
268 p->setHasFailedChildren(
true);
269 p = p->getParent(na);
277 :
Node(-1, root==NULL),
281 setHasSolvedChildren(
false);
282 setHasFailedChildren(
true);
285 setHasSolvedChildren(
false);
286 setHasFailedChildren(
false);
305 QVector<QString> labels;
311 setHasOpenChildren(
false);
312 setHasSolvedChildren(
false);
313 setHasFailedChildren(
true);
318 p->closeChild(na,
true,
false);
327 setHasOpenChildren(
false);
328 setHasSolvedChildren(
true);
329 setHasFailedChildren(
false);
331 if (curBest != NULL) {
336 p->closeChild(na,
false,
true);
343 kids =
choice->alternatives();
344 setHasOpenChildren(
true);
352 for (
int i=0; i<kids; i++) {
353 std::ostringstream oss;
355 labels.push_back(QString(oss.str().c_str()));
360 static_cast<VisualNode*
>(
this)->changedStatus(na);
372 int noOfOpenChildren = 0;
375 return noOfOpenChildren;
Choice for performing commit
Static reference to the currently best space.
BestNode(SpaceNode *s0)
Constructor.
SpaceNode * s
The currently best node found, or NULL.
Representation of a branch in the search tree.
SpaceNode * ownBest
The best space known when the branch was created.
int alternative
Alternative number.
Branch(int a, const Choice *c, SpaceNode *best=NULL)
Constructor.
T * best(int i) const
Return index of best node before i.
void setBest(int i, int b)
Set index of best node before i to b.
NodeAllocatorBase< VisualNode > NodeAllocator
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
unsigned int getNumberOfChildren(void) const
Return the number of children.
Node(int p, bool failed=false)
Construct node with parent p.
int getParent(void) const
Return the parent.
bool isUndetermined(void) const
Return whether this node is undetermined.
int getChild(int n) const
Return index of child no n.
bool isRoot(void) const
Check if this node is the root of a tree.
int getIndex(const NodeAllocator &na) const
Return index of this node.
A node of a search tree of Gecode spaces.
Space * copy
A copy used for recomputation, or NULL.
unsigned int getDistance(void) const
Return distance from copy.
unsigned int nstatus
Status of the node.
void setStatus(NodeStatus s)
Set status to s.
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
void dispose(void)
Free allocated memory.
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
bool isOpen(void)
Return whether this node still has open children.
NodeStatus getStatus(void) const
Return current status of the node.
SpaceNode(int p)
Construct node with parent p.
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
void setDistance(unsigned int d)
Set distance from copy.
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
Statistics about the search tree
int choices
Number of choice nodes.
int failures
Number of failures.
int solutions
Number of solutions.
int undetermined
Number of open, undetermined nodes.
Node class that supports visual layout
virtual void constrain(const Space &best)
Constrain function for best solution search.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
const Choice * choice(void)
Create new choice for current brancher.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
@ SS_BRANCH
Space must be branched (at least one brancher left)
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
The Gecode Interactive Search Tool.
@ UNDETERMINED
Node that has not been explored yet.
@ FAILED
Node representing failure.
@ STOP
Node representing stop point.
@ SOLVED
Node representing a solution.
@ BRANCH
Node representing a branch.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode toplevel namespace
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.
Gecode::FloatVal b(9, 12)