solve_VPSC.cpp

Go to the documentation of this file.

 
#include "config.h"
 
#include <cassert>
#include <vpsc/constraint.h>
#include <vpsc/block.h>
#include <vpsc/blocks.h>
#include <vpsc/solve_VPSC.h>
#include <math.h>
#include <memory>
#include <sstream>
#include <fstream>
#include <stdexcept>
using std::ios;
using std::ofstream;
 
using std::ostringstream;
using std::list;
using std::set;
 
#ifndef RECTANGLE_OVERLAP_LOGGING
        #define RECTANGLE_OVERLAP_LOGGING 0
#endif
 
IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m_,
                 Constraint *cs_[])
    : VPSC(n, vs, m_, cs_) {
        inactive.assign(cs_, cs_ + m_);
        for(Constraint *c : inactive) {
                c->active=false;
        }
}
 
VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m_,
           Constraint *cs_[])
  : bs(n, vs), cs(cs_), m(m_) {
        if (RECTANGLE_OVERLAP_LOGGING) {
                printBlocks();
                assert(!constraintGraphIsCyclic(n,vs));
        }
}
 
// useful in debugging
void VPSC::printBlocks() {
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                for(Block *b : bs) {
                        f<<"  "<<*b<<"\n";
                }
                for(unsigned i=0;i<m;i++) {
                        f<<"  "<<*cs[i]<<"\n";
                }
        }
}
void VPSC::satisfy() {
        list<Variable*> vs=bs.totalOrder();
        for(Variable *v : vs) {
                if(!v->block->deleted) {
                        bs.mergeLeft(v->block);
                }
        }
        bs.cleanup();
        for(unsigned i=0;i<m;i++) {
                if(cs[i]->slack()<-0.0000001) {
                        if (RECTANGLE_OVERLAP_LOGGING) {
                                ofstream f(LOGFILE,ios::app);
                                f<<"Error: Unsatisfied constraint: "<<*cs[i]<<"\n";
                        }
                        //assert(cs[i]->slack()>-0.0000001);
                        throw std::runtime_error("Unsatisfied constraint");
                }
        }
}
 
void VPSC::refine() {
        for (bool solved = false; !solved;) {
                solved=true;
                for(Block *b : bs) {
                        b->setUpInConstraints();
                        b->setUpOutConstraints();
                }
                for(Block *b : bs) {
                        Constraint *c=b->findMinLM();
                        if(c!=nullptr && c->lm<0) {
                                if (RECTANGLE_OVERLAP_LOGGING) {
                                        ofstream f(LOGFILE,ios::app);
                                        f<<"Split on constraint: "<<*c<<"\n";
                                }
                                // Split on c
                                Block *l=nullptr, *r=nullptr;
                                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()<-0.0000001) {
                        assert(cs[i]->slack()>-0.0000001);
                        throw std::runtime_error("Unsatisfied constraint");
                }
        }
}
void VPSC::solve() {
        satisfy();
        refine();
}
 
void IncVPSC::solve() {
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"solve_inc()...\n";
        }
        double lastcost,cost = bs.cost();
        do {
                lastcost=cost;
                satisfy();
                splitBlocks();
                cost = bs.cost();
                if (RECTANGLE_OVERLAP_LOGGING) {
                        ofstream f(LOGFILE,ios::app);
                        f<<"  cost="<<cost<<"\n";
                }
        } while(fabs(lastcost-cost)>0.0001);
}
void IncVPSC::satisfy() {
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"satisfy_inc()...\n";
        }
        splitBlocks();
        long splitCtr = 0;
        Constraint* v = nullptr;
        while(mostViolated(inactive,v)<-0.0000001) {
                assert(!v->active);
                Block *lb = v->left->block, *rb = v->right->block;
                if(lb != rb) {
                        lb->merge(rb,v);
                } else {
                        if(splitCtr++>10000) {
                                throw std::runtime_error("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);
                }
        }
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  finished merges.\n";
        }
        bs.cleanup();
        for(unsigned i=0;i<m;i++) {
                v=cs[i];
                if(v->slack()<-0.0000001) {
                        //assert(cs[i]->slack()>-0.0000001);
                        ostringstream s;
                        s<<"Unsatisfied constraint: "<<*v;
                        throw std::runtime_error(s.str());
                }
        }
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  finished cleanup.\n";
                printBlocks();
        }
}
void IncVPSC::moveBlocks() {
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"moveBlocks()...\n";
        }
        for(Block *b : bs) {
                b->wposn = b->desiredWeightedPosition();
                b->posn = b->wposn / b->weight;
        }
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  moved blocks.\n";
        }
}
void IncVPSC::splitBlocks() {
        moveBlocks();
        // Split each block if necessary on min LM
        for(Block *b : bs) {
                Constraint* v=b->findMinLM();
                if(v!=nullptr && v->lm < -0.0000001) {
                        if (RECTANGLE_OVERLAP_LOGGING) {
                                ofstream f(LOGFILE,ios::app);
                                f<<"    found split point: "<<*v<<" lm="<<v->lm<<"\n";
                        }
                        Block *b2 = v->left->block, *l=nullptr, *r=nullptr;
                        assert(v->left->block == v->right->block);
                        double pos = b2->posn;
                        b2->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);
                        b2->deleted=true;
                        inactive.push_back(v);
                        if (RECTANGLE_OVERLAP_LOGGING) {
                                ofstream f(LOGFILE,ios::app);
                                f<<"  new blocks: "<<*l<<" and "<<*r<<"\n";
                        }
                }
        }
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  finished splits.\n";
        }
        bs.cleanup();
}
 
