Generated on Tue Oct 22 2013 00:49:02 for Gecode by doxygen 1.8.4
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