Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
visualnode.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
35
38
39#include <utility>
40
41namespace Gecode { namespace Gist {
42
45
48 public:
52 (*Shape::leaf)[0] = Extent(Layout::extent);
53 Shape::leaf->computeBoundingBox();
54
56 (*Shape::hidden)[0] = Extent(Layout::extent);
57 (*Shape::hidden)[1] = Extent(Layout::extent);
58 Shape::hidden->computeBoundingBox();
59 }
64 };
65
68
70 : SpaceNode(p)
71 , offset(0)
72 {
73 shape = NULL;
74 setDirty(true);
76 setHidden(false);
77 setMarked(false);
78 setOnPath(false);
79 setBookmarked(false);
80 }
81
83 : SpaceNode(root)
84 , offset(0)
85 {
86 shape = NULL;
87 setDirty(true);
89 setHidden(false);
90 setMarked(false);
91 setOnPath(false);
92 setBookmarked(false);
93 }
94
95 void
100
101 void
103 VisualNode* cur = this;
104 while (!cur->isDirty()) {
105 cur->setDirty(true);
106 if (! cur->isRoot()) {
107 cur = cur->getParent(na);
108 }
109 }
110 }
111
112 void
114 LayoutCursor l(this,na);
116 // int nodesLayouted = 1;
117 // clock_t t0 = clock();
118 // while (p.next()) {}
119 // while (p.next()) { nodesLayouted++; }
120 // double t = (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC) * 1000.0;
121 // double nps = static_cast<double>(nodesLayouted) /
122 // (static_cast<double>(clock()-t0) / CLOCKS_PER_SEC);
123 // std::cout << "Layout done. " << nodesLayouted << " nodes in "
124 // << t << " ms. " << nps << " nodes/s." << std::endl;
125 }
126
128 VisualNode* cur = this;
129 while (cur) {
130 cur->setOnPath(true);
131 cur = cur->getParent(na);
132 }
133 }
134
136 VisualNode* cur = this;
137 while (!cur->isRoot()) {
138 cur->setOnPath(false);
139 cur = cur->getParent(na);
140 }
141 }
142
143 int
145 for (int i=getNumberOfChildren(); i--;) {
146 if (getChild(na,i)->isOnPath())
147 return i;
148 }
149 return -1;
150 }
151
152 void
157
158 void
159 VisualNode::hideFailed(const NodeAllocator& na, bool onlyDirty) {
160 HideFailedCursor c(this,na,onlyDirty);
162 dirtyUp(na);
163 }
164
165 void
167 BestNode* curBest, int c_d, int a_d) {
168 bool clear = na.hasLabel(this);
169 BranchLabelCursor c(this,curBest,c_d,a_d,clear,na);
171 dirtyUp(na);
172 }
173
174 void
176 BestNode* curBest, int c_d, int a_d) {
177 if (na.hasLabel(this)) {
178 // clear labels on path to root
179 VisualNode* p = this;
180 while (p) {
181 na.clearLabel(p);
182 p = p->getParent(na);
183 }
184 } else {
185 // set labels on path to root
186 std::vector<std::pair<VisualNode*,int> > path;
187 VisualNode* p = this;
188 while (p) {
189 path.push_back(std::pair<VisualNode*,int>(p,p->getAlternative(na)));
190 p = p->getParent(na);
191 }
192 while (!path.empty()) {
193 std::pair<VisualNode*,int> cur = path.back(); path.pop_back();
194 if (p) {
195 std::string l =
196 cur.first->getBranchLabel(na,p,p->getChoice(),
197 curBest,c_d,a_d,cur.second);
198 na.setLabel(cur.first,QString(l.c_str()));
199 }
200 p = cur.first;
201 }
202 }
203 dirtyUp(na);
204 }
205
206 void
212
213 void
215 if (getStatus() == STOP)
217 else if (getStatus() == UNSTOP)
219 dirtyUp(na);
220 }
221
222 void
228
229 void
231
232 bool
235 if (x < box.left ||
236 x > box.right ||
237 depth >= getShape()->depth()) {
238 return false;
239 }
240 Extent theExtent;
241 if (getShape()->getExtentAtDepth(depth, theExtent)) {
242 return (theExtent.l <= x && x <= theExtent.r);
243 } else {
244 return false;
245 }
246 }
247
249 VisualNode::findNode(const NodeAllocator& na, int x, int y) {
250 VisualNode* cur = this;
251 int depth = y / Layout::dist_y;
252
253 while (depth > 0 && cur != NULL) {
254 if (cur->isHidden()) {
255 break;
256 }
257 VisualNode* oldCur = cur;
258 cur = NULL;
259 for (unsigned int i=0; i<oldCur->getNumberOfChildren(); i++) {
260 VisualNode* nextChild = oldCur->getChild(na,i);
261 int newX = x - nextChild->getOffset();
262 if (nextChild->containsCoordinateAtDepth(newX, depth - 1)) {
263 cur = nextChild;
264 x = newX;
265 break;
266 }
267 }
268 depth--;
269 y -= Layout::dist_y;
270 }
271
272 if(cur == this && !cur->containsCoordinateAtDepth(x, 0)) {
273 return NULL;
274 }
275 return cur;
276 }
277
278 std::string
280 return "";
281 }
282
283 std::string
285 VisualNode* p, const Choice* c,
286 BestNode* curBest, int c_d, int a_d, int alt) {
287 std::ostringstream oss;
288 p->acquireSpace(na,curBest,c_d,a_d);
289 p->getWorkingSpace()->print(*c,alt,oss);
290 return oss.str();
291 }
292
293
295 class Layouter {
296 public:
298 template<class S1, class S2>
299 static int getAlpha(const S1& shape1, int depth1,
300 const S2& shape2, int depth2);
302 template<class S1, class S2>
303 static void merge(Extent* result,
304 const S1& shape1, int depth1,
305 const S2& shape2, int depth2, int alpha);
306 };
307
308 template<class S1, class S2>
309 int
310 Layouter::getAlpha(const S1& shape1, int depth1,
311 const S2& shape2, int depth2) {
312 int alpha = Layout::minimalSeparation;
313 int extentR = 0;
314 int extentL = 0;
315 for (int i=0; i<depth1 && i<depth2; i++) {
316 extentR += shape1[i].r;
317 extentL += shape2[i].l;
318 alpha = std::max(alpha, extentR - extentL + Layout::minimalSeparation);
319 }
320 return alpha;
321 }
322
323 template<class S1, class S2>
324 void
326 const S1& shape1, int depth1,
327 const S2& shape2, int depth2, int alpha) {
328 if (depth1 == 0) {
329 for (int i=depth2; i--;)
330 result[i] = shape2[i];
331 } else if (depth2 == 0) {
332 for (int i=depth1; i--;)
333 result[i] = shape1[i];
334 } else {
335 // Extend the topmost right extent by alpha. This, in effect,
336 // moves the second shape to the right by alpha units.
337 int topmostL = shape1[0].l;
338 int topmostR = shape2[0].r;
339 int backoffTo1 =
340 shape1[0].r - alpha - shape2[0].r;
341 int backoffTo2 =
342 shape2[0].l + alpha - shape1[0].l;
343
344 result[0] = Extent(topmostL, topmostR+alpha);
345
346 // Now, since extents are given in relative units, in order to
347 // compute the extents of the merged shape, we can just collect the
348 // extents of shape1 and shape2, until one of the shapes ends. If
349 // this happens, we need to "back-off" to the axis of the deeper
350 // shape in order to properly determine the remaining extents.
351 int i=1;
352 for (; i<depth1 && i<depth2; i++) {
353 Extent currentExtent1 = shape1[i];
354 Extent currentExtent2 = shape2[i];
355 int newExtentL = currentExtent1.l;
356 int newExtentR = currentExtent2.r;
357 result[i] = Extent(newExtentL, newExtentR);
358 backoffTo1 += currentExtent1.r - currentExtent2.r;
359 backoffTo2 += currentExtent2.l - currentExtent1.l;
360 }
361
362 // If shape1 is deeper than shape2, back off to the axis of shape1,
363 // and process the remaining extents of shape1.
364 if (i<depth1) {
365 Extent currentExtent1 = shape1[i];
366 int newExtentL = currentExtent1.l;
367 int newExtentR = currentExtent1.r;
368 result[i] = Extent(newExtentL, newExtentR+backoffTo1);
369 ++i;
370 for (; i<depth1; i++) {
371 result[i] = shape1[i];
372 }
373 }
374
375 // Vice versa, if shape2 is deeper than shape1, back off to the
376 // axis of shape2, and process the remaining extents of shape2.
377 if (i<depth2) {
378 Extent currentExtent2 = shape2[i];
379 int newExtentL = currentExtent2.l;
380 int newExtentR = currentExtent2.r;
381 result[i] = Extent(newExtentL+backoffTo2, newExtentR);
382 ++i;
383 for (; i<depth2; i++) {
384 result[i] = shape2[i];
385 }
386 }
387 }
388 }
389
390 void
392 if (shape != s)
394 shape = s;
395 shape->computeBoundingBox();
396 }
397
398 void
400 int numberOfShapes = getNumberOfChildren();
401 Extent extent;
402 if (na.hasLabel(this)) {
403 int ll = na.getLabel(this).length();
404 ll *= 7;
405 VisualNode* p = getParent(na);
406 int alt = 0;
407 int n_alt = 1;
408 if (p) {
409 alt = getAlternative(na);
410 n_alt = p->getNumberOfChildren();
411 }
412 extent = Extent(Layout::extent);
413 if (alt==0 && n_alt > 1) {
414 extent.l = std::min(extent.l, -ll);
415 } else if (alt==n_alt-1 && n_alt > 1) {
416 extent.r = std::max(extent.r, ll);
417 } else {
418 extent.l = std::min(extent.l, -ll);
419 extent.r = std::max(extent.r, ll);
420 }
421 } else {
422 if (numberOfShapes==0) {
424 return;
425 } else {
426 extent = Extent(Layout::extent);
427 }
428 }
429
430 int maxDepth = 0;
431 for (int i = numberOfShapes; i--;)
432 maxDepth = std::max(maxDepth, getChild(na,i)->getShape()->depth());
433 Shape* mergedShape;
434 if (getShape() && getShape() != Shape::leaf &&
435 getShape()->depth() >= maxDepth+1) {
436 mergedShape = getShape();
437 mergedShape->setDepth(maxDepth+1);
438 } else {
439 mergedShape = Shape::allocate(maxDepth+1);
440 }
441 (*mergedShape)[0] = extent;
442 if (numberOfShapes < 1) {
443 setShape(mergedShape);
444 } else if (numberOfShapes == 1) {
445 getChild(na,0)->setOffset(0);
446 const Shape* childShape = getChild(na,0)->getShape();
447 for (int i=childShape->depth(); i--;)
448 (*mergedShape)[i+1] = (*childShape)[i];
449 (*mergedShape)[1].extend(- extent.l, - extent.r);
450 setShape(mergedShape);
451 } else {
452 // alpha stores the necessary distances between the
453 // axes of the shapes in the list: alpha[i].first gives the distance
454 // between shape[i] and shape[i-1], when shape[i-1] and shape[i]
455 // are merged left-to-right; alpha[i].second gives the distance between
456 // shape[i] and shape[i+1], when shape[i] and shape[i+1] are merged
457 // right-to-left.
458 Region r;
459 std::pair<int,int>* alpha =
460 r.alloc<std::pair<int,int> >(numberOfShapes);
461
462 // distance between the leftmost and the rightmost axis in the list
463 int width = 0;
464
465 Extent* currentShapeL = r.alloc<Extent>(maxDepth);
466 int ldepth = getChild(na,0)->getShape()->depth();
467 for (int i=ldepth; i--;)
468 currentShapeL[i] = (*getChild(na,0)->getShape())[i];
469
470 // After merging, we can pick the result of either merging left or right
471 // Here we chose the result of merging right
472 Shape* rShape = getChild(na,numberOfShapes-1)->getShape();
473 int rdepth = rShape->depth();
474 for (int i=rdepth; i--;)
475 (*mergedShape)[i+1] = (*rShape)[i];
476 Extent* currentShapeR = &(*mergedShape)[1];
477
478 for (int i = 1; i < numberOfShapes; i++) {
479 // Merge left-to-right. Note that due to the asymmetry of the
480 // merge operation, nextAlphaL is the distance between the
481 // *leftmost* axis in the shape list, and the axis of
482 // nextShapeL; what we are really interested in is the distance
483 // between the *previous* axis and the axis of nextShapeL.
484 // This explains the correction.
485
486 Shape* nextShapeL = getChild(na,i)->getShape();
487 int nextAlphaL =
488 Layouter::getAlpha<Extent*,Shape>(&currentShapeL[0], ldepth,
489 *nextShapeL, nextShapeL->depth());
490 Layouter::merge<Extent*,Shape>(&currentShapeL[0],
491 &currentShapeL[0], ldepth,
492 *nextShapeL, nextShapeL->depth(),
493 nextAlphaL);
494 ldepth = std::max(ldepth,nextShapeL->depth());
495 alpha[i].first = nextAlphaL - width;
496 width = nextAlphaL;
497
498 // Merge right-to-left. Here, a correction of nextAlphaR is
499 // not required.
500 Shape* nextShapeR = getChild(na,numberOfShapes-1-i)->getShape();
501 int nextAlphaR =
502 Layouter::getAlpha<Shape,Extent*>(*nextShapeR, nextShapeR->depth(),
503 &currentShapeR[0], rdepth);
504 Layouter::merge<Shape,Extent*>(&currentShapeR[0],
505 *nextShapeR, nextShapeR->depth(),
506 &currentShapeR[0], rdepth,
507 nextAlphaR);
508 rdepth = std::max(rdepth,nextShapeR->depth());
509 alpha[numberOfShapes - i].second = nextAlphaR;
510 }
511
512 // The merged shape has to be adjusted to its topmost extent
513 (*mergedShape)[1].extend(- extent.l, - extent.r);
514
515 // After the loop, the merged shape has the same axis as the
516 // leftmost shape in the list. What we want is to move the axis
517 // such that it is the center of the axis of the leftmost shape in
518 // the list and the axis of the rightmost shape.
519 int halfWidth = false ? 0 : width / 2;
520 (*mergedShape)[1].move(- halfWidth);
521
522 // Finally, for the offset lists. Now that the axis of the merged
523 // shape is at the center of the two extreme axes, the first shape
524 // needs to be offset by -halfWidth units with respect to the new
525 // axis. As for the offsets for the other shapes, we take the
526 // median of the alphaL and alphaR values, as suggested in
527 // Kennedy's paper.
528 int offset = - halfWidth;
529 getChild(na,0)->setOffset(offset);
530 for (int i = 1; i < numberOfShapes; i++) {
531 offset += (alpha[i].first + alpha[i].second) / 2;
532 getChild(na,i)->setOffset(offset);
533 }
534 setShape(mergedShape);
535 }
536 }
537
538}}
539
540// STATISTICS: gist-any
Choice for performing commit
Definition core.hpp:1414
Static reference to the currently best space.
Definition spacenode.hh:80
int right
Right coordinate.
Definition visualnode.hh:57
int left
Left coordinate.
Definition visualnode.hh:55
A cursor that labels branches.
Extent representing shape of a tree at one depth level
Definition visualnode.hh:63
int l
Left extent.
Definition visualnode.hh:66
int r
Right extent.
Definition visualnode.hh:68
void extend(int deltaL, int deltaR)
Extend extent by deltaL and deltaR.
A cursor that marks failed subtrees as hidden.
Definition nodecursor.hh:86
A cursor that computes a tree layout for VisualNodes.
static const int dist_y
Definition visualnode.hh:46
static const int extent
Definition visualnode.hh:47
static const int minimalSeparation
Definition visualnode.hh:48
Helper functions for the layout algorithm.
static int getAlpha(const S1 &shape1, int depth1, const S2 &shape2, int depth2)
Compute distance needed between shape1 and shape2.
static void merge(Extent *result, const S1 &shape1, int depth1, const S2 &shape2, int depth2, int alpha)
Merge shape1 and shape2 into result with distance alpha.
QString getLabel(T *n) const
Get label of node n.
Definition node.hpp:144
bool hasLabel(T *n) const
Return whether node n has a label.
Definition node.hpp:126
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition node.hpp:132
void clearLabel(T *n)
Remove label of node n.
Definition node.hpp:138
NodeAllocatorBase< VisualNode > NodeAllocator
Definition node.hh:143
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
int getChild(int n) const
Return index of child no n.
Definition node.hpp:195
bool isRoot(void) const
Check if this node is the root of a tree.
Definition node.hpp:211
Run a cursor over a tree, processing nodes in post-order.
void run(void)
Execute visitor.
Run a cursor over a tree, processing nodes in pre-order.
void run(void)
Execute visitor.
Allocate shapes statically.
ShapeAllocator(void)
Constructor.
The shape of a subtree.
Definition visualnode.hh:83
const BoundingBox & getBoundingBox(void) const
Return bounding box.
static Shape * allocate(int d)
Construct shape of depth d.
int depth(void) const
Return depth of the shape.
static Shape * leaf
Static shape for leaf nodes.
static Shape * hidden
Static shape for hidden nodes.
static void deallocate(Shape *)
void setDepth(int d)
Set depth of the shape to d (must be smaller than original depth)
const Choice * getChoice(void)
Return choice of this node.
const Space * getWorkingSpace(void) const
Return working space (if present).
void setStatus(NodeStatus s)
Set status to s.
Definition spacenode.hpp:65
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 getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
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
A cursor that marks all nodes in the tree as not hidden.
A cursor that marks all nodes in the tree as not stopping.
Node class that supports visual layout
void unstopAll(const NodeAllocator &na)
Do not stop at any stop node in the subtree of this node.
int offset
Relative offset from the parent node.
int getPathAlternative(const NodeAllocator &na)
Return the alternative of the child that is on the path (-1 if none)
void unPathUp(const NodeAllocator &na)
Set all nodes from the node to the root not to be on the path.
void unhideAll(const NodeAllocator &na)
Unhide all nodes in the subtree of this node.
void setShape(Shape *s)
Set the shape of this node.
void setOnPath(bool onPath0)
Set whether node is on the path.
int getOffset(void)
Return offset off this node from its parent.
bool isHidden(void)
Return if node is hidden.
void toggleStop(const NodeAllocator &na)
Do not stop at this node.
void labelBranches(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels in subtree.
void setBookmarked(bool m)
Set bookmark of this node.
void computeShape(const NodeAllocator &na)
Compute the shape according to the shapes of the children.
Shape * shape
Shape of this node.
void dispose(void)
Free allocated memory.
void toggleHidden(const NodeAllocator &na)
Toggle whether this node is hidden.
void setHidden(bool h)
Set hidden state to h.
std::string getBranchLabel(NodeAllocator &na, VisualNode *p, const Choice *c, BestNode *curBest, int c_d, int a_d, int alt)
Return string that describes the branch.
void labelPath(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Create or clear branch labels on path to root.
void pathUp(const NodeAllocator &na)
Set all nodes from the node to the root to be on the path.
void dirtyUp(const NodeAllocator &na)
Mark all nodes up the path to the parent as dirty.
void changedStatus(const NodeAllocator &na)
Signal that the status has changed.
void layout(const NodeAllocator &na)
Compute layout for the subtree of this node.
void setDirty(bool d)
Mark node as dirty.
std::string toolTip(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Return string that is used as a tool tip.
VisualNode(int p)
Construct with parent p.
void hideFailed(const NodeAllocator &na, bool onlyDirty=false)
Hide all failed subtrees of this node.
VisualNode * findNode(const NodeAllocator &na, int x, int y)
Find a node in this subtree at coordinates x, y.
bool isDirty(void)
Return whether node is marked as dirty.
bool isOnPath(void)
Return whether node is on the path.
bool containsCoordinateAtDepth(int x, int depth)
Check if the x at depth depth lies in this subtree.
void setMarked(bool m)
Set mark of this node.
void setChildrenLayoutDone(bool d)
Mark node whether the layout of the node's children has been completed.
Shape * getShape(void)
Return the shape of this node.
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition core.cpp:656
The Gecode Interactive Search Tool.
ShapeAllocator shapeAllocator
Allocate shapes statically.
@ UNSTOP
Node representing ignored stop point.
Definition spacenode.hh:50
@ STOP
Node representing stop point.
Definition spacenode.hh:49
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
Post propagator for SetVar x
Definition set.hh:773