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.cpp647
1 files changed, 0 insertions, 647 deletions
diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp
deleted file mode 100644
index a5e7ed0d1..000000000
--- a/src/libvpsc/block.cpp
+++ /dev/null
@@ -1,647 +0,0 @@
-/*
- * 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 <cassert>
-#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
-
-#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<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);
- }
-}
-
-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<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 (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 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;
- 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 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 LIBVPSC_LOGGING
- f<<" merged heap: "<<*in<<endl;
-#endif
-}
-void Block::mergeOut(Block *b) {
- findMinOutConstraint();
- b->findMinOutConstraint();
- out->merge(b->out);
-}
-Constraint *Block::findMinInConstraint() {
- 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 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 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 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=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;
-}
-void Block::deleteMinInConstraint() {
- in->deleteMin();
-#ifdef LIBVPSC_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<"deleteMinInConstraint... "<<endl;
- f<<" result: "<<*in<<endl;
-#endif
-}
-void Block::deleteMinOutConstraint() {
- out->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==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;
-}
-
-// The top level v and r are variables between which we want to find the
-// constraint with the smallest lm.
-// 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).
-// 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<<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);
-}
-*/
-
-// 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<<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);
-#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) {
- 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* 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,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 LIBVPSC_LOGGING
- ofstream f(LOGFILE,ios::app);
- f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
-#endif
- Constraint *c=findMinLMBetween(vl, vr);
-#ifdef LIBVPSC_LOGGING
- f<<" going to split on: "<<*c<<endl;
-#endif
- 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(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="<<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 14:43:30 +0000