Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
37#include <gecode/search.hh>
38#include <stack>
39
40#include <QString>
41#include <QVector>
42
43namespace 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
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) {
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);
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;
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)) {
347 } else {
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::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
struct Gecode::@603::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.
void dispose(void)
Free allocated memory.
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
int getNumberOfChildNodes(NodeAllocator &na, BestNode *curBest, Statistics &stats, int c_d, int a_d)
Compute and return the number of children.
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
bool isOpen(void)
Return whether this node still has open children.
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).
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.
int getNoOfOpenChildren(const NodeAllocator &na)
Return number of open children.
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
Node class that supports visual layout
Computation spaces.
Definition core.hpp:1742
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
virtual Space * copy(void)=0
Copying member function.
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
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 toplevel namespace
T * dfs(T *s, const Search::Options &o=Search::Options::def)
Invoke depth-first search engine for subclass T of space s with options o.
Definition dfs.hpp:73