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