Generated on Tue Mar 5 2013 22:37:14 for Gecode by doxygen 1.8.3.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: 2010-08-11 23:13:48 +1000 (Wed, 11 Aug 2010) $ by $Author: tack $
11  * $Revision: 11343 $
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 namespace Gecode { namespace Gist {
45 
47  class Branch {
48  public:
53  const Choice* choice;
54 
56  Branch(int a, const Choice* c, SpaceNode* best = NULL)
57  : alternative(a), ownBest(best) {
58  choice = c;
59  }
60  };
61 
62  BestNode::BestNode(SpaceNode* s0) : s(s0) {}
63 
64  int
65  SpaceNode::recompute(NodeAllocator& na,
66  BestNode* curBest, int c_d, int a_d) {
67  int rdist = 0;
68 
69  if (copy == NULL) {
70  SpaceNode* curNode = this;
71  SpaceNode* lastFixpoint = NULL;
72 
73  lastFixpoint = curNode;
74 
75  std::stack<Branch> stck;
76 
77  int idx = getIndex(na);
78  while (curNode->copy == NULL) {
79  SpaceNode* parent = curNode->getParent(na);
80  int parentIdx = curNode->getParent();
81  int alternative = curNode->getAlternative(na);
82 
83  SpaceNode* ownBest = na.best(idx);
84  Branch b(alternative, parent->choice,
85  curBest == NULL ? NULL : ownBest);
86  stck.push(b);
87 
88  curNode = parent;
89  idx = parentIdx;
90  rdist++;
91  }
92  Space* curSpace = curNode->copy->clone();
93  curNode->setDistance(0);
94 
95  SpaceNode* lastBest = NULL;
96  SpaceNode* middleNode = curNode;
97  int curDist = 0;
98 
99  while (!stck.empty()) {
100  if (a_d >= 0 &&
101  curDist > a_d &&
102  curDist == rdist / 2) {
103  if (curSpace->status() == SS_FAILED) {
104  copy = static_cast<Space*>(Support::mark(curSpace));
105  return rdist;
106  } else {
107  middleNode->copy = curSpace->clone();
108  }
109  }
110  Branch b = stck.top(); stck.pop();
111 
112  if(middleNode == lastFixpoint) {
113  curSpace->status();
114  }
115 
116  curSpace->commit(*b.choice, b.alternative);
117 
118  if (b.ownBest != NULL && b.ownBest != lastBest) {
119  b.ownBest->acquireSpace(na,curBest, c_d, a_d);
120  Space* ownBestSpace =
121  static_cast<Space*>(Support::funmark(b.ownBest->copy));
122  if (ownBestSpace->status() != SS_SOLVED) {
123  // in the presence of weakly monotonic propagators, we may have to
124  // use search to find the solution here
125  ownBestSpace = Gecode::dfs(ownBestSpace);
126  if (Support::marked(b.ownBest->copy)) {
127  delete static_cast<Space*>(Support::unmark(b.ownBest->copy));
128  b.ownBest->copy =
129  static_cast<Space*>(Support::mark(ownBestSpace));
130  } else {
131  delete b.ownBest->copy;
132  b.ownBest->copy = ownBestSpace;
133  }
134  }
135  curSpace->constrain(*ownBestSpace);
136  lastBest = b.ownBest;
137  }
138  curDist++;
139  middleNode = middleNode->getChild(na,b.alternative);
140  middleNode->setDistance(curDist);
141  }
142  copy = static_cast<Space*>(Support::mark(curSpace));
143 
144  }
145  return rdist;
146  }
147 
148  void
150  BestNode* curBest, int c_d, int a_d) {
151  SpaceNode* p = getParent(na);
152  int parentIdx = getParent();
153  int idx = getIndex(na);
154 
155  if (getStatus() == UNDETERMINED && curBest != NULL &&
156  na.best(idx) == NULL &&
157  p != NULL && curBest->s != na.best(parentIdx)) {
158  na.setBest(idx, curBest->s->getIndex(na));
159  }
160  SpaceNode* ownBest = na.best(idx);
161 
162  if (copy == NULL && p != NULL && p->copy != NULL &&
163  Support::marked(p->copy)) {
164  // If parent has a working space, steal it
165  copy = p->copy;
166  p->copy = NULL;
167  if (p->choice != NULL)
168  static_cast<Space*>(Support::unmark(copy))->
169  commit(*p->choice, getAlternative(na));
170 
171  if (ownBest != NULL) {
172  ownBest->acquireSpace(na,curBest, c_d, a_d);
173  Space* ownBestSpace =
174  static_cast<Space*>(Support::funmark(ownBest->copy));
175  if (ownBestSpace->status() != SS_SOLVED) {
176  // in the presence of weakly monotonic propagators, we may have to
177  // use search to find the solution here
178 
179  ownBestSpace = Gecode::dfs(ownBestSpace);
180  if (Support::marked(ownBest->copy)) {
181  delete static_cast<Space*>(Support::unmark(ownBest->copy));
182  ownBest->copy =
183  static_cast<Space*>(Support::mark(ownBestSpace));
184  } else {
185  delete ownBest->copy;
186  ownBest->copy = ownBestSpace;
187  }
188  }
189  static_cast<Space*>(Support::unmark(copy))->constrain(*ownBestSpace);
190  }
191  int d = p->getDistance()+1;
192  if (d > c_d && c_d >= 0 &&
193  static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) {
194  copy = static_cast<Space*>(Support::unmark(copy));
195  d = 0;
196  }
197  setDistance(d);
198  }
199 
200  if (copy == NULL) {
201  if (recompute(na, curBest, c_d, a_d) > c_d && c_d >= 0 &&
202  static_cast<Space*>(Support::unmark(copy))->status() == SS_BRANCH) {
203  copy = static_cast<Space*>(Support::unmark(copy));
204  setDistance(0);
205  }
206  }
207 
208  // always return a fixpoint
209  static_cast<Space*>(Support::funmark(copy))->status();
210  if (Support::marked(copy) && p != NULL && isOpen() &&
211  p->copy != NULL && p->getNoOfOpenChildren(na) == 1 &&
212  !p->isRoot()) {
213  // last alternative optimization
214 
215  // If p->copy was a working space, we would have stolen it by now
216  assert(!Support::marked(p->copy));
217 
218  copy = static_cast<Space*>(Support::unmark(copy));
219  delete p->copy;
220  p->copy = NULL;
221  setDistance(0);
222  p->setDistance(p->getParent(na)->getDistance()+1);
223  }
224  }
225 
226  void
227  SpaceNode::closeChild(const NodeAllocator& na,
228  bool hadFailures, bool hadSolutions) {
229  setHasFailedChildren(hasFailedChildren() || hadFailures);
230  setHasSolvedChildren(hasSolvedChildren() || hadSolutions);
231 
232  bool allClosed = true;
233  for (int i=getNumberOfChildren(); i--;) {
234  if (getChild(na,i)->isOpen()) {
235  allClosed = false;
236  break;
237  }
238  }
239 
240  if (allClosed) {
241  setHasOpenChildren(false);
242  for (unsigned int i=0; i<getNumberOfChildren(); i++)
243  setHasSolvedChildren(hasSolvedChildren() ||
244  getChild(na,i)->hasSolvedChildren());
245  SpaceNode* p = getParent(na);
246  if (p != NULL) {
247  delete copy;
248  copy = NULL;
249  p->closeChild(na, hasFailedChildren(), hasSolvedChildren());
250  }
251  } else {
252 
253  if (hadSolutions) {
254  setHasSolvedChildren(true);
255  SpaceNode* p = getParent(na);
256  while (p != NULL && !p->hasSolvedChildren()) {
257  p->setHasSolvedChildren(true);
258  p = p->getParent(na);
259  }
260  }
261  if (hadFailures) {
262  SpaceNode* p = getParent(na);
263  while (p != NULL && !p->hasFailedChildren()) {
264  p->setHasFailedChildren(true);
265  p = p->getParent(na);
266  }
267  }
268  }
269 
270  }
271 
273  : Node(-1, root==NULL),
274  copy(root), choice(NULL), nstatus(0) {
275  if (root == NULL) {
276  setStatus(FAILED);
277  setHasSolvedChildren(false);
278  setHasFailedChildren(true);
279  } else {
281  setHasSolvedChildren(false);
282  setHasFailedChildren(false);
283  }
284  }
285 
286  void
288  delete choice;
289  delete static_cast<Space*>(Support::funmark(copy));
290  }
291 
292 
293  int
295  BestNode* curBest, Statistics& stats,
296  int c_d, int a_d) {
297  int kids = 0;
298  if (isUndetermined()) {
299  stats.undetermined--;
300  acquireSpace(na, curBest, c_d, a_d);
301  switch (static_cast<Space*>(Support::funmark(copy))->status(stats)) {
302  case SS_FAILED:
303  {
304  purge(na);
305  kids = 0;
306  setHasOpenChildren(false);
307  setHasSolvedChildren(false);
308  setHasFailedChildren(true);
309  setStatus(FAILED);
310  stats.failures++;
311  SpaceNode* p = getParent(na);
312  if (p != NULL)
313  p->closeChild(na, true, false);
314  }
315  break;
316  case SS_SOLVED:
317  {
318  // Deletes all pending branchers
319  (void) static_cast<Space*>(Support::funmark(copy))->choice();
320  kids = 0;
321  setStatus(SOLVED);
322  setHasOpenChildren(false);
323  setHasSolvedChildren(true);
324  setHasFailedChildren(false);
325  stats.solutions++;
326  if (curBest != NULL) {
327  curBest->s = this;
328  }
329  SpaceNode* p = getParent(na);
330  if (p != NULL)
331  p->closeChild(na, false, true);
332  }
333  break;
334  case SS_BRANCH:
335  {
336  choice = static_cast<Space*>(Support::funmark(copy))->choice();
337  kids = choice->alternatives();
338  setHasOpenChildren(true);
339  if (dynamic_cast<const StopChoice*>(choice)) {
340  setStatus(STOP);
341  } else {
342  setStatus(BRANCH);
343  stats.choices++;
344  }
345  stats.undetermined += kids;
346  }
347  break;
348  }
349  static_cast<VisualNode*>(this)->changedStatus(na);
350  setNumberOfChildren(kids, na);
351  } else {
352  kids = getNumberOfChildren();
353  }
354  return kids;
355  }
356 
357  int
359  if (!hasOpenChildren())
360  return 0;
361  int noOfOpenChildren = 0;
362  for (int i=getNumberOfChildren(); i--;)
363  noOfOpenChildren += (getChild(na,i)->isOpen());
364  return noOfOpenChildren;
365  }
366 
367 }}
368 
369 // STATISTICS: gist-any