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