Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
spacenode.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Copyright:
7  * Guido Tack, 2006
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include <gecode/gist/spacenode.hh>
37 #include <gecode/search.hh>
38 #include <stack>
39 
40 #include <QString>
41 #include <QVector>
42 
43 namespace Gecode { namespace Gist {
44 
46  class Branch {
47  public:
52  const Choice* choice;
53 
55  Branch(int a, const Choice* c, SpaceNode* best = NULL)
56  : alternative(a), ownBest(best) {
57  choice = c;
58  }
59  };
60 
61  BestNode::BestNode(SpaceNode* s0) : s(s0) {}
62 
63  int
64  SpaceNode::recompute(NodeAllocator& na,
65  BestNode* curBest, int c_d, int a_d) {
66  int rdist = 0;
67 
68  if (copy == NULL) {
69  SpaceNode* curNode = this;
70  SpaceNode* lastFixpoint = NULL;
71 
72  lastFixpoint = curNode;
73 
74  std::stack<Branch> stck;
75 
76  int idx = getIndex(na);
77  while (curNode->copy == NULL) {
78  SpaceNode* parent = curNode->getParent(na);
79  int parentIdx = curNode->getParent();
80  int alternative = curNode->getAlternative(na);
81 
82  SpaceNode* ownBest = na.best(idx);
83  Branch b(alternative, parent->choice,
84  curBest == NULL ? NULL : ownBest);
85  stck.push(b);
86 
87  curNode = parent;
88  idx = parentIdx;
89  rdist++;
90  }
91 
92  Space* curSpace;
93  if (Support::marked(curNode->copy)) {
94  curSpace = static_cast<Space*>(Support::unmark(curNode->copy));
95  curNode->copy = NULL;
96  a_d = -1;
97  } else {
98  curSpace = curNode->copy->clone();
99  curNode->setDistance(0);
100  }
101 
102  SpaceNode* lastBest = NULL;
103  SpaceNode* middleNode = curNode;
104  int curDist = 0;
105 
106  while (!stck.empty()) {
107  if (a_d >= 0 &&
108  curDist > a_d &&
109  curDist == rdist / 2) {
110  if (curSpace->status() == SS_FAILED) {
111  copy = static_cast<Space*>(Support::mark(curSpace));
112  return rdist;
113  } else {
114  middleNode->copy = curSpace->clone();
115  }
116  }
117  Branch b = stck.top(); stck.pop();
118 
119  if(middleNode == lastFixpoint) {
120  curSpace->status();
121  }
122 
123  curSpace->commit(*b.choice, b.alternative);
124 
125  if (b.ownBest != NULL && b.ownBest != lastBest) {
126  b.ownBest->acquireSpace(na,curBest, c_d, a_d);
127  Space* ownBestSpace =
128  static_cast<Space*>(Support::funmark(b.ownBest->copy));
129  if (ownBestSpace->status() != SS_SOLVED) {
130  // in the presence of weakly monotonic propagators, we may have to
131  // use search to find the solution here
132  ownBestSpace = Gecode::dfs(ownBestSpace);
133  if (Support::marked(b.ownBest->copy)) {
134  delete static_cast<Space*>(Support::unmark(b.ownBest->copy));
135  b.ownBest->copy =
136  static_cast<Space*>(Support::mark(ownBestSpace));
137  } else {
138  delete b.ownBest->copy;
139  b.ownBest->copy = ownBestSpace;
140  }
141  }
142  curSpace->constrain(*ownBestSpace);
143  lastBest = b.ownBest;
144  }
145  curDist++;
146  middleNode = middleNode->getChild(na,b.alternative);
147  middleNode->setDistance(curDist);
148  }
149  copy = static_cast<Space*>(Support::mark(curSpace));
150 
151  }
152  return rdist;
153  }
154 
155  void
157  BestNode* curBest, int c_d, int a_d) {
158  SpaceNode* p = getParent(na);
159  int parentIdx = getParent();
160  int idx = getIndex(na);
161 
162  if (getStatus() == UNDETERMINED && curBest != NULL &&
163  na.best(idx) == NULL &&
164  p != NULL && curBest->s != na.best(parentIdx)) {
165  na.setBest(idx, curBest->s->getIndex(na));
166  }
167  SpaceNode* ownBest = na.best(idx);
168 
169  if (copy == NULL && p != NULL && p->copy != NULL &&
170  Support::marked(p->copy)) {
171  // If parent has a working space, steal it
172  copy = p->copy;
173  p->copy = NULL;
174  if (p->choice != NULL)
175  static_cast<Space*>(Support::unmark(copy))->
176  commit(*p->choice, getAlternative(na));
177 
178  if (ownBest != NULL) {
179  ownBest->acquireSpace(na,curBest, c_d, a_d);
180  Space* ownBestSpace =
181  static_cast<Space*>(Support::funmark(ownBest->copy));
182  if (ownBestSpace->status() != SS_SOLVED) {
183  // in the presence of weakly monotonic propagators, we may have to
184  // use search to find the solution here
185 
186  ownBestSpace = Gecode::dfs(ownBestSpace);
187  if (Support::marked(ownBest->copy)) {
188  delete static_cast<Space*>(Support::unmark(ownBest->copy));
189  ownBest->copy =
190  static_cast<Space*>(Support::mark(ownBestSpace));
191  } else {
192  delete ownBest->copy;
193  ownBest->copy = ownBestSpace;
194  }
195  }
196  static_cast<Space*>(Support::unmark(copy))->constrain(*ownBestSpace);
197  }
198  int d = p->getDistance()+1;
199  if (d > c_d && c_d >= 0 &&
200  static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) {
201  copy = static_cast<Space*>(Support::unmark(copy));
202  d = 0;
203  }
204  setDistance(d);
205  }
206 
207  if (copy == NULL) {
208  if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 &&
209  static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) {
210  copy = static_cast<Space*>(Support::unmark(copy));
211  setDistance(0);
212  }
213  }
214 
215  // always return a fixpoint
216  static_cast<Space*>(Support::funmark(copy))->status();
217  if (Support::marked(copy) && p != NULL && isOpen() &&
218  p->copy != NULL && p->getNoOfOpenChildren(na) == 1 &&
219  !p->isRoot()) {
220  // last alternative optimization
221 
222  copy = static_cast<Space*>(Support::unmark(copy));
223  delete static_cast<Space*>(Support::funmark(p->copy));
224  p->copy = NULL;
225  setDistance(0);
226  p->setDistance(p->getParent(na)->getDistance()+1);
227  }
228  }
229 
230  void
231  SpaceNode::closeChild(const NodeAllocator& na,
232  bool hadFailures, bool hadSolutions) {
233  setHasFailedChildren(hasFailedChildren() || hadFailures);
234  setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
235 
236  bool allClosed = true;
237  for (int i=getNumberOfChildren(); i--;) {
238  if (getChild(na,i)->isOpen()) {
239  allClosed = false;
240  break;
241  }
242  }
243 
244  if (allClosed) {
245  setHasOpenChildren(false);
246  for (unsigned int i=0; i<getNumberOfChildren(); i++)
247  setHasSolvedChildren(hasSolvedChildren() ||
248  getChild(na,i)->hasSolvedChildren());
249  SpaceNode* p = getParent(na);
250  if (p != NULL) {
251  delete static_cast<Space*>(Support::funmark(copy));
252  copy = NULL;
253  p->closeChild(na, hasFailedChildren(), hasSolvedChildren());
254  }
255  } else {
256 
257  if (hadSolutions) {
258  setHasSolvedChildren(true);
259  SpaceNode* p = getParent(na);
260  while (p != NULL && !p->hasSolvedChildren()) {
261  p->setHasSolvedChildren(true);
262  p = p->getParent(na);
263  }
264  }
265  if (hadFailures) {
266  SpaceNode* p = getParent(na);
267  while (p != NULL && !p->hasFailedChildren()) {
268  p->setHasFailedChildren(true);
269  p = p->getParent(na);
270  }
271  }
272  }
273 
274  }
275 
277  : Node(-1, root==NULL),
278  copy(root), choice(NULL), nstatus(0) {
279  if (root == NULL) {
280  setStatus(FAILED);
281  setHasSolvedChildren(false);
282  setHasFailedChildren(true);
283  } else {
285  setHasSolvedChildren(false);
286  setHasFailedChildren(false);
287  }
288  }
289 
290  void
292  delete choice;
293  delete static_cast<Space*>(Support::funmark(copy));
294  }
295 
296 
297  int
299  BestNode* curBest, Statistics& stats,
300  int c_d, int a_d) {
301  int kids = 0;
302  if (isUndetermined()) {
303  stats.undetermined--;
304  acquireSpace(na, curBest, c_d, a_d);
305  QVector<QString> labels;
306  switch (static_cast<Space*>(Support::funmark(copy))->status(stats)) {
307  case SS_FAILED:
308  {
309  purge(na);
310  kids = 0;
311  setHasOpenChildren(false);
312  setHasSolvedChildren(false);
313  setHasFailedChildren(true);
314  setStatus(FAILED);
315  stats.failures++;
316  SpaceNode* p = getParent(na);
317  if (p != NULL)
318  p->closeChild(na, true, false);
319  }
320  break;
321  case SS_SOLVED:
322  {
323  // Deletes all pending branchers
324  (void) static_cast<Space*>(Support::funmark(copy))->choice();
325  kids = 0;
326  setStatus(SOLVED);
327  setHasOpenChildren(false);
328  setHasSolvedChildren(true);
329  setHasFailedChildren(false);
330  stats.solutions++;
331  if (curBest != NULL) {
332  curBest->s = this;
333  }
334  SpaceNode* p = getParent(na);
335  if (p != NULL)
336  p->closeChild(na, false, true);
337  }
338  break;
339  case SS_BRANCH:
340  {
341  Space* s = static_cast<Space*>(Support::funmark(copy));
342  choice = s->choice();
343  kids = choice->alternatives();
344  setHasOpenChildren(true);
345  if (dynamic_cast<const StopChoice*>(choice)) {
346  setStatus(STOP);
347  } else {
348  setStatus(BRANCH);
349  stats.choices++;
350  }
351  stats.undetermined += kids;
352  for (int i=0; i<kids; i++) {
353  std::ostringstream oss;
354  s->print(*choice,i,oss);
355  labels.push_back(QString(oss.str().c_str()));
356  }
357  }
358  break;
359  }
360  static_cast<VisualNode*>(this)->changedStatus(na);
361  setNumberOfChildren(kids, na);
362  } else {
363  kids = getNumberOfChildren();
364  }
365  return kids;
366  }
367 
368  int
370  if (!hasOpenChildren())
371  return 0;
372  int noOfOpenChildren = 0;
373  for (int i=getNumberOfChildren(); i--;)
374  noOfOpenChildren += (getChild(na,i)->isOpen());
375  return noOfOpenChildren;
376  }
377 
378 }}
379 
380 // STATISTICS: gist-any
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1412
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3770
Static reference to the currently best space.
Definition: spacenode.hh:80
BestNode(SpaceNode *s0)
Constructor.
Definition: spacenode.cpp:61
SpaceNode * s
The currently best node found, or NULL.
Definition: spacenode.hh:83
Representation of a branch in the search tree.
Definition: spacenode.cpp:46
const Choice * choice
Definition: spacenode.cpp:52
SpaceNode * ownBest
The best space known when the branch was created.
Definition: spacenode.cpp:51
int alternative
Alternative number.
Definition: spacenode.cpp:49
Branch(int a, const Choice *c, SpaceNode *best=NULL)
Constructor.
Definition: spacenode.cpp:55
T * best(int i) const
Return index of best node before i.
Definition: node.hpp:97
void setBest(int i, int b)
Set index of best node before i to b.
Definition: node.hpp:106
Base class for nodes of the search tree.
Definition: node.hh:106
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
Definition: node.cpp:42
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition: node.hpp:214
int getParent(void) const
Return the parent.
Definition: node.hpp:182
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition: node.hpp:192
int getChild(int n) const
Return index of child no n.
Definition: node.hpp:195
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition: node.hpp:227
A node of a search tree of Gecode spaces.
Definition: spacenode.hh:89
Space * copy
A copy used for recomputation, or NULL.
Definition: spacenode.hh:96
const Choice * choice
Definition: spacenode.hh:98
void setStatus(NodeStatus s)
Set status to s.
Definition: spacenode.hpp:65
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
Definition: spacenode.hpp:144
void dispose(void)
Free allocated memory.
Definition: spacenode.cpp:291
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
Definition: spacenode.cpp:156
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
Definition: spacenode.cpp:298
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
Definition: spacenode.hpp:149
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
Definition: spacenode.hpp:169
bool isOpen(void)
Return whether this node still has open children.
Definition: spacenode.hpp:138
NodeStatus getStatus(void) const
Return current status of the node.
Definition: spacenode.hpp:71
SpaceNode(int p)
Construct node with parent p.
Definition: spacenode.hpp:89
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
Definition: spacenode.hpp:120
void setDistance(unsigned int d)
Set distance from copy.
Definition: spacenode.hpp:76
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
Definition: spacenode.hpp:154
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
Definition: spacenode.cpp:369
Statistics about the search tree
Definition: spacenode.hh:59
int choices
Number of choice nodes.
Definition: spacenode.hh:66
int failures
Number of failures.
Definition: spacenode.hh:64
int solutions
Number of solutions.
Definition: spacenode.hh:62
int undetermined
Number of open, undetermined nodes.
Definition: spacenode.hh:68
Choice for StopBrancher
Definition: stopbrancher.hh:40
Node class that supports visual layout
Definition: visualnode.hh:125
Computation spaces.
Definition: core.hpp:1742
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:203
virtual Space * copy(void)=0
Copying member function.
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:841
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition: core.cpp:655
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:537
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3232
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition: core.hpp:1683
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
@ UNDETERMINED
Node that has not been explored yet.
Definition: spacenode.hh:48
@ FAILED
Node representing failure.
Definition: spacenode.hh:46
@ STOP
Node representing stop point.
Definition: spacenode.hh:49
@ SOLVED
Node representing a solution.
Definition: spacenode.hh:45
@ BRANCH
Node representing a branch.
Definition: spacenode.hh:47
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)