summaryrefslogtreecommitdiffstats
path: root/src/libvpsc/block.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/libvpsc/block.cpp')
-rw-r--r--src/libvpsc/block.cpp845
1 files changed, 548 insertions, 297 deletions
diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp
index 8171780d4..a5e7ed0d1 100644
--- a/src/libvpsc/block.cpp
+++ b/src/libvpsc/block.cpp
@@ -1,208 +1,292 @@
/*
- * Authors:
- * Tim Dwyer <tgdwyer@gmail.com>
+ * vim: ts=4 sw=4 et tw=0 wm=0
*
- * Copyright (C) 2005 Authors
+ * 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.
*
- * Released under GNU LGPL. Read the file 'COPYING' for more information.
*/
+
+#include "libvpsc/block.h"
+#include "libvpsc/variable.h"
#include <cassert>
-#include "pairingheap/PairingHeap.h"
-#include "constraint.h"
-#include "block.h"
-#include "blocks.h"
-#ifdef RECTANGLE_OVERLAP_LOGGING
+#include "libvpsc/pairing_heap.h"
+#include "libvpsc/constraint.h"
+#include "libvpsc/exceptions.h"
+#include "libvpsc/blocks.h"
+
+#ifdef LIBVPSC_LOGGING
#include <fstream>
using std::ios;
using std::ofstream;
using std::endl;
#endif
-using std::vector;
+
+#define __NOTNAN(p) (p)==(p)
namespace vpsc {
-void Block::addVariable(Variable* const v) {
- v->block=this;
- vars->push_back(v);
- weight+=v->weight;
- wposn += v->weight * (v->desiredPosition - v->offset);
- posn=wposn/weight;
-}
-Block::Block(Variable* const v) {
- timeStamp=0;
- posn=weight=wposn=0;
- in=NULL;
- out=NULL;
- deleted=false;
- vars=new vector<Variable*>;
- if(v!=NULL) {
- v->offset=0;
- addVariable(v);
- }
+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<Variable*>)
+ , posn(0)
+ //, weight(0)
+ //, wposn(0)
+ , deleted(false)
+ , timeStamp(0)
+ , in(NULL)
+ , out(NULL)
+ , blocks(blocks)
+{
+ if(v!=NULL) {
+ v->offset=0;
+ addVariable(v);
+ }
}
-double Block::desiredWeightedPosition() {
- double wp = 0;
- for (Vit v=vars->begin();v!=vars->end();++v) {
- wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
- }
- return wp;
+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;
+ delete vars;
+ delete in;
+ delete out;
}
void Block::setUpInConstraints() {
- setUpConstraintHeap(in,true);
+ setUpConstraintHeap(in,true);
}
void Block::setUpOutConstraints() {
- setUpConstraintHeap(out,false);
-}
-void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
- delete h;
- h = new PairingHeap<Constraint*>(&compareConstraints);
- for (Vit i=vars->begin();i!=vars->end();++i) {
- Variable *v=*i;
- vector<Constraint*> *cs=in?&(v->in):&(v->out);
- for (Cit j=cs->begin();j!=cs->end();++j) {
- Constraint *c=*j;
- c->timeStamp=blockTimeCtr;
- if ((c->left->block != this && in) || (c->right->block != this && !in)) {
- h->insert(c);
- }
- }
- }
-}
-void Block::merge(Block* b, Constraint* c) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
+ setUpConstraintHeap(out,false);
+}
+void Block::setUpConstraintHeap(PairingHeap<Constraint*,CompareConstraints>* &h,bool in) {
+ delete h;
+ h = new PairingHeap<Constraint*,CompareConstraints>();
+ for (Vit i=vars->begin();i!=vars->end();++i) {
+ Variable *v=*i;
+ std::vector<Constraint*> *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="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
#endif
- double dist = c->right->offset - c->left->offset - c->gap;
- Block *l=c->left->block;
- Block *r=c->right->block;
- if (vars->size() < b->vars->size()) {
- r->merge(l,c,dist);
- } else {
- l->merge(r,c,-dist);
- }
-#ifdef RECTANGLE_OVERLAP_LOGGING
- f<<" merged block="<<(b->deleted?*this:*b)<<endl;
+ double dist = c->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<<endl;
#endif
+ return mergeBlock;
}
-
+/*
+ * Merges b into this block across c. Can be either a
+ * right merge or a left merge
+ * @param b block to merge into this
+ * @param c constraint being merged
+ * @param distance separation required to satisfy c
+ */
void Block::merge(Block *b, Constraint *c, double dist) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" merging: "<<*b<<"dist="<<dist<<endl;
+#ifdef LIBVPSC_LOGGING
+ ofstream f(LOGFILE,ios::app);
+ f<<" merging: "<<*b<<"dist="<<dist<<endl;
#endif
- c->active=true;
- wposn+=b->wposn-dist*b->weight;
- weight+=b->weight;
- posn=wposn/weight;
- for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
- Variable *v=*i;
- v->block=this;
- v->offset+=dist;
- vars->push_back(v);
- }
- b->deleted=true;
+ c->active=true;
+ //wposn+=b->wposn-dist*b->weight;
+ //weight+=b->weight;
+ for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
+ Variable *v=*i;
+ //v->block=this;
+ //vars->push_back(v);
+ v->offset+=dist;
+ addVariable(v);
+ }
+#ifdef LIBVPSC_LOGGING
+ for(Vit i=vars->begin();i!=vars->end();++i) {
+ Variable *v=*i;
+ f<<" v["<<v->id<<"]: d="<<v->desiredPosition
+ <<" a="<<v->scale<<" o="<<v->offset
+ <<endl;
+ }
+ f<<" AD="<<ps.AD<<" AB="<<ps.AB<<" A2="<<ps.A2<<endl;
+#endif
+ //posn=wposn/weight;
+ //COLA_ASSERT(wposn==ps.AD - ps.AB);
+ posn=(ps.AD - ps.AB) / ps.A2;
+ COLA_ASSERT(__NOTNAN(posn));
+ b->deleted=true;
}
void Block::mergeIn(Block *b) {
-#ifdef RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" merging constraint heaps... "<<endl;
+#ifdef LIBVPSC_LOGGING
+ ofstream f(LOGFILE,ios::app);
+ f<<" merging constraint heaps... "<<endl;
#endif
- // We check the top of the heaps to remove possible internal constraints
- findMinInConstraint();
- b->findMinInConstraint();
- in->merge(b->in);
-#ifdef RECTANGLE_OVERLAP_LOGGING
- f<<" merged heap: "<<*in<<endl;
+ // We check the top of the heaps to remove possible internal constraints
+ findMinInConstraint();
+ b->findMinInConstraint();
+ in->merge(b->in);
+#ifdef LIBVPSC_LOGGING
+ f<<" merged heap: "<<*in<<endl;
#endif
}
-void Block::mergeOut(Block *b) {
- findMinOutConstraint();
- b->findMinOutConstraint();
- out->merge(b->out);
+void Block::mergeOut(Block *b) {
+ findMinOutConstraint();
+ b->findMinOutConstraint();
+ out->merge(b->out);
}
Constraint *Block::findMinInConstraint() {
- Constraint *v = NULL;
- vector<Constraint*> 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 RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" checking constraint ... "<<*v;
- f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
+ Constraint *v = NULL;
+ std::vector<Constraint*> 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="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
#endif
- if(lb == rb) {
- // constraint has been merged into the same block
-#ifdef RECTANGLE_OVERLAP_LOGGING
- if(v->slack()<0) {
- f<<" violated internal constraint found! "<<*v<<endl;
- f<<" lb="<<*lb<<endl;
- f<<" rb="<<*rb<<endl;
- }
+ if(lb == rb) {
+ // constraint has been merged into the same block
+#ifdef LIBVPSC_LOGGING
+ if(v->slack()<0) {
+ f<<" violated internal constraint found! "<<*v<<endl;
+ f<<" lb="<<*lb<<endl;
+ f<<" rb="<<*rb<<endl;
+ }
#endif
- in->deleteMin();
-#ifdef RECTANGLE_OVERLAP_LOGGING
- f<<" ... skipping internal constraint"<<endl;
+ in->deleteMin();
+#ifdef LIBVPSC_LOGGING
+ f<<" ... skipping internal constraint"<<endl;
#endif
- } else if(v->timeStamp < lb->timeStamp) {
- // block at other end of constraint has been moved since this
- in->deleteMin();
- outOfDate.push_back(v);
-#ifdef RECTANGLE_OVERLAP_LOGGING
- f<<" reinserting out of date (reinsert later)"<<endl;
+ } else if(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)"<<endl;
#endif
- } else {
- break;
- }
- }
- for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
- v=*i;
- v->timeStamp=blockTimeCtr;
- in->insert(v);
- }
- if(in->isEmpty()) {
- v=NULL;
- } else {
- v=in->findMin();
- }
- return v;
+ } else {
+ break;
+ }
+ }
+ for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
+ v=*i;
+ v->timeStamp=blocks->blockTimeCtr;
+ in->insert(v);
+ }
+ if(in->isEmpty()) {
+ v=NULL;
+ } else {
+ v=in->findMin();
+ }
+ return v;
}
Constraint *Block::findMinOutConstraint() {
- if(out->isEmpty()) return NULL;
- Constraint *v = out->findMin();
- while (v->left->block == v->right->block) {
- out->deleteMin();
- if(out->isEmpty()) return NULL;
- v = out->findMin();
- }
- return v;
+ if(out->isEmpty()) return NULL;
+ Constraint *v = out->findMin();
+ while (v->left->block == v->right->block) {
+ out->deleteMin();
+ if(out->isEmpty()) return NULL;
+ v = out->findMin();
+ }
+ return v;
}
void Block::deleteMinInConstraint() {
- in->deleteMin();
-#ifdef RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<"deleteMinInConstraint... "<<endl;
- f<<" result: "<<*in<<endl;
+ in->deleteMin();
+#ifdef LIBVPSC_LOGGING
+ ofstream f(LOGFILE,ios::app);
+ f<<"deleteMinInConstraint... "<<endl;
+ f<<" result: "<<*in<<endl;
#endif
}
void Block::deleteMinOutConstraint() {
- out->deleteMin();
+ out->deleteMin();
}
-inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) {
- return c->left->block==this && c->active && last!=c->left;
+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 *c, const Variable* const last) {
- return c->right->block==this && c->active && last!=c->right;
+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
@@ -211,32 +295,47 @@ inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
// 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->weight*(v->position() - v->desiredPosition);
- for(Cit it=v->out.begin();it!=v->out.end();++it) {
- Constraint *c=*it;
- if(canFollowRight(c,u)) {
- dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
- if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
- }
- }
- for(Cit it=v->in.begin();it!=v->in.end();++it) {
- Constraint *c=*it;
- if(canFollowLeft(c,u)) {
- dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
- if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
- }
- }
- return dfdv;
+ 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==NULL||c->lm<min_lm->lm)) 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==NULL||c->lm<min_lm->lm)) 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;
}
-
-// computes dfdv for each variable and uses the sum of dfdv on either side of
-// the constraint c to compute the lagrangian multiplier lm_c.
// The top level v and r are variables between which we want to find the
// constraint with the smallest lm.
-// When we find r we pass NULL to subsequent recursive calls,
-// thus r=NULL indicates constraints are not on the shortest path.
// Similarly, m is initially NULL 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 NULL).
@@ -244,153 +343,305 @@ double Block::compute_dfdv(Variable* const v, Variable* const u,
// 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<<endl;
+#endif
+ if(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->lm<m->lm)) {
+ 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<<endl;
+#endif
+ if(c->right==r) {
+ if(!c->equality) m=c;
+ return true;
+ } else {
+ if(split_path(r,c->right,v,m)) {
+ if(!c->equality && (!m||c->lm<m->lm))
+ 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=NULL;
- 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=NULL;
- 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=NULL;
- 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);
+ 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=NULL;
+ 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=NULL;
+ 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=NULL;
+ 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);
- }
- }
+ 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<<endl;
+#endif
+ list_active(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<<endl;
+#endif
+ list_active(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=NULL;
- reset_active_lm(vars->front(),NULL);
- compute_dfdv(vars->front(),NULL,min_lm);
- return min_lm;
+ Constraint *min_lm=NULL;
+ reset_active_lm(vars->front(),NULL);
+ compute_dfdv(vars->front(),NULL,min_lm);
+#ifdef LIBVPSC_LOGGING
+ ofstream f(LOGFILE,ios::app);
+ f<<" langrangians: "<<endl;
+ list_active(vars->front(),NULL);
+#endif
+ return min_lm;
}
Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) {
- Constraint *min_lm=NULL;
- reset_active_lm(vars->front(),NULL);
- min_lm=compute_dfdv_between(rv,lv,NULL).second;
- return min_lm;
+ reset_active_lm(vars->front(),NULL);
+ compute_dfdv(vars->front(),NULL);
+ Constraint *min_lm=NULL;
+ split_path(rv,lv,NULL,min_lm);
+#if 0
+ if(min_lm==NULL) {
+ split_path(rv,lv,NULL,min_lm,true);
+ }
+#else
+ if(min_lm==NULL) {
+#ifdef LIBVPSC_DEBUG
+ fprintf(stderr,"Couldn't find split point!\n");
+#endif
+ UnsatisfiableException e;
+ getActivePathBetween(e.path,lv,rv,NULL);
+ throw e;
+ }
+ COLA_ASSERT(min_lm!=NULL);
+#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* const 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);
- }
+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* u, Variable *v) {
- if(u==v) return true;
- for (Cit c=u->out.begin();c!=u->out.end();++c) {
- if(canFollowRight(*c,NULL)) {
- if(isActiveDirectedPathBetween((*c)->right,v)) {
- (*c)->visited=true;
- return true;
- }
- (*c)->visited=false;
- }
- }
- return false;
+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,NULL)) {
+ 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,NULL)) {
+ 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 RECTANGLE_OVERLAP_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
+ Block* &lb, Block* &rb) {
+#ifdef LIBVPSC_LOGGING
+ ofstream f(LOGFILE,ios::app);
+ f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
#endif
- Constraint *c=findMinLMBetween(vl, vr);
-#ifdef RECTANGLE_OVERLAP_LOGGING
- f<<" going to split on: "<<*c<<endl;
+ Constraint *c=findMinLMBetween(vl, vr);
+#ifdef LIBVPSC_LOGGING
+ f<<" going to split on: "<<*c<<endl;
#endif
- split(lb,rb,c);
- deleted = true;
- return c;
+ if(c!=NULL) {
+ split(lb,rb,c);
+ deleted = true;
+ }
+ return c;
}
+/*
+ * Creates two new blocks, l and r, and splits this block across constraint c,
+ * placing the left subtree of constraints (and associated variables) into l
+ * and the right into r.
+ */
void Block::split(Block* &l, Block* &r, Constraint* c) {
- c->active=false;
- l=new Block();
- populateSplitBlock(l,c->left,c->right);
- r=new Block();
- populateSplitBlock(r,c->right,c->left);
+ c->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;
-}
-ostream& operator <<(ostream &os, const Block& b)
+ 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:";
- for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
- os<<" "<<**v;
- }
- if(b.deleted) {
- os<<" Deleted!";
- }
+ os<<"Block(posn="<<b.posn<<"):";
+ for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
+ os<<" "<<**v;
+ }
+ if(b.deleted) {
+ os<<" Deleted!";
+ }
return os;
}
+
}
+
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 08:07:09 +0000