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 typedef vector<Constraint*>::iterator Cit;
28 void Block::addVariable(Variable *v) {
29 v->block=this;
30 vars->push_back(v);
31 weight+=v->weight;
32 wposn += v->weight * (v->desiredPosition - v->offset);
33 posn=wposn/weight;
34 }
35 Block::Block(Variable *v) {
36 timeStamp=0;
37 posn=weight=wposn=0;
38 in=NULL;
39 out=NULL;
40 deleted=false;
41 vars=new vector<Variable*>;
42 if(v!=NULL) {
43 v->offset=0;
44 addVariable(v);
45 }
46 }
48 double Block::desiredWeightedPosition() {
49 double wp = 0;
50 for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();++v) {
51 wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
52 }
53 return wp;
54 }
55 Block::~Block(void)
56 {
57 delete vars;
58 delete in;
59 delete out;
60 }
61 void Block::setUpInConstraints() {
62 setUpConstraintHeap(in,true);
63 }
64 void Block::setUpOutConstraints() {
65 setUpConstraintHeap(out,false);
66 }
67 void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
68 delete h;
69 h = new PairingHeap<Constraint*>(&compareConstraints);
70 for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();++i) {
71 Variable *v=*i;
72 vector<Constraint*> *cs=in?&(v->in):&(v->out);
73 for (Cit j=cs->begin();j!=cs->end();++j) {
74 Constraint *c=*j;
75 c->timeStamp=blockTimeCtr;
76 if (c->left->block != this && in || c->right->block != this && !in) {
77 h->insert(c);
78 }
79 }
80 }
81 }
82 void Block::merge(Block* b, Constraint* c) {
83 #ifdef RECTANGLE_OVERLAP_LOGGING
84 ofstream f(LOGFILE,ios::app);
85 f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
86 #endif
87 double dist = c->right->offset - c->left->offset - c->gap;
88 Block *l=c->left->block;
89 Block *r=c->right->block;
90 if (vars->size() < b->vars->size()) {
91 r->merge(l,c,dist);
92 } else {
93 l->merge(r,c,-dist);
94 }
95 #ifdef RECTANGLE_OVERLAP_LOGGING
96 f<<" merged block="<<(b->deleted?*this:*b)<<endl;
97 #endif
98 }
99 /**
100 * Merges b into this block across c. Can be either a
101 * right merge or a left merge
102 * @param b block to merge into this
103 * @param c constraint being merged
104 * @param distance separation required to satisfy c
105 */
106 void Block::merge(Block *b, Constraint *c, double dist) {
107 #ifdef RECTANGLE_OVERLAP_LOGGING
108 ofstream f(LOGFILE,ios::app);
109 f<<" merging: "<<*b<<"dist="<<dist<<endl;
110 #endif
111 c->active=true;
112 wposn+=b->wposn-dist*b->weight;
113 weight+=b->weight;
114 posn=wposn/weight;
115 for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();++i) {
116 Variable *v=*i;
117 v->block=this;
118 v->offset+=dist;
119 vars->push_back(v);
120 }
121 b->deleted=true;
122 }
124 void Block::mergeIn(Block *b) {
125 #ifdef RECTANGLE_OVERLAP_LOGGING
126 ofstream f(LOGFILE,ios::app);
127 f<<" merging constraint heaps... "<<endl;
128 #endif
129 // We check the top of the heaps to remove possible internal constraints
130 findMinInConstraint();
131 b->findMinInConstraint();
132 in->merge(b->in);
133 #ifdef RECTANGLE_OVERLAP_LOGGING
134 f<<" merged heap: "<<*in<<endl;
135 #endif
136 }
137 void Block::mergeOut(Block *b) {
138 findMinOutConstraint();
139 b->findMinOutConstraint();
140 out->merge(b->out);
141 }
142 Constraint *Block::findMinInConstraint() {
143 Constraint *v = NULL;
144 vector<Constraint*> outOfDate;
145 while (!in->isEmpty()) {
146 v = in->findMin();
147 Block *lb=v->left->block;
148 Block *rb=v->right->block;
149 // rb may not be this if called between merge and mergeIn
150 #ifdef RECTANGLE_OVERLAP_LOGGING
151 ofstream f(LOGFILE,ios::app);
152 f<<" checking constraint ... "<<*v;
153 f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
154 #endif
155 if(lb == rb) {
156 // constraint has been merged into the same block
157 #ifdef RECTANGLE_OVERLAP_LOGGING
158 if(v->slack()<0) {
159 f<<" violated internal constraint found! "<<*v<<endl;
160 f<<" lb="<<*lb<<endl;
161 f<<" rb="<<*rb<<endl;
162 }
163 #endif
164 in->deleteMin();
165 #ifdef RECTANGLE_OVERLAP_LOGGING
166 f<<" ... skipping internal constraint"<<endl;
167 #endif
168 } else if(v->timeStamp < lb->timeStamp) {
169 // block at other end of constraint has been moved since this
170 in->deleteMin();
171 outOfDate.push_back(v);
172 #ifdef RECTANGLE_OVERLAP_LOGGING
173 f<<" reinserting out of date (reinsert later)"<<endl;
174 #endif
175 } else {
176 break;
177 }
178 }
179 for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
180 v=*i;
181 v->timeStamp=blockTimeCtr;
182 in->insert(v);
183 }
184 if(in->isEmpty()) {
185 v=NULL;
186 } else {
187 v=in->findMin();
188 }
189 return v;
190 }
191 Constraint *Block::findMinOutConstraint() {
192 if(out->isEmpty()) return NULL;
193 Constraint *v = out->findMin();
194 while (v->left->block == v->right->block) {
195 out->deleteMin();
196 if(out->isEmpty()) return NULL;
197 v = out->findMin();
198 }
199 return v;
200 }
201 void Block::deleteMinInConstraint() {
202 in->deleteMin();
203 #ifdef RECTANGLE_OVERLAP_LOGGING
204 ofstream f(LOGFILE,ios::app);
205 f<<"deleteMinInConstraint... "<<endl;
206 f<<" result: "<<*in<<endl;
207 #endif
208 }
209 void Block::deleteMinOutConstraint() {
210 out->deleteMin();
211 }
212 inline bool Block::canFollowLeft(Constraint *c, Variable *last) {
213 return c->left->block==this && c->active && last!=c->left;
214 }
215 inline bool Block::canFollowRight(Constraint *c, Variable *last) {
216 return c->right->block==this && c->active && last!=c->right;
217 }
219 // computes the derivative of v and the lagrange multipliers
220 // of v's out constraints (as the recursive sum of those below.
221 // Does not backtrack over u.
222 // also records the constraint with minimum lagrange multiplier
223 // in min_lm
224 double Block::compute_dfdv(Variable *v, Variable *u, 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(Variable* r, Variable* v, Variable* u,
258 Direction dir = NONE, bool changedDirection = false) {
259 double dfdv=v->weight*(v->position() - v->desiredPosition);
260 Constraint *m=NULL;
261 for(Cit it(v->in.begin());it!=v->in.end();++it) {
262 Constraint *c=*it;
263 if(canFollowLeft(c,u)) {
264 if(dir==RIGHT) {
265 changedDirection = true;
266 }
267 if(c->left==r) {
268 r=NULL;
269 if(!c->equality) m=c;
270 }
271 Pair p=compute_dfdv_between(r,c->left,v,
272 LEFT,changedDirection);
273 dfdv -= c->lm = -p.first;
274 if(r && p.second)
275 m = p.second;
276 }
277 }
278 for(Cit it(v->out.begin());it!=v->out.end();++it) {
279 Constraint *c=*it;
280 if(canFollowRight(c,u)) {
281 if(dir==LEFT) {
282 changedDirection = true;
283 }
284 if(c->right==r) {
285 r=NULL;
286 if(!c->equality) m=c;
287 }
288 Pair p=compute_dfdv_between(r,c->right,v,
289 RIGHT,changedDirection);
290 dfdv += c->lm = p.first;
291 if(r && p.second)
292 m = changedDirection && !c->equality && c->lm < p.second->lm
293 ? c
294 : p.second;
295 }
296 }
297 return Pair(dfdv,m);
298 }
300 // resets LMs for all active constraints to 0 by
301 // traversing active constraint tree starting from v,
302 // not back tracking over u
303 void Block::reset_active_lm(Variable *v, Variable *u) {
304 for(Cit it=v->out.begin();it!=v->out.end();++it) {
305 Constraint *c=*it;
306 if(canFollowRight(c,u)) {
307 c->lm=0;
308 reset_active_lm(c->right,v);
309 }
310 }
311 for(Cit it=v->in.begin();it!=v->in.end();++it) {
312 Constraint *c=*it;
313 if(canFollowLeft(c,u)) {
314 c->lm=0;
315 reset_active_lm(c->left,v);
316 }
317 }
318 }
319 /**
320 * finds the constraint with the minimum lagrange multiplier, that is, the constraint
321 * that most wants to split
322 */
323 Constraint *Block::findMinLM() {
324 Constraint *min_lm=NULL;
325 reset_active_lm(vars->front(),NULL);
326 compute_dfdv(vars->front(),NULL,min_lm);
327 return min_lm;
328 }
329 Constraint *Block::findMinLMBetween(Variable* lv, Variable* rv) {
330 Constraint *min_lm=NULL;
331 reset_active_lm(vars->front(),NULL);
332 min_lm=compute_dfdv_between(rv,lv,NULL).second;
333 return min_lm;
334 }
336 // populates block b by traversing the active constraint tree adding variables as they're
337 // visited. Starts from variable v and does not backtrack over variable u.
338 void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) {
339 b->addVariable(v);
340 for (Cit c=v->in.begin();c!=v->in.end();++c) {
341 if (canFollowLeft(*c,u))
342 populateSplitBlock(b, (*c)->left, v);
343 }
344 for (Cit c=v->out.begin();c!=v->out.end();++c) {
345 if (canFollowRight(*c,u))
346 populateSplitBlock(b, (*c)->right, v);
347 }
348 }
349 /**
350 * Block needs to be split because of a violated constraint between vl and vr.
351 * We need to search the active constraint tree between l and r and find the constraint
352 * with min lagrangrian multiplier and split at that point.
353 * Returns the split constraint
354 */
355 Constraint* Block::splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb) {
356 #ifdef RECTANGLE_OVERLAP_LOGGING
357 ofstream f(LOGFILE,ios::app);
358 f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
359 #endif
360 Constraint *c=findMinLMBetween(vl, vr);
361 #ifdef RECTANGLE_OVERLAP_LOGGING
362 f<<" going to split on: "<<*c<<endl;
363 #endif
364 split(lb,rb,c);
365 deleted = true;
366 return c;
367 }
368 /**
369 * Creates two new blocks, l and r, and splits this block across constraint c,
370 * placing the left subtree of constraints (and associated variables) into l
371 * and the right into r.
372 */
373 void Block::split(Block* &l, Block* &r, Constraint* c) {
374 c->active=false;
375 l=new Block();
376 populateSplitBlock(l,c->left,c->right);
377 r=new Block();
378 populateSplitBlock(r,c->right,c->left);
379 }
381 /**
382 * Computes the cost (squared euclidean distance from desired positions) of the
383 * current positions for variables in this block
384 */
385 double Block::cost() {
386 double c = 0;
387 for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();++v) {
388 double diff = (*v)->position() - (*v)->desiredPosition;
389 c += (*v)->weight * diff * diff;
390 }
391 return c;
392 }
393 ostream& operator <<(ostream &os, const Block &b)
394 {
395 os<<"Block:";
396 for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();++v) {
397 os<<" "<<**v;
398 }
399 if(b.deleted) {
400 os<<" Deleted!";
401 }
402 return os;
403 }