47 namespace Gecode {
namespace Gist {
60 : alternative(a), ownBest(best) {
68 SpaceNode::recompute(NodeAllocator& na,
76 lastFixpoint = curNode;
78 std::stack<Branch> stck;
81 while (curNode->
copy == NULL) {
88 curBest == NULL ? NULL : ownBest);
110 while (!stck.empty()) {
113 curDist == rdist / 2) {
121 Branch
b = stck.top(); stck.pop();
123 if(middleNode == lastFixpoint) {
127 curSpace->
commit(*b.choice, b.alternative);
129 if (b.ownBest != NULL && b.ownBest != lastBest) {
130 b.ownBest->acquireSpace(na,curBest, c_d, a_d);
131 Space* ownBestSpace =
133 if (ownBestSpace->status() !=
SS_SOLVED) {
142 delete b.ownBest->copy;
143 b.ownBest->copy = ownBestSpace;
147 lastBest = b.ownBest;
150 middleNode = middleNode->getChild(na,b.alternative);
151 middleNode->setDistance(curDist);
161 BestNode* curBest,
int c_d,
int a_d) {
167 na.
best(idx) == NULL &&
168 p != NULL && curBest->
s != na.
best(parentIdx)) {
173 if (
copy == NULL && p != NULL && p->
copy != NULL &&
182 if (ownBest != NULL) {
184 Space* ownBestSpace =
196 delete ownBest->
copy;
197 ownBest->
copy = ownBestSpace;
203 if (d > c_d && c_d >= 0 &&
212 if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 &&
235 SpaceNode::closeChild(
const NodeAllocator& na,
236 bool hadFailures,
bool hadSolutions) {
240 bool allClosed =
true;
249 setHasOpenChildren(
false);
262 setHasSolvedChildren(
true);
264 while (p != NULL && !p->hasSolvedChildren()) {
265 p->setHasSolvedChildren(
true);
266 p = p->getParent(na);
271 while (p != NULL && !p->hasFailedChildren()) {
272 p->setHasFailedChildren(
true);
273 p = p->getParent(na);
281 :
Node(-1, root==NULL),
282 copy(root), choice(NULL), nstatus(0) {
285 setHasSolvedChildren(
false);
286 setHasFailedChildren(
true);
289 setHasSolvedChildren(
false);
290 setHasFailedChildren(
false);
309 QVector<QString> labels;
315 setHasOpenChildren(
false);
316 setHasSolvedChildren(
false);
317 setHasFailedChildren(
true);
322 p->closeChild(na,
true,
false);
331 setHasOpenChildren(
false);
332 setHasSolvedChildren(
true);
333 setHasFailedChildren(
false);
335 if (curBest != NULL) {
340 p->closeChild(na,
false,
true);
348 setHasOpenChildren(
true);
349 if (dynamic_cast<const StopChoice*>(
choice)) {
356 for (
int i=0;
i<kids;
i++) {
357 std::ostringstream oss;
359 labels.push_back(QString(oss.str().c_str()));
364 static_cast<VisualNode*
>(
this)->changedStatus(na);
376 int noOfOpenChildren = 0;
379 return noOfOpenChildren;
Node representing stop point.
bool marked(void *p)
Check whether p is marked.
int solutions
Number of solutions.
virtual Space * copy(bool share)=0
Copying member function.
Space must be branched (at least one brancher left)
SpaceNode * s
The currently best node found, or NULL.
Static reference to the currently best space.
Node representing a branch.
Branch(int a, const Choice *c, SpaceNode *best=NULL)
Constructor.
int alternative
Alternative number.
BestNode(SpaceNode *s0)
Constructor.
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
int choices
Number of choice nodes.
Node representing failure.
Base class for nodes of the search tree.
unsigned int getNumberOfChildren(void) const
Return the number of children.
unsigned int alternatives(void) const
Return number of alternatives.
void * mark(void *p)
Return marked pointer for p.
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
void setStatus(NodeStatus s)
Set status to s.
Node that has not been explored yet.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
void setDistance(unsigned int d)
Set distance from copy.
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
Gecode::FloatVal c(-8, 8)
int getParent(void) const
Return the parent.
NodeStatus getStatus(void) const
Return current status of the node.
int p
Number of positive literals for node type.
bool isRoot(void) const
Check if this node is the root of a tree.
Gecode::IntArgs i(4, 1, 2, 3, 4)
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Node representing a solution.
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
virtual void constrain(const Space &best)
Constrain function for best solution search.
int undetermined
Number of open, undetermined nodes.
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
unsigned int getDistance(void) const
Return distance from copy.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
T * dfs(T *s, const Search::Options &o)
Invoke depth-first search engine for subclass T of space s with options o.
void setBest(int i, int b)
Set index of best node before i to b.
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
Choice for performing commit
Representation of a branch in the search tree.
int getIndex(const NodeAllocator &na) const
Return index of this node.
Node class that supports visual layout
void dispose(void)
Free allocated memory.
SpaceNode * ownBest
The best space known when the branch was created.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
T * best(int i) const
Return index of best node before i.
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
A node of a search tree of Gecode spaces.
Space * copy
A copy used for recomputation, or NULL.
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
int getChild(int n) const
Return index of child no n.
bool isUndetermined(void) const
Return whether this node is undetermined.
bool isOpen(void)
Return whether this node still has open children.
const Choice * choice(void)
Create new choice for current brancher.
SpaceNode(int p)
Construct node with parent p.
int failures
Number of failures.
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Statistics about the search tree
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
Space is solved (no brancher left)