Go to the documentation of this file.
43 namespace Gecode {
namespace Gist {
64 SpaceNode::recompute(NodeAllocator& na,
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) {
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);
163 na.
best(idx) == NULL &&
164 p != NULL && curBest->
s != na.
best(parentIdx)) {
169 if (
copy == NULL &&
p != NULL &&
p->copy != NULL &&
174 if (
p->choice != NULL)
178 if (ownBest != NULL) {
180 Space* ownBestSpace =
192 delete ownBest->
copy;
193 ownBest->
copy = ownBestSpace;
198 int d =
p->getDistance()+1;
208 if (recompute(na, curBest,
c_d,
a_d) >
c_d &&
c_d >= 0 &&
218 p->copy != NULL &&
p->getNoOfOpenChildren(na) == 1 &&
226 p->setDistance(
p->getParent(na)->getDistance()+1);
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),
278 copy(root), choice(NULL), nstatus(0) {
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);
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;
@ UNDETERMINED
Node that has not been explored yet.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
@ SS_SOLVED
Space is solved (no brancher left)
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
@ STOP
Node representing stop point.
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Node class that supports visual layout
virtual void constrain(const Space &best)
Constrain function for best solution search.
const Choice * choice(void)
Create new choice for current brancher.
unsigned int alternatives(void) const
Return number of alternatives.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
NodeStatus getStatus(void) const
Return current status of the node.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
@ SS_BRANCH
Space must be branched (at least one brancher left)
void dispose(void)
Free allocated memory.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
virtual Space * copy(void)=0
Copying member function.
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
int getIndex(const NodeAllocator &na) const
Return index of this node.
int failures
Number of failures.
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
Base class for nodes of the search tree.
SpaceNode * s
The currently best node found, or NULL.
Gecode toplevel namespace
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
bool isOpen(void)
Return whether this node still has open children.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
T * best(int i) const
Return index of best node before i.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
Space * copy
A copy used for recomputation, or NULL.
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
int choices
Number of choice nodes.
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Static reference to the currently best space.
int getChild(int n) const
Return index of child no n.
Representation of a branch in the search tree.
int solutions
Number of solutions.
@ BRANCH
Node representing a branch.
SpaceNode * ownBest
The best space known when the branch was created.
int getParent(void) const
Return the parent.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
void setBest(int i, int b)
Set index of best node before i to b.
unsigned int getNumberOfChildren(void) const
Return the number of children.
bool isUndetermined(void) const
Return whether this node is undetermined.
A node of a search tree of Gecode spaces.
Statistics about the search tree
BestNode(SpaceNode *s0)
Constructor.
SpaceNode(int p)
Construct node with parent p.
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
void setDistance(unsigned int d)
Set distance from copy.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
void setStatus(NodeStatus s)
Set status to s.
Gecode::FloatVal c(-8, 8)
Choice for performing commit
Branch(int a, const Choice *c, SpaceNode *best=NULL)
Constructor.
@ FAILED
Node representing failure.
Gecode::IntArgs i({1, 2, 3, 4})
@ SS_FAILED
Space is failed
int p
Number of positive literals for node type.
int undetermined
Number of open, undetermined nodes.
bool marked(void *p)
Check whether p is marked.
@ SOLVED
Node representing a solution.
int alternative
Alternative number.