Go to the documentation of this file.
47 namespace Gecode {
namespace Gist {
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);
167 na.
best(idx) == NULL &&
168 p != NULL && curBest->
s != na.
best(parentIdx)) {
173 if (
copy == NULL &&
p != NULL &&
p->copy != NULL &&
178 if (
p->choice != NULL)
182 if (ownBest != NULL) {
184 Space* ownBestSpace =
196 delete ownBest->
copy;
197 ownBest->
copy = ownBestSpace;
202 int d =
p->getDistance()+1;
212 if (recompute(na, curBest,
c_d,
a_d) >
c_d &&
c_d >= 0 &&
222 p->copy != NULL &&
p->getNoOfOpenChildren(na) == 1 &&
230 p->setDistance(
p->getParent(na)->getDistance()+1);
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);
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;
@ 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
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
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.
Gecode::IntArgs i(4, 1, 2, 3, 4)
@ 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.
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
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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.
@ BRANCH
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.
virtual Space * copy(bool share)=0
Copying member function.
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.
@ 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.