this repo has no description
dekker.one
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>
35#include <gecode/gist/visualnode.hh>
36#include <gecode/gist/stopbrancher.hh>
37#include <gecode/search.hh>
38#include <stack>
39
40#include <QString>
41#include <QVector>
42
43namespace Gecode { namespace Gist {
44
45 /// \brief Representation of a branch in the search tree
46 class Branch {
47 public:
48 /// Alternative number
49 int alternative;
50 /// The best space known when the branch was created
51 SpaceNode* ownBest;
52 const Choice* choice;
53
54 /// Constructor
55 Branch(int a, const Choice* c, SpaceNode* best = nullptr)
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 == nullptr) {
69 SpaceNode* curNode = this;
70 SpaceNode* lastFixpoint = nullptr;
71
72 lastFixpoint = curNode;
73
74 std::stack<Branch> stck;
75
76 int idx = getIndex(na);
77 while (curNode->copy == nullptr) {
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 == nullptr ? nullptr : 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 = nullptr;
96 a_d = -1;
97 } else {
98 curSpace = curNode->copy->clone();
99 curNode->setDistance(0);
100 }
101
102 SpaceNode* lastBest = nullptr;
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 != nullptr && 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
156 SpaceNode::acquireSpace(NodeAllocator& na,
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 != nullptr &&
163 na.best(idx) == nullptr &&
164 p != nullptr && curBest->s != na.best(parentIdx)) {
165 na.setBest(idx, curBest->s->getIndex(na));
166 }
167 SpaceNode* ownBest = na.best(idx);
168
169 if (copy == nullptr && p != nullptr && p->copy != nullptr &&
170 Support::marked(p->copy)) {
171 // If parent has a working space, steal it
172 copy = p->copy;
173 p->copy = nullptr;
174 if (p->choice != nullptr)
175 static_cast<Space*>(Support::unmark(copy))->
176 commit(*p->choice, getAlternative(na));
177
178 if (ownBest != nullptr) {
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 == nullptr) {
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 != nullptr && isOpen() &&
218 p->copy != nullptr && 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 = nullptr;
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 != nullptr) {
251 delete static_cast<Space*>(Support::funmark(copy));
252 copy = nullptr;
253 p->closeChild(na, hasFailedChildren(), hasSolvedChildren());
254 }
255 } else {
256
257 if (hadSolutions) {
258 setHasSolvedChildren(true);
259 SpaceNode* p = getParent(na);
260 while (p != nullptr && !p->hasSolvedChildren()) {
261 p->setHasSolvedChildren(true);
262 p = p->getParent(na);
263 }
264 }
265 if (hadFailures) {
266 SpaceNode* p = getParent(na);
267 while (p != nullptr && !p->hasFailedChildren()) {
268 p->setHasFailedChildren(true);
269 p = p->getParent(na);
270 }
271 }
272 }
273
274 }
275
276 SpaceNode::SpaceNode(Space* root)
277 : Node(-1, root==nullptr),
278 copy(root), choice(nullptr), nstatus(0) {
279 if (root == nullptr) {
280 setStatus(FAILED);
281 setHasSolvedChildren(false);
282 setHasFailedChildren(true);
283 } else {
284 setStatus(UNDETERMINED);
285 setHasSolvedChildren(false);
286 setHasFailedChildren(false);
287 }
288 }
289
290 void
291 SpaceNode::dispose(void) {
292 delete choice;
293 delete static_cast<Space*>(Support::funmark(copy));
294 }
295
296
297 int
298 SpaceNode::getNumberOfChildNodes(NodeAllocator& na,
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 != nullptr)
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 != nullptr) {
332 curBest->s = this;
333 }
334 SpaceNode* p = getParent(na);
335 if (p != nullptr)
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
369 SpaceNode::getNoOfOpenChildren(const NodeAllocator& na) {
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