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) {
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);
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);
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;
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Node that has not been explored yet.
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
Space is solved (no brancher left)
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
Node representing stop point.
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
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.
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.
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.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
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.
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.
Node representing a branch.
SpaceNode * ownBest
The best space known when the branch was created.
int getParent(void) const
Return the parent.
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.
Node representing failure.
Gecode::IntArgs i({1, 2, 3, 4})
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.
Node representing a solution.
int alternative
Alternative number.