43 namespace Gecode {
namespace Gist {
56 : alternative(a), ownBest(best) {
64 SpaceNode::recompute(NodeAllocator& na,
72 lastFixpoint = curNode;
74 std::stack<Branch> stck;
76 int idx = getIndex(na);
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) {
127 Space* ownBestSpace =
157 BestNode* curBest,
int c_d,
int a_d) {
159 int parentIdx = getParent();
160 int idx = getIndex(na);
163 na.
best(idx) == NULL &&
164 p != NULL && curBest->
s != na.
best(parentIdx)) {
169 if (copy == NULL && p != NULL && p->
copy != NULL &&
176 commit(*p->
choice, getAlternative(na));
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 &&
232 bool hadFailures,
bool hadSolutions) {
233 setHasFailedChildren(hasFailedChildren() || hadFailures);
234 setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
236 bool allClosed =
true;
237 for (
int i=getNumberOfChildren();
i--;) {
238 if (getChild(na,
i)->isOpen()) {
245 setHasOpenChildren(
false);
246 for (
unsigned int i=0;
i<getNumberOfChildren();
i++)
247 setHasSolvedChildren(hasSolvedChildren() ||
248 getChild(na,
i)->hasSolvedChildren());
253 p->closeChild(na, hasFailedChildren(), hasSolvedChildren());
258 setHasSolvedChildren(
true);
261 p->setHasSolvedChildren(
true);
268 p->setHasFailedChildren(
true);
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);
345 if (dynamic_cast<const StopChoice*>(
choice)) {
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;
Node representing stop point.
unsigned int alternatives(void) const
Return number of alternatives.
bool marked(void *p)
Check whether p is marked.
int solutions
Number of solutions.
Space must be branched (at least one brancher left)
bool isRoot(void) const
Check if this node is the root of a tree.
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.
int choices
Number of choice nodes.
unsigned int getDistance(void) const
Return distance from copy.
Node representing failure.
Base class for nodes of the search tree.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
unsigned int getNumberOfChildren(void) const
Return the number of children.
int getIndex(const NodeAllocator &na) const
Return index of this node.
T * best(int i) const
Return index of best node before i.
void setStatus(NodeStatus s)
Set status to s.
Node that has not been explored yet.
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)
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
int p
Number of positive literals for node type.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
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 * 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.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int getParent(void) const
Return the parent.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Representation of a branch in the search tree.
Node class that supports visual layout
void dispose(void)
Free allocated memory.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
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)
bool isUndetermined(void) const
Return whether this node is undetermined.
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.
int getChild(int n) const
Return index of child no n.
Gecode toplevel namespace
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.
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)