/** * \brief Solve an instance of the "Variable Placement with Separation * Constraints" problem. * * Authors: * Tim Dwyer <tgdwyer@gmail.com> * * Copyright (C) 2005 Authors * * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include <cassert> #include "constraint.h" #include "block.h" #include "blocks.h" #include "solve_VPSC.h" #include <math.h> #include <sstream> #ifdef RECTANGLE_OVERLAP_LOGGING #include <fstream> #endif #include <map> using namespace std; namespace vpsc { static const double ZERO_UPPERBOUND=-0.0000001; IncSolver::IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : Solver(n,vs,m,cs) { inactive.assign(cs,cs+m); for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) { (*i)->active=false; } } Solver::Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) { bs=new Blocks(n, vs); #ifdef RECTANGLE_OVERLAP_LOGGING printBlocks(); //assert(!constraintGraphIsCyclic(n,vs)); #endif } Solver::~Solver() { delete bs; } // useful in debugging void Solver::printBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; f<<" "<<*b<<endl; } for(unsigned i=0;i<m;i++) { f<<" "<<*cs[i]<<endl; } #endif } /** * Produces a feasible - though not necessarily optimal - solution by * examining blocks in the partial order defined by the directed acyclic * graph of constraints. For each block (when processing left to right) we * maintain the invariant that all constraints to the left of the block * (incoming constraints) are satisfied. This is done by repeatedly merging * blocks into bigger blocks across violated constraints (most violated * first) fixing the position of variables inside blocks relative to one * another so that constraints internal to the block are satisfied. */ 00072 void Solver::satisfy() { list<Variable*> *vs=bs->totalOrder(); for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) { Variable *v=*i; if(!v->block->deleted) { bs->mergeLeft(v->block); } } bs->cleanup(); for(unsigned i=0;i<m;i++) { if(cs[i]->slack() < ZERO_UPPERBOUND) { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl; #endif //assert(cs[i]->slack()>-0.0000001); throw "Unsatisfied constraint"; } } delete vs; } void Solver::refine() { bool solved=false; // Solve shouldn't loop indefinately // ... but just to make sure we limit the number of iterations unsigned maxtries=100; while(!solved&&maxtries>0) { solved=true; maxtries--; for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); b->setUpOutConstraints(); } for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; Constraint *c=b->findMinLM(); if(c!=NULL && c->lm<0) { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"Split on constraint: "<<*c<<endl; #endif // Split on c Block *l=NULL, *r=NULL; bs->split(b,l,r,c); bs->cleanup(); // split alters the block set so we have to restart solved=false; break; } } } for(unsigned i=0;i<m;i++) { if(cs[i]->slack() < ZERO_UPPERBOUND) { assert(cs[i]->slack()>ZERO_UPPERBOUND); throw "Unsatisfied constraint"; } } } /** * Calculate the optimal solution. After using satisfy() to produce a * feasible solution, refine() examines each block to see if further * refinement is possible by splitting the block. This is done repeatedly * until no further improvement is possible. */ 00138 void Solver::solve() { satisfy(); refine(); } void IncSolver::solve() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"solve_inc()..."<<endl; #endif double lastcost,cost = bs->cost(); do { lastcost=cost; satisfy(); splitBlocks(); cost = bs->cost(); #ifdef RECTANGLE_OVERLAP_LOGGING f<<" cost="<<cost<<endl; #endif } while(fabs(lastcost-cost)>0.0001); } /** * incremental version of satisfy that allows refinement after blocks are * moved. * * - move blocks to new positions * - repeatedly merge across most violated constraint until no more * violated constraints exist * * Note: there is a special case to handle when the most violated constraint * is between two variables in the same block. Then, we must split the block * over an active constraint between the two variables. We choose the * constraint with the most negative lagrangian multiplier. */ void IncSolver::satisfy() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"satisfy_inc()..."<<endl; #endif splitBlocks(); long splitCtr = 0; Constraint* v = NULL; while((v=mostViolated(inactive))&&(v->equality || v->slack() < ZERO_UPPERBOUND)) { assert(!v->active); Block *lb = v->left->block, *rb = v->right->block; if(lb != rb) { lb->merge(rb,v); } else { if(lb->isActiveDirectedPathBetween(v->right,v->left)) { // cycle found, relax the violated, cyclic constraint v->gap = v->slack(); continue; } if(splitCtr++>10000) { throw "Cycle Error!"; } // constraint is within block, need to split first inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb)); lb->merge(rb,v); bs->insert(lb); } } #ifdef RECTANGLE_OVERLAP_LOGGING f<<" finished merges."<<endl; #endif bs->cleanup(); for(unsigned i=0;i<m;i++) { v=cs[i]; if(v->slack() < ZERO_UPPERBOUND) { ostringstream s; s<<"Unsatisfied constraint: "<<*v; #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<s.str()<<endl; #endif throw s.str().c_str(); } } #ifdef RECTANGLE_OVERLAP_LOGGING f<<" finished cleanup."<<endl; printBlocks(); #endif } void IncSolver::moveBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"moveBlocks()..."<<endl; #endif for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) { Block *b = *i; b->wposn = b->desiredWeightedPosition(); b->posn = b->wposn / b->weight; } #ifdef RECTANGLE_OVERLAP_LOGGING f<<" moved blocks."<<endl; #endif } void IncSolver::splitBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); #endif moveBlocks(); splitCnt=0; // Split each block if necessary on min LM for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) { Block* b = *i; Constraint* v=b->findMinLM(); if(v!=NULL && v->lm < ZERO_UPPERBOUND) { assert(!v->equality); #ifdef RECTANGLE_OVERLAP_LOGGING f<<" found split point: "<<*v<<" lm="<<v->lm<<endl; #endif splitCnt++; Block *b = v->left->block, *l=NULL, *r=NULL; assert(v->left->block == v->right->block); double pos = b->posn; b->split(l,r,v); l->posn=r->posn=pos; l->wposn = l->posn * l->weight; r->wposn = r->posn * r->weight; bs->insert(l); bs->insert(r); b->deleted=true; inactive.push_back(v); #ifdef RECTANGLE_OVERLAP_LOGGING f<<" new blocks: "<<*l<<" and "<<*r<<endl; #endif } } #ifdef RECTANGLE_OVERLAP_LOGGING f<<" finished splits."<<endl; #endif bs->cleanup(); } /** * Scan constraint list for the most violated constraint, or the first equality * constraint */ Constraint* IncSolver::mostViolated(ConstraintList &l) { double minSlack = DBL_MAX; Constraint* v=NULL; #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); f<<"Looking for most violated..."<<endl; #endif ConstraintList::iterator end = l.end(); ConstraintList::iterator deletePoint = end; for(ConstraintList::iterator i=l.begin();i!=end;++i) { Constraint *c=*i; double slack = c->slack(); if(c->equality || slack < minSlack) { minSlack=slack; v=c; deletePoint=i; if(c->equality) break; } } // Because the constraint list is not order dependent we just // move the last element over the deletePoint and resize // downwards. There is always at least 1 element in the // vector because of search. if(deletePoint != end && (minSlack<ZERO_UPPERBOUND||v->equality)) { *deletePoint = l[l.size()-1]; l.resize(l.size()-1); } #ifdef RECTANGLE_OVERLAP_LOGGING f<<" most violated is: "<<*v<<endl; #endif return v; } struct node { set<node*> in; set<node*> out; }; // useful in debugging - cycles would be BAD bool Solver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) { map<Variable*, node*> varmap; vector<node*> graph; for(unsigned i=0;i<n;i++) { node *u=new node; graph.push_back(u); varmap[vs[i]]=u; } for(unsigned i=0;i<n;i++) { for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) { Variable *l=(*c)->left; varmap[vs[i]]->in.insert(varmap[l]); } for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { Variable *r=(*c)->right; varmap[vs[i]]->out.insert(varmap[r]); } } while(graph.size()>0) { node *u=NULL; vector<node*>::iterator i=graph.begin(); for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; } } if(i==graph.end() && graph.size()>0) { //cycle found! return true; } else { graph.erase(i); for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } delete u; } } for(unsigned i=0; i<graph.size(); ++i) { delete graph[i]; } return false; } // useful in debugging - cycles would be BAD bool Solver::blockGraphIsCyclic() { map<Block*, node*> bmap; vector<node*> graph; for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; node *u=new node; graph.push_back(u); bmap[b]=u; } for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); Constraint *c=b->findMinInConstraint(); while(c!=NULL) { Block *l=c->left->block; bmap[b]->in.insert(bmap[l]); b->deleteMinInConstraint(); c=b->findMinInConstraint(); } b->setUpOutConstraints(); c=b->findMinOutConstraint(); while(c!=NULL) { Block *r=c->right->block; bmap[b]->out.insert(bmap[r]); b->deleteMinOutConstraint(); c=b->findMinOutConstraint(); } } while(graph.size()>0) { node *u=NULL; vector<node*>::iterator i=graph.begin(); for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; } } if(i==graph.end() && graph.size()>0) { //cycle found! return true; } else { graph.erase(i); for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } delete u; } } for(unsigned i=0; i<graph.size(); i++) { delete graph[i]; } return false; } }