src/removeoverlap/solve_VPSC.cpp

   1 /**
   2  * \brief Remove overlaps function
   3  *
   4  * Authors:
   5  *   Tim Dwyer <tgdwyer@gmail.com>
   6  *
   7  * Copyright (C) 2005 Authors
   8  *
   9  * Released under GNU GPL.  Read the file 'COPYING' for more information.
  10  */
  11
  12 #include <cassert>
  13 #include "constraint.h"
  14 #include "block.h"
  15 #include "blocks.h"
  16 #include "solve_VPSC.h"
  17 #ifdef RECTANGLE_OVERLAP_LOGGING
  18 #include <fstream>
  19 using std::ios;
  20 using std::ofstream;
  21 using std::endl;
  22 #endif
  23
  24 using std::list;
  25 using std::set;
  26
  27 VPSC::VPSC(Variable *vs[], const int n, Constraint *cs[], const int m) : cs(cs), m(m) {
  28         //assert(!constraintGraphIsCyclic(vs,n));
  29         bs=new Blocks(vs,n);
  30 #ifdef RECTANGLE_OVERLAP_LOGGING
  31         printBlocks();
  32 #endif
  33 }
  34 VPSC::~VPSC() {
  35         delete bs;
  36 }
  37
  38 // useful in debugging
  39 void VPSC::printBlocks() {
  40 #ifdef RECTANGLE_OVERLAP_LOGGING
  41         ofstream f(LOGFILE,ios::app);
  42         for(set<Block*>::iterator i=bs->begin();i!=bs->end();i++) {
  43                 Block *b=*i;
  44                 f<<"  "<<*b<<endl;
  45         }
  46         for(int i=0;i<m;i++) {
  47                 f<<"  "<<*cs[i]<<endl;
  48         }
  49 #endif
  50 }
  51 /**
  52 * Produces a feasible - though not necessarily optimal - solution by
  53 * examining blocks in the partial order defined by the directed acyclic
  54 * graph of constraints. For each block (when processing left to right) we
  55 * maintain the invariant that all constraints to the left of the block
  56 * (incoming constraints) are satisfied. This is done by repeatedly merging
  57 * blocks into bigger blocks across violated constraints (most violated
  58 * first) fixing the position of variables inside blocks relative to one
  59 * another so that constraints internal to the block are satisfied.
  60 */
  61 void VPSC::satisfy() {
  62         list<Variable*> *vs=bs->totalOrder();
  63         for(list<Variable*>::iterator i=vs->begin();i!=vs->end();i++) {
  64                 Variable *v=*i;
  65                 if(!v->block->deleted) {
  66                         bs->mergeLeft(v->block);
  67                 }
  68         }
  69         bs->cleanup();
  70         for(int i=0;i<m;i++) {
  71                 if(cs[i]->slack()<-0.0000001) {
  72 #ifdef RECTANGLE_OVERLAP_LOGGING
  73                         ofstream f(LOGFILE,ios::app);
  74                         f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
  75 #endif
  76                         //assert(cs[i]->slack()>-0.0000001);
  77                         throw "Unsatisfied constraint";
  78                 }
  79         }
  80         delete vs;
  81 }
  82
  83 void VPSC::refine() {
  84         bool solved=false;
  85         // Solve shouldn't loop indefinately
  86         // ... but just to make sure we limit the number of iterations
  87         int maxtries=100;
  88         while(!solved&&maxtries>=0) {
  89                 solved=true;
  90                 maxtries--;
  91                 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
  92                         Block *b=*i;
  93                         b->setUpInConstraints();
  94                         b->setUpOutConstraints();
  95                 }
  96                 for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
  97                         Block *b=*i;
  98                         Constraint *c=b->findMinLM();
  99                         if(c!=NULL && c->lm<0) {
 100 #ifdef RECTANGLE_OVERLAP_LOGGING
 101                                 ofstream f(LOGFILE,ios::app);
 102                                 f<<"Split on constraint: "<<*c<<endl;
 103 #endif
 104                                 // Split on c
 105                                 Block *l=NULL, *r=NULL;
 106                                 bs->split(b,l,r,c);
 107                                 bs->cleanup();
 108                                 // split alters the block set so we have to restart
 109                                 solved=false;
 110                                 break;
 111                         }
 112                 }
 113         }
 114         for(int i=0;i<m;i++) {
 115                 if(cs[i]->slack()<-0.0000001) {
 116                         assert(cs[i]->slack()>-0.0000001);
 117                         throw "Unsatisfied constraint";
 118                 }
 119         }
 120 }
 121 /**
 122  * Calculate the optimal solution. After using satisfy() to produce a
 123  * feasible solution, refine() examines each block to see if further
 124  * refinement is possible by splitting the block. This is done repeatedly
 125  * until no further improvement is possible.
 126  */
 127 void VPSC::solve() {
 128         satisfy();
 129         refine();
 130 }
 131
 132 /**
 133  * incremental version of solve that should allow refinement after blocks are
 134  * moved.  Work in progress.
 135  */
 136 void VPSC::move_and_split() {
 137         //assert(!blockGraphIsCyclic());
 138         for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
 139                 Block *b=*i;
 140                 if(!b->deleted) {
 141                         b->wposn = b->desiredWeightedPosition();
 142                         b->posn = b->wposn / b->weight;
 143                         Variable *v=b->vars->front();
 144                         bs->mergeLeft(b);
 145                         // b may be merged away, so get any new block from one of its members
 146                         bs->mergeRight(v->block);
 147                 }
 148         }
 149         bs->cleanup();
 150         // assert(!blockGraphIsCyclic());
 151         refine();
 152 }
 153
 154 #include <map>
 155 using std::map;
 156 using std::vector;
 157 struct node {
 158         set<node*> in;
 159         set<node*> out;
 160 };
 161 /*
 162 // useful in debugging - cycles would be BAD
 163 bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) {
 164         map<Variable*, node*> varmap;
 165         vector<node*> graph;
 166         for(int i=0;i<n;i++) {
 167                 node *u=new node;
 168                 graph.push_back(u);
 169                 varmap[vs[i]]=u;
 170         }
 171         for(int i=0;i<n;i++) {
 172                 for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) {
 173                         Variable *l=(*c)->left;
 174                         varmap[vs[i]]->in.insert(varmap[l]);
 175                 }
 176
 177                 for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) {
 178                         Variable *r=(*c)->right;
 179                         varmap[vs[i]]->out.insert(varmap[r]);
 180                 }
 181         }
 182         while(graph.size()>0) {
 183                 node *u=NULL;
 184                 vector<node*>::iterator i=graph.begin();
 185                 for(;i!=graph.end();i++) {
 186                         u=*i;
 187                         if(u->in.size()==0) {
 188                                 break;
 189                         }
 190                 }
 191                 if(i==graph.end() && graph.size()>0) {
 192                         //cycle found!
 193                         return true;
 194                 } else {
 195                         graph.erase(i);
 196                         for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
 197                                 node *v=*j;
 198                                 v->in.erase(u);
 199                         }
 200                         delete u;
 201                 }
 202         }
 203         for(unsigned i=0; i<graph.size(); i++) {
 204                 delete graph[i];
 205         }
 206         return false;
 207 }
 208
 209 // useful in debugging - cycles would be BAD
 210 bool VPSC::blockGraphIsCyclic() {
 211         map<Block*, node*> bmap;
 212         vector<node*> graph;
 213         for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
 214                 Block *b=*i;
 215                 node *u=new node;
 216                 graph.push_back(u);
 217                 bmap[b]=u;
 218         }
 219         for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
 220                 Block *b=*i;
 221                 b->setUpInConstraints();
 222                 Constraint *c=b->findMinInConstraint();
 223                 while(c!=NULL) {
 224                         Block *l=c->left->block;
 225                         bmap[b]->in.insert(bmap[l]);
 226                         b->deleteMinInConstraint();
 227                         c=b->findMinInConstraint();
 228                 }
 229
 230                 b->setUpOutConstraints();
 231                 c=b->findMinOutConstraint();
 232                 while(c!=NULL) {
 233                         Block *r=c->right->block;
 234                         bmap[b]->out.insert(bmap[r]);
 235                         b->deleteMinOutConstraint();
 236                         c=b->findMinOutConstraint();
 237                 }
 238         }
 239         while(graph.size()>0) {
 240                 node *u=NULL;
 241                 vector<node*>::iterator i=graph.begin();
 242                 for(;i!=graph.end();i++) {
 243                         u=*i;
 244                         if(u->in.size()==0) {
 245                                 break;
 246                         }
 247                 }
 248                 if(i==graph.end() && graph.size()>0) {
 249                         //cycle found!
 250                         return true;
 251                 } else {
 252                         graph.erase(i);
 253                         for(set<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
 254                                 node *v=*j;
 255                                 v->in.erase(u);
 256                         }
 257                         delete u;
 258                 }
 259         }
 260         for(unsigned i=0; i<graph.size(); i++) {
 261                 delete graph[i];
 262         }
 263         return false;
 264 }
 265 */
 266