double IncVPSC::mostViolated(ConstraintList &l, Constraint* &v) {
        double minSlack = DBL_MAX;
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"Looking for most violated...\n";
        }
        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 (slack < minSlack) {
                        minSlack=slack; 
                        v=c;
                        deletePoint=i;
                }
        }
        // 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<-0.0000001) {
                *deletePoint = l.back();
                l.pop_back();
        }
        if (RECTANGLE_OVERLAP_LOGGING) {
                ofstream f(LOGFILE,ios::app);
                f<<"  most violated is: "<<*v<<"\n";
        }
        return minSlack;
}
 
#include <map>
using std::map;
using std::vector;
struct node {
        set<node*> in;
        set<node*> out;
};
// useful in debugging - cycles would be BAD
bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
        map<Variable*, node*> varmap;
        vector<std::unique_ptr<node>> graph;
        for(unsigned i=0;i<n;i++) {
                graph.emplace_back(new node);
                varmap[vs[i]]=graph.back().get();
        }
        for(unsigned i=0;i<n;i++) {
                for(Constraint *c : vs[i]->in) {
                        Variable *l=c->left;
                        varmap[vs[i]]->in.insert(varmap[l]);
                }
 
                for(Constraint *c : vs[i]->out) {
                        Variable *r=c->right;
                        varmap[vs[i]]->out.insert(varmap[r]);
                }
        }
        while(!graph.empty()) {
                node *u=nullptr;
                vector<std::unique_ptr<node>>::iterator i=graph.begin();
                for(;i!=graph.end();i++) {
                        u=(*i).get();
                        if(u->in.empty()) {
                                break;
                        }
                }
                if(i==graph.end()) {
                        //cycle found!
                        return true;
                } else {
                        graph.erase(i);
                        for(node *v : u->out) {
                                v->in.erase(u);
                        }
                }
        }
        return false;
}
 
// useful in debugging - cycles would be BAD
bool VPSC::blockGraphIsCyclic() {
        map<Block*, node*> bmap;
        vector<std::unique_ptr<node>> graph;
        for(Block *b : bs) {
                graph.emplace_back(new node);
                bmap[b]=graph.back().get();
        }
        for(Block *b : bs) {
                b->setUpInConstraints();
                Constraint *c=b->findMinInConstraint();
                while(c!=nullptr) {
                        Block *l=c->left->block;
                        bmap[b]->in.insert(bmap[l]);
                        b->deleteMinInConstraint();
                        c=b->findMinInConstraint();
                }
 
                b->setUpOutConstraints();
                c=b->findMinOutConstraint();
                while(c!=nullptr) {
                        Block *r=c->right->block;
                        bmap[b]->out.insert(bmap[r]);
                        b->deleteMinOutConstraint();
                        c=b->findMinOutConstraint();
                }
        }
        while(!graph.empty()) {
                node *u=nullptr;
                vector<std::unique_ptr<node>>::iterator i=graph.begin();
                for(;i!=graph.end();i++) {
                        u=(*i).get();
                        if(u->in.empty()) {
                                break;
                        }
                }
                if(i==graph.end()) {
                        //cycle found!
                        return true;
                }
                graph.erase(i);
                for(node *v : u->out) {
                        v->in.erase(u);
                }
        }
        return false;
}