src/removeoverlap/solve_VPSC.cpp

   1 /**
   2  * \brief Solve an instance of the "Variable Placement with Separation
   3  * Constraints" problem.
   4  *
   5  * Authors:
   6  *   Tim Dwyer <tgdwyer@gmail.com>
   7  *
   8  * Copyright (C) 2005 Authors
   9  *
  10  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  11  */
  12
  13 #include <cassert>
  14 #include "constraint.h"
  15 #include "block.h"
  16 #include "blocks.h"
  17 #include "solve_VPSC.h"
  18 #include <math.h>
  19 #include <sstream>
  20 #ifdef RECTANGLE_OVERLAP_LOGGING
  21 #include <fstream>
  22 using std::ios;
  23 using std::ofstream;
  24 using std::endl;
  25 #endif
  26
  27 using std::ostringstream;
  28 using std::list;
  29 using std::set;
  30
  31 IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[])
  32         : VPSC(n,vs,m,cs) {
  33         inactive.assign(cs,cs+m);
  34         for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) {
  35                 (*i)->active=false;
  36         }
  37 }
  38 VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) : cs(cs), m(m), vs(vs) {
  39         bs=new Blocks(n, vs);
  40 #ifdef RECTANGLE_OVERLAP_LOGGING
  41         printBlocks();
  42         assert(!constraintGraphIsCyclic(n,vs));
  43 #endif
  44 }
  45 VPSC::~VPSC() {
  46         delete bs;
  47 }
  48
  49 // useful in debugging
  50 void VPSC::printBlocks() {
  51 #ifdef RECTANGLE_OVERLAP_LOGGING
  52         ofstream f(LOGFILE,ios::app);
  53         for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
  54                 Block *b=*i;
  55                 f<<"  "<<*b<<endl;
  56         }
  57         for(unsigned i=0;i<m;i++) {
  58                 f<<"  "<<*cs[i]<<endl;
  59         }
  60 #endif
  61 }
  62 /**
  63 * Produces a feasible - though not necessarily optimal - solution by
  64 * examining blocks in the partial order defined by the directed acyclic
  65 * graph of constraints. For each block (when processing left to right) we
  66 * maintain the invariant that all constraints to the left of the block
  67 * (incoming constraints) are satisfied. This is done by repeatedly merging
  68 * blocks into bigger blocks across violated constraints (most violated
  69 * first) fixing the position of variables inside blocks relative to one
  70 * another so that constraints internal to the block are satisfied.
  71 */
  72 void VPSC::satisfy() {
  73         list<Variable*> *vs=bs->totalOrder();
  74         for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
  75                 Variable *v=*i;
  76                 if(!v->block->deleted) {
  77                         bs->mergeLeft(v->block);
  78                 }
  79         }
  80         bs->cleanup();
  81         for(unsigned i=0;i<m;i++) {
  82                 if(cs[i]->slack()<-0.0000001) {
  83 #ifdef RECTANGLE_OVERLAP_LOGGING
  84                         ofstream f(LOGFILE,ios::app);
  85                         f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
  86 #endif
  87                         //assert(cs[i]->slack()>-0.0000001);
  88                         throw "Unsatisfied constraint";
  89                 }
  90         }
  91         delete vs;
  92 }
  93
  94 void VPSC::refine() {
  95         bool solved=false;
  96         // Solve shouldn't loop indefinately
  97         // ... but just to make sure we limit the number of iterations
  98         unsigned maxtries=100;
  99         while(!solved&&maxtries>0) {
 100                 solved=true;
 101                 maxtries--;
 102                 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
 103                         Block *b=*i;
 104                         b->setUpInConstraints();
 105                         b->setUpOutConstraints();
 106                 }
 107                 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
 108                         Block *b=*i;
 109                         Constraint *c=b->findMinLM();
 110                         if(c!=NULL && c->lm<0) {
 111 #ifdef RECTANGLE_OVERLAP_LOGGING
 112                                 ofstream f(LOGFILE,ios::app);
 113                                 f<<"Split on constraint: "<<*c<<endl;
 114 #endif
 115                                 // Split on c
 116                                 Block *l=NULL, *r=NULL;
 117                                 bs->split(b,l,r,c);
 118                                 bs->cleanup();
 119                                 // split alters the block set so we have to restart
 120                                 solved=false;
 121                                 break;
 122                         }
 123                 }
 124         }
 125         for(unsigned i=0;i<m;i++) {
 126                 if(cs[i]->slack()<-0.0000001) {
 127                         assert(cs[i]->slack()>-0.0000001);
 128                         throw "Unsatisfied constraint";
 129                 }
 130         }
 131 }
 132 /**
 133  * Calculate the optimal solution. After using satisfy() to produce a
 134  * feasible solution, refine() examines each block to see if further
 135  * refinement is possible by splitting the block. This is done repeatedly
 136  * until no further improvement is possible.
 137  */
 138 void VPSC::solve() {
 139         satisfy();
 140         refine();
 141 }
 142
 143 void IncVPSC::solve() {
 144 #ifdef RECTANGLE_OVERLAP_LOGGING
 145         ofstream f(LOGFILE,ios::app);
 146         f<<"solve_inc()..."<<endl;
 147 #endif
 148         double lastcost,cost = bs->cost();
 149         do {
 150                 lastcost=cost;
 151                 satisfy();
 152                 splitBlocks();
 153                 cost = bs->cost();
 154 #ifdef RECTANGLE_OVERLAP_LOGGING
 155         f<<"  cost="<<cost<<endl;
 156 #endif
 157         } while(fabs(lastcost-cost)>0.0001);
 158 }
 159 /**
 160  * incremental version of satisfy that allows refinement after blocks are
 161  * moved.
 162  *
 163  *  - move blocks to new positions
 164  *  - repeatedly merge across most violated constraint until no more
 165  *    violated constraints exist
 166  *
 167  * Note: there is a special case to handle when the most violated constraint
 168  * is between two variables in the same block.  Then, we must split the block
 169  * over an active constraint between the two variables.  We choose the
 170  * constraint with the most negative lagrangian multiplier.
 171  */
 172 void IncVPSC::satisfy() {
 173 #ifdef RECTANGLE_OVERLAP_LOGGING
 174         ofstream f(LOGFILE,ios::app);
 175         f<<"satisfy_inc()..."<<endl;
 176 #endif
 177         splitBlocks();
 178         long splitCtr = 0;
 179         Constraint* v = NULL;
 180         while((v=mostViolated(inactive))&&(v->equality || v->slack()<-0.000001)) {
 181                 assert(!v->active);
 182                 Block *lb = v->left->block, *rb = v->right->block;
 183                 if(lb != rb) {
 184                         lb->merge(rb,v);
 185                 } else {
 186                         if(splitCtr++>10000) {
 187                                 throw "Cycle Error!";
 188                         }
 189                         // constraint is within block, need to split first
 190                         inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb));
 191                         lb->merge(rb,v);
 192                         bs->insert(lb);
 193                 }
 194         }
 195 #ifdef RECTANGLE_OVERLAP_LOGGING
 196         f<<"  finished merges."<<endl;
 197 #endif
 198         bs->cleanup();
 199         for(unsigned i=0;i<m;i++) {
 200                 v=cs[i];
 201                 if(v->slack()<-0.0000001) {
 202                         //assert(cs[i]->slack()>-0.0000001);
 203                         ostringstream s;
 204                         s<<"Unsatisfied constraint: "<<*v;
 205                         throw s.str().c_str();
 206                 }
 207         }
 208 #ifdef RECTANGLE_OVERLAP_LOGGING
 209         f<<"  finished cleanup."<<endl;
 210         printBlocks();
 211 #endif
 212 }
 213 void IncVPSC::moveBlocks() {
 214 #ifdef RECTANGLE_OVERLAP_LOGGING
 215         ofstream f(LOGFILE,ios::app);
 216         f<<"moveBlocks()..."<<endl;
 217 #endif
 218         for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
 219                 Block *b = *i;
 220                 b->wposn = b->desiredWeightedPosition();
 221                 b->posn = b->wposn / b->weight;
 222         }
 223 #ifdef RECTANGLE_OVERLAP_LOGGING
 224         f<<"  moved blocks."<<endl;
 225 #endif
 226 }
 227 void IncVPSC::splitBlocks() {
 228 #ifdef RECTANGLE_OVERLAP_LOGGING
 229         ofstream f(LOGFILE,ios::app);
 230 #endif
 231         moveBlocks();
 232         splitCnt=0;
 233         // Split each block if necessary on min LM
 234         for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
 235                 Block* b = *i;
 236                 Constraint* v=b->findMinLM();
 237                 if(v!=NULL && v->lm < -0.0000001) {
 238                         assert(!v->equality);
 239 #ifdef RECTANGLE_OVERLAP_LOGGING
 240                         f<<"    found split point: "<<*v<<" lm="<<v->lm<<endl;
 241 #endif
 242                         splitCnt++;
 243                         Block *b = v->left->block, *l=NULL, *r=NULL;
 244                         assert(v->left->block == v->right->block);
 245                         double pos = b->posn;
 246                         b->split(l,r,v);
 247                         l->posn=r->posn=pos;
 248                         l->wposn = l->posn * l->weight;
 249                         r->wposn = r->posn * r->weight;
 250                         bs->insert(l);
 251                         bs->insert(r);
 252                         b->deleted=true;
 253                         inactive.push_back(v);
 254 #ifdef RECTANGLE_OVERLAP_LOGGING
 255                         f<<"  new blocks: "<<*l<<" and "<<*r<<endl;
 256 #endif
 257                 }
 258         }
 259 #ifdef RECTANGLE_OVERLAP_LOGGING
 260         f<<"  finished splits."<<endl;
 261 #endif
 262         bs->cleanup();
 263 }
 264
 265 /**
 266  * Scan constraint list for the most violated constraint, or the first equality
 267  * constraint
 268  */
 269 Constraint* IncVPSC::mostViolated(ConstraintList &l) {
 270         double minSlack = DBL_MAX;
 271         Constraint* v=NULL;
 272 #ifdef RECTANGLE_OVERLAP_LOGGING
 273         ofstream f(LOGFILE,ios::app);
 274         f<<"Looking for most violated..."<<endl;
 275 #endif
 276         ConstraintList::iterator end = l.end();
 277         ConstraintList::iterator deletePoint = end;
 278         for(ConstraintList::iterator i=l.begin();i!=end;++i) {
 279                 Constraint *c=*i;
 280                 double slack = c->slack();
 281                 if(c->equality || slack < minSlack) {
 282                         minSlack=slack;
 283                         v=c;
 284                         deletePoint=i;
 285                         if(c->equality) break;
 286                 }
 287         }
 288         // Because the constraint list is not order dependent we just
 289         // move the last element over the deletePoint and resize
 290         // downwards.  There is always at least 1 element in the
 291         // vector because of search.
 292         if(deletePoint != end && (minSlack<-0.0000001||v->equality)) {
 293                 *deletePoint = l[l.size()-1];
 294                 l.resize(l.size()-1);
 295         }
 296 #ifdef RECTANGLE_OVERLAP_LOGGING
 297         f<<"  most violated is: "<<*v<<endl;
 298 #endif
 299         return v;
 300 }
 301
 302 #include <map>
 303 using std::map;
 304 using std::vector;
 305 struct node {
 306         set<node*> in;
 307         set<node*> out;
 308 };
 309 // useful in debugging - cycles would be BAD
 310 bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
 311         map<Variable*, node*> varmap;
 312         vector<node*> graph;
 313         for(unsigned i=0;i<n;i++) {
 314                 node *u=new node;
 315                 graph.push_back(u);
 316                 varmap[vs[i]]=u;
 317         }
 318         for(unsigned i=0;i<n;i++) {
 319                 for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
 320                         Variable *l=(*c)->left;
 321                         varmap[vs[i]]->in.insert(varmap[l]);
 322                 }
 323
 324                 for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
 325                         Variable *r=(*c)->right;
 326                         varmap[vs[i]]->out.insert(varmap[r]);
 327                 }
 328         }
 329         while(graph.size()>0) {
 330                 node *u=NULL;
 331                 vector<node*>::iterator i=graph.begin();
 332                 for(;i!=graph.end();++i) {
 333                         u=*i;
 334                         if(u->in.size()==0) {
 335                                 break;
 336                         }
 337                 }
 338                 if(i==graph.end() && graph.size()>0) {
 339                         //cycle found!
 340                         return true;
 341                 } else {
 342                         graph.erase(i);
 343                         for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
 344                                 node *v=*j;
 345                                 v->in.erase(u);
 346                         }
 347                         delete u;
 348                 }
 349         }
 350         for(unsigned i=0; i<graph.size(); ++i) {
 351                 delete graph[i];
 352         }
 353         return false;
 354 }
 355
 356 // useful in debugging - cycles would be BAD
 357 bool VPSC::blockGraphIsCyclic() {
 358         map<Block*, node*> bmap;
 359         vector<node*> graph;
 360         for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
 361                 Block *b=*i;
 362                 node *u=new node;
 363                 graph.push_back(u);
 364                 bmap[b]=u;
 365         }
 366         for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
 367                 Block *b=*i;
 368                 b->setUpInConstraints();
 369                 Constraint *c=b->findMinInConstraint();
 370                 while(c!=NULL) {
 371                         Block *l=c->left->block;
 372                         bmap[b]->in.insert(bmap[l]);
 373                         b->deleteMinInConstraint();
 374                         c=b->findMinInConstraint();
 375                 }
 376
 377                 b->setUpOutConstraints();
 378                 c=b->findMinOutConstraint();
 379                 while(c!=NULL) {
 380                         Block *r=c->right->block;
 381                         bmap[b]->out.insert(bmap[r]);
 382                         b->deleteMinOutConstraint();
 383                         c=b->findMinOutConstraint();
 384                 }
 385         }
 386         while(graph.size()>0) {
 387                 node *u=NULL;
 388                 vector<node*>::iterator i=graph.begin();
 389                 for(;i!=graph.end();++i) {
 390                         u=*i;
 391                         if(u->in.size()==0) {
 392                                 break;
 393                         }
 394                 }
 395                 if(i==graph.end() && graph.size()>0) {
 396                         //cycle found!
 397                         return true;
 398                 } else {
 399                         graph.erase(i);
 400                         for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
 401                                 node *v=*j;
 402                                 v->in.erase(u);
 403                         }
 404                         delete u;
 405                 }
 406         }
 407         for(unsigned i=0; i<graph.size(); i++) {
 408                 delete graph[i];
 409         }
 410         return false;
 411 }
 412