src/removeoverlap/block.cpp

   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;
  25
  26 typedef vector<Constraint*>::iterator Cit;
  27
  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 }
  47
  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 }
 123
 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 }
 218
 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 }
 242
 243
 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 }
 299
 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 }
 335
 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 }
 380
 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 }