/* * vim: ts=4 sw=4 et tw=0 wm=0 * * libvpsc - A solver for the problem of Variable Placement with * Separation Constraints. * * Copyright (C) 2005-2008 Monash University * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * See the file LICENSE.LGPL distributed with the library. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * Author(s): Tim Dwyer */ /* * @brief A block is a group of variables that must be moved together to improve * the goal function without violating already active constraints. * The variables in a block are spanned by a tree of active constraints. * */ #include "libvpsc/block.h" #include "libvpsc/variable.h" #include #include "libvpsc/pairing_heap.h" #include "libvpsc/constraint.h" #include "libvpsc/exceptions.h" #include "libvpsc/blocks.h" #ifdef LIBVPSC_LOGGING #include using std::ios; using std::ofstream; using std::endl; #endif #define __NOTNAN(p) (p)==(p) namespace vpsc { void PositionStats::addVariable(Variable* v) { double ai=scale/v->scale; double bi=v->offset/v->scale; double wi=v->weight; AB+=wi*ai*bi; AD+=wi*ai*v->desiredPosition; A2+=wi*ai*ai; /* #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" << v->desiredPosition << ", ai=" << ai << ", bi=" << bi << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2; #endif */ } void Block::addVariable(Variable* v) { v->block=this; vars->push_back(v); if(ps.A2==0) ps.scale=v->scale; //weight+= v->weight; //wposn += v->weight * (v->desiredPosition - v->offset); //posn=wposn/weight; ps.addVariable(v); posn=(ps.AD - ps.AB) / ps.A2; COLA_ASSERT(__NOTNAN(posn)); /* #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f << ", posn=" << posn << endl; #endif */ } Block::Block(Blocks *blocks, Variable* const v) : vars(new std::vector) , posn(0) //, weight(0) //, wposn(0) , deleted(false) , timeStamp(0) , in(nullptr) , out(nullptr) , blocks(blocks) { if(v!=nullptr) { v->offset=0; addVariable(v); } } void Block::updateWeightedPosition() { //wposn=0; ps.AB=ps.AD=ps.A2=0; for (Vit v=vars->begin();v!=vars->end();++v) { //wposn += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight; ps.addVariable(*v); } posn=(ps.AD - ps.AB) / ps.A2; COLA_ASSERT(__NOTNAN(posn)); #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f << ", posn=" << posn << endl; #endif } Block::~Block(void) { delete vars; delete in; delete out; } void Block::setUpInConstraints() { setUpConstraintHeap(in,true); } void Block::setUpOutConstraints() { setUpConstraintHeap(out,false); } void Block::setUpConstraintHeap(PairingHeap* &h,bool in) { delete h; h = new PairingHeap(); for (Vit i=vars->begin();i!=vars->end();++i) { Variable *v=*i; std::vector *cs=in?&(v->in):&(v->out); for (Cit j=cs->begin();j!=cs->end();++j) { Constraint *c=*j; c->timeStamp=blocks->blockTimeCtr; if ( ((c->left->block != this) && in) || ((c->right->block != this) && !in) ) { h->insert(c); } } } } Block* Block::merge(Block* b, Constraint* c) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" merging on: "<<*c<<",c->left->offset="<left->offset<<",c->right->offset="<right->offset<right->offset - c->left->offset - c->gap; Block *l=c->left->block; Block *r=c->right->block; if (l->vars->size() < r->vars->size()) { r->merge(l,c,dist); } else { l->merge(r,c,-dist); } Block* mergeBlock=b->deleted?this:b; #ifdef LIBVPSC_LOGGING f<<" merged block="<<*mergeBlock<id<<"]: d="<desiredPosition <<" a="<scale<<" o="<offset <findMinInConstraint(); in->merge(b->in); #ifdef LIBVPSC_LOGGING f<<" merged heap: "<<*in<findMinOutConstraint(); out->merge(b->out); } Constraint *Block::findMinInConstraint() { Constraint *v = nullptr; std::vector outOfDate; while (!in->isEmpty()) { v = in->findMin(); Block *lb=v->left->block; Block *rb=v->right->block; // rb may not be this if called between merge and mergeIn #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" checking constraint ... "<<*v; f<<" timestamps: left="<timeStamp<<" right="<timeStamp<<" constraint="<timeStamp<slack()<0) { f<<" violated internal constraint found! "<<*v<timeStamp < lb->timeStamp) { // block at other end of constraint has been moved since this in->deleteMin(); outOfDate.push_back(v); #ifdef LIBVPSC_LOGGING f<<" reinserting out of date (reinsert later)"<timeStamp=blocks->blockTimeCtr; in->insert(v); } if(in->isEmpty()) { v=nullptr; } else { v=in->findMin(); } return v; } Constraint *Block::findMinOutConstraint() { if(out->isEmpty()) return nullptr; Constraint *v = out->findMin(); while (v->left->block == v->right->block) { out->deleteMin(); if(out->isEmpty()) return nullptr; v = out->findMin(); } return v; } void Block::deleteMinInConstraint() { in->deleteMin(); #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<"deleteMinInConstraint... "<deleteMin(); } inline bool Block::canFollowLeft(Constraint const* c, Variable const* last) const { return c->left->block==this && c->active && last!=c->left; } inline bool Block::canFollowRight(Constraint const* c, Variable const* last) const { return c->right->block==this && c->active && last!=c->right; } // computes the derivative of v and the lagrange multipliers // of v's out constraints (as the recursive sum of those below. // Does not backtrack over u. // also records the constraint with minimum lagrange multiplier // in min_lm double Block::compute_dfdv(Variable* const v, Variable* const u, Constraint *&min_lm) { double dfdv=v->dfdv(); for(Cit it=v->out.begin();it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { c->lm=compute_dfdv(c->right,v,min_lm); dfdv+=c->lm*c->left->scale; if(!c->equality&&(min_lm==nullptr||c->lmlm)) min_lm=c; } } for(Cit it=v->in.begin();it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { c->lm=-compute_dfdv(c->left,v,min_lm); dfdv-=c->lm*c->right->scale; if(!c->equality&&(min_lm==nullptr||c->lmlm)) min_lm=c; } } return dfdv/v->scale; } double Block::compute_dfdv(Variable* const v, Variable* const u) { double dfdv = v->dfdv(); for(Cit it = v->out.begin(); it != v->out.end(); ++it) { Constraint *c = *it; if(canFollowRight(c,u)) { c->lm = compute_dfdv(c->right,v); dfdv += c->lm * c->left->scale; } } for(Cit it=v->in.begin();it!=v->in.end();++it) { Constraint *c = *it; if(canFollowLeft(c,u)) { c->lm = - compute_dfdv(c->left,v); dfdv -= c->lm * c->right->scale; } } return dfdv/v->scale; } // The top level v and r are variables between which we want to find the // constraint with the smallest lm. // Similarly, m is initially nullptr and is only assigned a value if the next // variable to be visited is r or if a possible min constraint is returned from // a nested call (rather than nullptr). // Then, the search for the m with minimum lm occurs as we return from // the recursion (checking only constraints traversed left-to-right // in order to avoid creating any new violations). // We also do not consider equality constraints as potential split points bool Block::split_path( Variable* r, Variable* const v, Variable* const u, Constraint* &m, bool desperation=false ) { for(Cit it(v->in.begin());it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" left split path: "<<*c<left==r) { if(desperation&&!c->equality) m=c; return true; } else { if(split_path(r,c->left,v,m)) { if(desperation && !c->equality && (!m||c->lmlm)) { m=c; } return true; } } } } for(Cit it(v->out.begin());it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" right split path: "<<*c<right==r) { if(!c->equality) m=c; return true; } else { if(split_path(r,c->right,v,m)) { if(!c->equality && (!m||c->lmlm)) m=c; return true; } } } } return false; } /* Block::Pair Block::compute_dfdv_between( Variable* r, Variable* const v, Variable* const u, const Direction dir = NONE, bool changedDirection = false) { double dfdv=v->weight*(v->position() - v->desiredPosition); Constraint *m=nullptr; for(Cit it(v->in.begin());it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { if(dir==RIGHT) { changedDirection = true; } if(c->left==r) { r=nullptr; if(!c->equality) m=c; } Pair p=compute_dfdv_between(r,c->left,v, LEFT,changedDirection); dfdv -= c->lm = -p.first; if(r && p.second) m = p.second; } } for(Cit it(v->out.begin());it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { if(dir==LEFT) { changedDirection = true; } if(c->right==r) { r=nullptr; if(!c->equality) m=c; } Pair p=compute_dfdv_between(r,c->right,v, RIGHT,changedDirection); dfdv += c->lm = p.first; if(r && p.second) m = changedDirection && !c->equality && c->lm < p.second->lm ? c : p.second; } } return Pair(dfdv,m); } */ // resets LMs for all active constraints to 0 by // traversing active constraint tree starting from v, // not back tracking over u void Block::reset_active_lm(Variable* const v, Variable* const u) { for(Cit it=v->out.begin();it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { c->lm=0; reset_active_lm(c->right,v); } } for(Cit it=v->in.begin();it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { c->lm=0; reset_active_lm(c->left,v); } } } void Block::list_active(Variable* const v, Variable* const u) { for(Cit it=v->out.begin();it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" "<<*c<right,v); } } for(Cit it=v->in.begin();it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" "<<*c<left,v); } } } /* * finds the constraint with the minimum lagrange multiplier, that is, the constraint * that most wants to split */ Constraint *Block::findMinLM() { Constraint *min_lm=nullptr; reset_active_lm(vars->front(),nullptr); compute_dfdv(vars->front(),nullptr,min_lm); #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" langrangians: "<front(),nullptr); #endif return min_lm; } Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) { reset_active_lm(vars->front(),nullptr); compute_dfdv(vars->front(),nullptr); Constraint *min_lm=nullptr; split_path(rv,lv,nullptr,min_lm); #if 0 if(min_lm==nullptr) { split_path(rv,lv,nullptr,min_lm,true); } #else if(min_lm==nullptr) { #ifdef LIBVPSC_DEBUG fprintf(stderr,"Couldn't find split point!\n"); #endif UnsatisfiableException e; getActivePathBetween(e.path,lv,rv,nullptr); throw e; } COLA_ASSERT(min_lm!=nullptr); #endif return min_lm; } // populates block b by traversing the active constraint tree adding variables as they're // visited. Starts from variable v and does not backtrack over variable u. void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) { b->addVariable(v); for (Cit c=v->in.begin();c!=v->in.end();++c) { if (canFollowLeft(*c,u)) populateSplitBlock(b, (*c)->left, v); } for (Cit c=v->out.begin();c!=v->out.end();++c) { if (canFollowRight(*c,u)) populateSplitBlock(b, (*c)->right, v); } } /* * Returns the active path between variables u and v... not back tracking over w */ bool Block::getActivePathBetween(Constraints& path, Variable const* u, Variable const* v, Variable const *w) const { if(u==v) return true; for (Cit_const c=u->in.begin();c!=u->in.end();++c) { if (canFollowLeft(*c,w)) { if(getActivePathBetween(path, (*c)->left, v, u)) { path.push_back(*c); return true; } } } for (Cit_const c=u->out.begin();c!=u->out.end();++c) { if (canFollowRight(*c,w)) { if(getActivePathBetween(path, (*c)->right, v, u)) { path.push_back(*c); return true; } } } return false; } // Search active constraint tree from u to see if there is a directed path to v. // Returns true if path is found with all constraints in path having their visited flag // set true. bool Block::isActiveDirectedPathBetween(Variable const* u, Variable const* v) const { if(u==v) return true; for (Cit_const c=u->out.begin();c!=u->out.end();++c) { if(canFollowRight(*c,nullptr)) { if(isActiveDirectedPathBetween((*c)->right,v)) { return true; } } } return false; } bool Block::getActiveDirectedPathBetween( Constraints& path, Variable const* u, Variable const* v) const { if(u==v) return true; for (Cit_const c=u->out.begin();c!=u->out.end();++c) { if(canFollowRight(*c,nullptr)) { if(getActiveDirectedPathBetween(path,(*c)->right,v)) { path.push_back(*c); return true; } } } return false; } /* * Block needs to be split because of a violated constraint between vl and vr. * We need to search the active constraint tree between l and r and find the constraint * with min lagrangrian multiplier and split at that point. * Returns the split constraint */ Constraint* Block::splitBetween(Variable* const vl, Variable* const vr, Block* &lb, Block* &rb) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" need to split between: "<<*vl<<" and "<<*vr<active=false; l=new Block(blocks); populateSplitBlock(l,c->left,c->right); //COLA_ASSERT(l->weight>0); r=new Block(blocks); populateSplitBlock(r,c->right,c->left); //COLA_ASSERT(r->weight>0); } /* * Computes the cost (squared euclidean distance from desired positions) of the * current positions for variables in this block */ double Block::cost() { double c = 0; for (Vit v=vars->begin();v!=vars->end();++v) { double diff = (*v)->position() - (*v)->desiredPosition; c += (*v)->weight * diff * diff; } return c; } std::ostream& operator <<(std::ostream &os, const Block& b) { os<<"Block(posn="<begin();v!=b.vars->end();++v) { os<<" "<<**v; } if(b.deleted) { os<<" Deleted!"; } return os; } }