1 /**
2 * \brief A block is a group of variables that must be moved together to improve
3 * the goal function without violating already active constraints.
4 * The variables in a block are spanned by a tree of active constraints.
5 *
6 * Authors:
7 * Tim Dwyer <tgdwyer@gmail.com>
8 *
9 * Copyright (C) 2005 Authors
10 *
11 * Released under GNU LGPL. Read the file 'COPYING' for more information.
12 */
13 #include <cassert>
14 #include "pairingheap/PairingHeap.h"
15 #include "constraint.h"
16 #include "block.h"
17 #include "blocks.h"
18 #ifdef RECTANGLE_OVERLAP_LOGGING
19 #include <fstream>
20 using std::ios;
21 using std::ofstream;
22 using std::endl;
23 #endif
24 using std::vector;
26 namespace vpsc {
27 void Block::addVariable(Variable* const v) {
28 v->block=this;
29 vars->push_back(v);
30 weight+=v->weight;
31 wposn += v->weight * (v->desiredPosition - v->offset);
32 posn=wposn/weight;
33 }
34 Block::Block(Variable* const v) {
35 timeStamp=0;
36 posn=weight=wposn=0;
37 in=NULL;
38 out=NULL;
39 deleted=false;
40 vars=new vector<Variable*>;
41 if(v!=NULL) {
42 v->offset=0;
43 addVariable(v);
44 }
45 }
47 double Block::desiredWeightedPosition() {
48 double wp = 0;
49 for (Vit v=vars->begin();v!=vars->end();++v) {
50 wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
51 }
52 return wp;
53 }
54 Block::~Block(void)
55 {
56 delete vars;
57 delete in;
58 delete out;
59 }
60 void Block::setUpInConstraints() {
61 setUpConstraintHeap(in,true);
62 }
63 void Block::setUpOutConstraints() {
64 setUpConstraintHeap(out,false);
65 }
66 void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
67 delete h;
68 h = new PairingHeap<Constraint*>(&compareConstraints);
69 for (Vit i=vars->begin();i!=vars->end();++i) {
70 Variable *v=*i;
71 vector<Constraint*> *cs=in?&(v->in):&(v->out);
72 for (Cit j=cs->begin();j!=cs->end();++j) {
73 Constraint *c=*j;
74 c->timeStamp=blockTimeCtr;
75 if (c->left->block != this && in || c->right->block != this && !in) {
76 h->insert(c);
77 }
78 }
79 }
80 }
81 void Block::merge(Block* b, Constraint* c) {
82 #ifdef RECTANGLE_OVERLAP_LOGGING
83 ofstream f(LOGFILE,ios::app);
84 f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
85 #endif
86 double dist = c->right->offset - c->left->offset - c->gap;
87 Block *l=c->left->block;
88 Block *r=c->right->block;
89 if (vars->size() < b->vars->size()) {
90 r->merge(l,c,dist);
91 } else {
92 l->merge(r,c,-dist);
93 }
94 #ifdef RECTANGLE_OVERLAP_LOGGING
95 f<<" merged block="<<(b->deleted?*this:*b)<<endl;
96 #endif
97 }
98 /**
99 * Merges b into this block across c. Can be either a
100 * right merge or a left merge
101 * @param b block to merge into this
102 * @param c constraint being merged
103 * @param distance separation required to satisfy c
104 */
105 void Block::merge(Block *b, Constraint *c, double dist) {
106 #ifdef RECTANGLE_OVERLAP_LOGGING
107 ofstream f(LOGFILE,ios::app);
108 f<<" merging: "<<*b<<"dist="<<dist<<endl;
109 #endif
110 c->active=true;
111 wposn+=b->wposn-dist*b->weight;
112 weight+=b->weight;
113 posn=wposn/weight;
114 for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
115 Variable *v=*i;
116 v->block=this;
117 v->offset+=dist;
118 vars->push_back(v);
119 }
120 b->deleted=true;
121 }
123 void Block::mergeIn(Block *b) {
124 #ifdef RECTANGLE_OVERLAP_LOGGING
125 ofstream f(LOGFILE,ios::app);
126 f<<" merging constraint heaps... "<<endl;
127 #endif
128 // We check the top of the heaps to remove possible internal constraints
129 findMinInConstraint();
130 b->findMinInConstraint();
131 in->merge(b->in);
132 #ifdef RECTANGLE_OVERLAP_LOGGING
133 f<<" merged heap: "<<*in<<endl;
134 #endif
135 }
136 void Block::mergeOut(Block *b) {
137 findMinOutConstraint();
138 b->findMinOutConstraint();
139 out->merge(b->out);
140 }
141 Constraint *Block::findMinInConstraint() {
142 Constraint *v = NULL;
143 vector<Constraint*> outOfDate;
144 while (!in->isEmpty()) {
145 v = in->findMin();
146 Block *lb=v->left->block;
147 Block *rb=v->right->block;
148 // rb may not be this if called between merge and mergeIn
149 #ifdef RECTANGLE_OVERLAP_LOGGING
150 ofstream f(LOGFILE,ios::app);
151 f<<" checking constraint ... "<<*v;
152 f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
153 #endif
154 if(lb == rb) {
155 // constraint has been merged into the same block
156 #ifdef RECTANGLE_OVERLAP_LOGGING
157 if(v->slack()<0) {
158 f<<" violated internal constraint found! "<<*v<<endl;
159 f<<" lb="<<*lb<<endl;
160 f<<" rb="<<*rb<<endl;
161 }
162 #endif
163 in->deleteMin();
164 #ifdef RECTANGLE_OVERLAP_LOGGING
165 f<<" ... skipping internal constraint"<<endl;
166 #endif
167 } else if(v->timeStamp < lb->timeStamp) {
168 // block at other end of constraint has been moved since this
169 in->deleteMin();
170 outOfDate.push_back(v);
171 #ifdef RECTANGLE_OVERLAP_LOGGING
172 f<<" reinserting out of date (reinsert later)"<<endl;
173 #endif
174 } else {
175 break;
176 }
177 }
178 for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
179 v=*i;
180 v->timeStamp=blockTimeCtr;
181 in->insert(v);
182 }
183 if(in->isEmpty()) {
184 v=NULL;
185 } else {
186 v=in->findMin();
187 }
188 return v;
189 }
190 Constraint *Block::findMinOutConstraint() {
191 if(out->isEmpty()) return NULL;
192 Constraint *v = out->findMin();
193 while (v->left->block == v->right->block) {
194 out->deleteMin();
195 if(out->isEmpty()) return NULL;
196 v = out->findMin();
197 }
198 return v;
199 }
200 void Block::deleteMinInConstraint() {
201 in->deleteMin();
202 #ifdef RECTANGLE_OVERLAP_LOGGING
203 ofstream f(LOGFILE,ios::app);
204 f<<"deleteMinInConstraint... "<<endl;
205 f<<" result: "<<*in<<endl;
206 #endif
207 }
208 void Block::deleteMinOutConstraint() {
209 out->deleteMin();
210 }
211 inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) {
212 return c->left->block==this && c->active && last!=c->left;
213 }
214 inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
215 return c->right->block==this && c->active && last!=c->right;
216 }
218 // computes the derivative of v and the lagrange multipliers
219 // of v's out constraints (as the recursive sum of those below.
220 // Does not backtrack over u.
221 // also records the constraint with minimum lagrange multiplier
222 // in min_lm
223 double Block::compute_dfdv(Variable* const v, Variable* const u,
224 Constraint *&min_lm) {
225 double dfdv=v->weight*(v->position() - v->desiredPosition);
226 for(Cit it=v->out.begin();it!=v->out.end();++it) {
227 Constraint *c=*it;
228 if(canFollowRight(c,u)) {
229 dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
230 if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
231 }
232 }
233 for(Cit it=v->in.begin();it!=v->in.end();++it) {
234 Constraint *c=*it;
235 if(canFollowLeft(c,u)) {
236 dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
237 if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
238 }
239 }
240 return dfdv;
241 }
244 // computes dfdv for each variable and uses the sum of dfdv on either side of
245 // the constraint c to compute the lagrangian multiplier lm_c.
246 // The top level v and r are variables between which we want to find the
247 // constraint with the smallest lm.
248 // When we find r we pass NULL to subsequent recursive calls,
249 // thus r=NULL indicates constraints are not on the shortest path.
250 // Similarly, m is initially NULL and is only assigned a value if the next
251 // variable to be visited is r or if a possible min constraint is returned from
252 // a nested call (rather than NULL).
253 // Then, the search for the m with minimum lm occurs as we return from
254 // the recursion (checking only constraints traversed left-to-right
255 // in order to avoid creating any new violations).
256 // We also do not consider equality constraints as potential split points
257 Block::Pair Block::compute_dfdv_between(
258 Variable* r, Variable* const v, Variable* const u,
259 const Direction dir = NONE, bool changedDirection = false) {
260 double dfdv=v->weight*(v->position() - v->desiredPosition);
261 Constraint *m=NULL;
262 for(Cit it(v->in.begin());it!=v->in.end();++it) {
263 Constraint *c=*it;
264 if(canFollowLeft(c,u)) {
265 if(dir==RIGHT) {
266 changedDirection = true;
267 }
268 if(c->left==r) {
269 r=NULL;
270 if(!c->equality) m=c;
271 }
272 Pair p=compute_dfdv_between(r,c->left,v,
273 LEFT,changedDirection);
274 dfdv -= c->lm = -p.first;
275 if(r && p.second)
276 m = p.second;
277 }
278 }
279 for(Cit it(v->out.begin());it!=v->out.end();++it) {
280 Constraint *c=*it;
281 if(canFollowRight(c,u)) {
282 if(dir==LEFT) {
283 changedDirection = true;
284 }
285 if(c->right==r) {
286 r=NULL;
287 if(!c->equality) m=c;
288 }
289 Pair p=compute_dfdv_between(r,c->right,v,
290 RIGHT,changedDirection);
291 dfdv += c->lm = p.first;
292 if(r && p.second)
293 m = changedDirection && !c->equality && c->lm < p.second->lm
294 ? c
295 : p.second;
296 }
297 }
298 return Pair(dfdv,m);
299 }
301 // resets LMs for all active constraints to 0 by
302 // traversing active constraint tree starting from v,
303 // not back tracking over u
304 void Block::reset_active_lm(Variable* const v, Variable* const u) {
305 for(Cit it=v->out.begin();it!=v->out.end();++it) {
306 Constraint *c=*it;
307 if(canFollowRight(c,u)) {
308 c->lm=0;
309 reset_active_lm(c->right,v);
310 }
311 }
312 for(Cit it=v->in.begin();it!=v->in.end();++it) {
313 Constraint *c=*it;
314 if(canFollowLeft(c,u)) {
315 c->lm=0;
316 reset_active_lm(c->left,v);
317 }
318 }
319 }
320 /**
321 * finds the constraint with the minimum lagrange multiplier, that is, the constraint
322 * that most wants to split
323 */
324 Constraint *Block::findMinLM() {
325 Constraint *min_lm=NULL;
326 reset_active_lm(vars->front(),NULL);
327 compute_dfdv(vars->front(),NULL,min_lm);
328 return min_lm;
329 }
330 Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) {
331 Constraint *min_lm=NULL;
332 reset_active_lm(vars->front(),NULL);
333 min_lm=compute_dfdv_between(rv,lv,NULL).second;
334 return min_lm;
335 }
337 // populates block b by traversing the active constraint tree adding variables as they're
338 // visited. Starts from variable v and does not backtrack over variable u.
339 void Block::populateSplitBlock(Block *b, Variable* const v, Variable* const u) {
340 b->addVariable(v);
341 for (Cit c=v->in.begin();c!=v->in.end();++c) {
342 if (canFollowLeft(*c,u))
343 populateSplitBlock(b, (*c)->left, v);
344 }
345 for (Cit c=v->out.begin();c!=v->out.end();++c) {
346 if (canFollowRight(*c,u))
347 populateSplitBlock(b, (*c)->right, v);
348 }
349 }
350 // Search active constraint tree from u to see if there is a directed path to v.
351 // Returns true if path is found with all constraints in path having their visited flag
352 // set true.
353 bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) {
354 if(u==v) return true;
355 for (Cit c=u->out.begin();c!=u->out.end();++c) {
356 if(canFollowRight(*c,NULL)) {
357 if(isActiveDirectedPathBetween((*c)->right,v)) {
358 (*c)->visited=true;
359 return true;
360 }
361 (*c)->visited=false;
362 }
363 }
364 return false;
365 }
366 /**
367 * Block needs to be split because of a violated constraint between vl and vr.
368 * We need to search the active constraint tree between l and r and find the constraint
369 * with min lagrangrian multiplier and split at that point.
370 * Returns the split constraint
371 */
372 Constraint* Block::splitBetween(Variable* const vl, Variable* const vr,
373 Block* &lb, Block* &rb) {
374 #ifdef RECTANGLE_OVERLAP_LOGGING
375 ofstream f(LOGFILE,ios::app);
376 f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
377 #endif
378 Constraint *c=findMinLMBetween(vl, vr);
379 #ifdef RECTANGLE_OVERLAP_LOGGING
380 f<<" going to split on: "<<*c<<endl;
381 #endif
382 split(lb,rb,c);
383 deleted = true;
384 return c;
385 }
386 /**
387 * Creates two new blocks, l and r, and splits this block across constraint c,
388 * placing the left subtree of constraints (and associated variables) into l
389 * and the right into r.
390 */
391 void Block::split(Block* &l, Block* &r, Constraint* c) {
392 c->active=false;
393 l=new Block();
394 populateSplitBlock(l,c->left,c->right);
395 r=new Block();
396 populateSplitBlock(r,c->right,c->left);
397 }
399 /**
400 * Computes the cost (squared euclidean distance from desired positions) of the
401 * current positions for variables in this block
402 */
403 double Block::cost() {
404 double c = 0;
405 for (Vit v=vars->begin();v!=vars->end();++v) {
406 double diff = (*v)->position() - (*v)->desiredPosition;
407 c += (*v)->weight * diff * diff;
408 }
409 return c;
410 }
411 ostream& operator <<(ostream &os, const Block& b)
412 {
413 os<<"Block:";
414 for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
415 os<<" "<<**v;
416 }
417 if(b.deleted) {
418 os<<" Deleted!";
419 }
420 return os;
421 }
422 }