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);
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.
unsigned int alternatives(void) const
Return number of alternatives.
bool marked(void *p)
Check whether p is marked.
int solutions
Number of solutions.
NodeStatus getStatus(void) const
Return current status of the node.
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.
int choices
Number of choice nodes.
Node representing failure.
Base class for nodes of the search tree.
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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)
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.
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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.
int getParent(void) const
Return the parent.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
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)