src/libvpsc/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 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 }
  46
  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 }
 122
 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 }
 217
 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 }
 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(
 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 }
 300
 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 }
 336
 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 }
 398
 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 }