e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * vim: ts=4 sw=4 et tw=0 wm=0
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * libavoid - Fast, Incremental, Object-avoiding Line Router
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Copyright (C) 2005-2009 Monash University
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * This library is free software; you can redistribute it and/or
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * modify it under the terms of the GNU Lesser General Public
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * License as published by the Free Software Foundation; either
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * version 2.1 of the License, or (at your option) any later version.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * See the file LICENSE.LGPL distributed with the library.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Licensees holding a valid commercial license may use this file in
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz * accordance with the commercial license agreement provided with the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * This library is distributed in the hope that it will be useful,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * but WITHOUT ANY WARRANTY; without even the implied warranty of
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Author(s): Tim Dwyer <Tim.Dwyer@csse.monash.edu.au>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * --------------
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * This file contains a slightly modified version of Solver() from libvpsc:
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * A solver for the problem of Variable Placement with Separation Constraints.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * It has the following changes from the Adaptagrams VPSC version:
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * - The required VPSC code has been consolidated into a single file.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * - Unnecessary code (like Solver) has been removed.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * - The PairingHeap code has been replaced by a STL priority_queue.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Modifications: Michael Wybrow <mjwybrow@users.sourceforge.net>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanusing namespace std;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const double ZERO_UPPERBOUND=-1e-10;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const double LAGRANGIAN_TOLERANCE=-1e-4;
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. CruzIncSolver::IncSolver(vector<Variable*> const &vs, vector<Constraint *> const &cs)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<n;++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<m;++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //COLA_ASSERT(!constraintGraphIsCyclic(n,vs));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Constraints::iterator i=inactive.begin();i!=inactive.end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// useful in debugging
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<m;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Stores the relative positions of the variables in their finalPosition
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Variables::const_iterator i=vs.begin();i!=vs.end();++i) {
65ed89c52f57ac8f74d6005fc61edaa589c200ccKris COLA_ASSERT(v->finalPosition==v->finalPosition);/// TODO: check! Possibly some error in this line...
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// useful in debugging - cycles would be BAD
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool IncSolver::constraintGraphIsCyclic(const unsigned n, Variable* const vs[]) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<n;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<n;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(vector<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //cycle found!
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// useful in debugging - cycles would be BAD
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //cycle found!
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double lastcost = DBL_MAX, cost = bs->cost();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" bs->size="<<bs->size()<<", cost="<<cost<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * incremental version of satisfy that allows refinement after blocks are
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * - move blocks to new positions
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * - repeatedly merge across most violated constraint until no more
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * violated constraints exist
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Note: there is a special case to handle when the most violated constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * is between two variables in the same block. Then, we must split the block
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz * over an active constraint between the two variables. We choose the
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz * constraint with the most negative lagrangian multiplier.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //long splitCtr = 0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //CBuffer buffer(inactive);
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz && (v->equality || ((v->slack() < ZERO_UPPERBOUND) && !v->active)))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Block *lb = v->left->block, *rb = v->right->block;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(lb->isActiveDirectedPathBetween(v->right,v->left)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // cycle found, relax the violated, cyclic constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //UnsatisfiableException e;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //lb->getActiveDirectedPathBetween(e.path,v->right,v->left);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //e.path.push_back(v);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //if(splitCtr++>10000) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //throw "Cycle Error!";
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // constraint is within block, need to split first
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan =lb->splitBetween(v->left,v->right,lb,rb);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan std::cerr << "Unsatisfiable:" << std::endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(std::vector<Constraint*>::iterator r=e.path.begin();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // v was satisfied by the above split!
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<"...remaining blocks="<<bs->size()<<", cost="<<bs->cost()<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(unsigned i=0;i<m;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan s<<"Unsatisfied constraint: "<<*v;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //b->posn = b->wposn / b->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // Split each block if necessary on min LM
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::const_iterator i(bs->begin());i!=bs->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(v!=NULL && v->lm < LAGRANGIAN_TOLERANCE) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" found split point: "<<*v<<" lm="<<v->lm<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Block *b = v->left->block, *l=NULL, *r=NULL;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan COLA_ASSERT(v->left->block == v->right->block);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //double pos = b->posn;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //l->posn=r->posn=pos;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //l->wposn = l->posn * l->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //r->wposn = r->posn * r->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" new blocks: "<<*l<<" and "<<*r<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //if(splitCnt>0) { std::cout<<" splits: "<<splitCnt<<endl; }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Scan constraint list for the most violated constraint, or the first equality
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanConstraint* IncSolver::mostViolated(Constraints &l) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Constraints::iterator i=l.begin();i!=end;++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // Because the constraint list is not order dependent we just
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // move the last element over the deletePoint and resize
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // downwards. There is always at least 1 element in the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // vector because of search.
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // TODO check this logic and add parens:
b2296609507c2d79d585f1076b058730a6ec9239Campbell Barton if((deletePoint != end) && (((minSlack < ZERO_UPPERBOUND) && !v->active) || v->equality)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanBlocks::Blocks(vector<Variable*> const &vs) : vs(vs),nvs(vs.size()) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(int i=0;i<nvs;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::iterator i=begin();i!=end();++i) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz * returns a list of variables with total ordering determined by the constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan list<Variable*> *order = new list<Variable*>;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(int i=0;i<nvs;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(int i=0;i<nvs;i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Recursive depth first search giving total order by pushing nodes in the DAG
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// onto the front of the list when we finish searching them
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan vector<Constraint*>::iterator it=v->out.begin();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Processes incoming constraints, most violated to least, merging with the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * neighbouring (left) block until no more violated constraints are found
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double dist = c->right->offset - c->left->offset - c->gap;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Symmetrical to mergeLeft
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraint *c = l->findMinOutConstraint();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<"mergeRight on constraint: "<<*c<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double dist = c->left->offset + c->gap - c->right->offset;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //erase(doomed);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Splits block b across constraint c into two new blocks, l and r (c's left
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * and right sides respectively)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //COLA_ASSERT(r->weight!=0);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //r->wposn = r->posn * r->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // r may have been merged!
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //r->posn = r->wposn / r->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * returns the cost total squared distance of variables from their desired
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(set<Block*>::iterator i=begin();i!=end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid PositionStats::addVariable(Variable* v) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#ifdef LIBVPSC_LOGGING
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan ofstream f(LOGFILE,ios::app);
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz f << "adding v[" << v->id << "], blockscale=" << scale << ", despos="
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan << v->desiredPosition << ", ai=" << ai << ", bi=" << bi
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //weight+= v->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //wposn += v->weight * (v->desiredPosition - v->offset);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#ifdef LIBVPSC_LOGGING
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan ofstream f(LOGFILE,ios::app);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f << ", posn=" << posn << endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Vit v=vars->begin();v!=vars->end();++v) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //wposn += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::setUpConstraintHeap(Heap* &h,bool in) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Vit i=vars->begin();i!=vars->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan vector<Constraint*> *cs=in?&(v->in):&(v->out);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit j=cs->begin();j!=cs->end();++j) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if (((c->left->block != this) && in) || ((c->right->block != this) && !in)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanBlock* Block::merge(Block* b, Constraint* c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double dist = c->right->offset - c->left->offset - c->gap;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Merges b into this block across c. Can be either a
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * right merge or a left merge
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * @param b block to merge into this
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * @param c constraint being merged
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * @param distance separation required to satisfy c
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::merge(Block *b, Constraint *c, double dist) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //wposn+=b->wposn-dist*b->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //weight+=b->weight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //v->block=this;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //vars->push_back(v);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Vit i=vars->begin();i!=vars->end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" v["<<v->id<<"]: d="<<v->desiredPosition
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" AD="<<ps.AD<<" AB="<<ps.AB<<" A2="<<ps.A2<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //COLA_ASSERT(wposn==ps.AD - ps.AB);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // We check the top of the heaps to remove possible internal constraints
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // rb may not be this if called between merge and mergeIn
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" checking constraint ... "<<*v;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // constraint has been merged into the same block
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" violated internal constraint found! "<<*v<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" ... skipping internal constraint"<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // block at other end of constraint has been moved since this
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" reinserting out of date (reinsert later)"<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanConstraint *Block::findMinOutConstraint() {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan while (v->left->block == v->right->block) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracaninline bool Block::canFollowLeft(Constraint const* c, Variable const* last) const {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan return c->left->block==this && c->active && last!=c->left;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracaninline bool Block::canFollowRight(Constraint const* c, Variable const* last) const {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan return c->right->block==this && c->active && last!=c->right;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// computes the derivative of v and the lagrange multipliers
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// of v's out constraints (as the recursive sum of those below.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Does not backtrack over u.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// also records the constraint with minimum lagrange multiplier
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracandouble Block::compute_dfdv(Variable* const v, Variable* const u,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->out.begin();it!=v->out.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->in.begin();it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracandouble Block::compute_dfdv(Variable* const v, Variable* const u) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it = v->out.begin(); it != v->out.end(); ++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->in.begin();it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// The top level v and r are variables between which we want to find the
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz// constraint with the smallest lm.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Similarly, m is initially NULL and is only assigned a value if the next
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// variable to be visited is r or if a possible min constraint is returned from
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// a nested call (rather than NULL).
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Then, the search for the m with minimum lm occurs as we return from
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz// the recursion (checking only constraints traversed left-to-right
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// in order to avoid creating any new violations).
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// We also do not consider equality constraints as potential split points
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it(v->in.begin());it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(desperation && !c->equality && (!m||c->lm<m->lm)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it(v->out.begin());it!=v->out.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanBlock::Pair Block::compute_dfdv_between(
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz Variable* r, Variable* const v, Variable* const u,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan const Direction dir = NONE, bool changedDirection = false) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double dfdv=v->weight*(v->position() - v->desiredPosition);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraint *m=NULL;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it(v->in.begin());it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraint *c=*it;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(canFollowLeft(c,u)) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(dir==RIGHT) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz changedDirection = true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(c->left==r) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(!c->equality) m=c;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Pair p=compute_dfdv_between(r,c->left,v,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan LEFT,changedDirection);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan dfdv -= c->lm = -p.first;
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(r && p.second)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it(v->out.begin());it!=v->out.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraint *c=*it;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(canFollowRight(c,u)) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(dir==LEFT) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz changedDirection = true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(c->right==r) {
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(!c->equality) m=c;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Pair p=compute_dfdv_between(r,c->right,v,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan RIGHT,changedDirection);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan dfdv += c->lm = p.first;
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if(r && p.second)
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz m = changedDirection && !c->equality && c->lm < p.second->lm
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan return Pair(dfdv,m);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// resets LMs for all active constraints to 0 by
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// traversing active constraint tree starting from v,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// not back tracking over u
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::reset_active_lm(Variable* const v, Variable* const u) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->out.begin();it!=v->out.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->in.begin();it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::list_active(Variable* const v, Variable* const u) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->out.begin();it!=v->out.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Cit it=v->in.begin();it!=v->in.end();++it) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * finds the constraint with the minimum lagrange multiplier, that is, the constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * that most wants to split
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanConstraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan fprintf(stderr,"Couldn't find split point!\n");
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz// populates block b by traversing the active constraint tree adding variables as they're
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// visited. Starts from variable v and does not backtrack over variable u.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit c=v->in.begin();c!=v->in.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit c=v->out.begin();c!=v->out.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Returns the active path between variables u and v... not back tracking over w
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Block::getActivePathBetween(Constraints& path, Variable const* u,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Variable const* v, Variable const *w) const {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(u==v) return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit_const c=u->in.begin();c!=u->in.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(getActivePathBetween(path, (*c)->left, v, u)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(getActivePathBetween(path, (*c)->right, v, u)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Search active constraint tree from u to see if there is a directed path to v.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Returns true if path is found with all constraints in path having their visited flag
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Block::isActiveDirectedPathBetween(Variable const* u, Variable const* v) const {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(u==v) return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(isActiveDirectedPathBetween((*c)->right,v)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraints& path, Variable const* u, Variable const* v) const {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(u==v) return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Cit_const c=u->out.begin();c!=u->out.end();++c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(getActiveDirectedPathBetween(path,(*c)->right,v)) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Block needs to be split because of a violated constraint between vl and vr.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * We need to search the active constraint tree between l and r and find the constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * with min lagrangrian multiplier and split at that point.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Returns the split constraint
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanConstraint* Block::splitBetween(Variable* const vl, Variable* const vr,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan f<<" need to split between: "<<*vl<<" and "<<*vr<<endl;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Creates two new blocks, l and r, and splits this block across constraint c,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * placing the left subtree of constraints (and associated variables) into l
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * and the right into r.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Block::split(Block* &l, Block* &r, Constraint* c) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //COLA_ASSERT(l->weight>0);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //COLA_ASSERT(r->weight>0);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Computes the cost (squared euclidean distance from desired positions) of the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * current positions for variables in this block
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for (Vit v=vars->begin();v!=vars->end();++v) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan double diff = (*v)->position() - (*v)->desiredPosition;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanostream& operator <<(ostream &os, const Block& b)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanConstraint::Constraint(Variable *left, Variable *right, double gap, bool equality)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // In hindsight I think it's probably better to build the constraint DAG
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // (by creating variable in/out lists) when needed, rather than in advance
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //left->out.push_back(this);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //right->in.push_back(this);
cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // see constructor: the following is just way too slow.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // Better to create a
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // new DAG on demand than maintain the lists dynamically.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //Constraints::iterator i;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //for(i=left->out.begin(); i!=left->out.end(); i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //if(*i==this) break;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //left->out.erase(i);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //for(i=right->in.begin(); i!=right->in.end(); i++) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //if(*i==this) break;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan //right->in.erase(i);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstd::ostream& operator <<(std::ostream &os, const Constraint &c)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan os<<lscale.str()<<*c.left<<"+"<<c.gap<<type<<rscale.str()<<*c.right;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan os<<"("<<c.slack()<<")"<<(c.active?"-active":"")
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool CompareConstraints::operator() (
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan Constraint *const &l, Constraint *const &r
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan // arbitrary choice based on id
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan if(l->right->id<r->right->id) return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstd::ostream& operator <<(std::ostream &os, const Variable &v) {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan os << "(" << v.id << "=" << v.position() << ")";
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan os << "(" << v.id << "=" << v.desiredPosition << ")";