diff options
Diffstat (limited to 'src/libvpsc/constraint.cpp')
| -rw-r--r-- | src/libvpsc/constraint.cpp | 224 |
1 files changed, 198 insertions, 26 deletions
diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp index 0ec06dfac..f1b7f0571 100644 --- a/src/libvpsc/constraint.cpp +++ b/src/libvpsc/constraint.cpp @@ -1,14 +1,36 @@ /* - * 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. * - * Released under GNU LGPL. Read the file 'COPYING' for more information. - */ + * 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 +*/ -#include "constraint.h" + +#include <map> +#include <list> +#include <sstream> #include <cassert> +#include <cfloat> +#include <cmath> + + +#include "libvpsc/constraint.h" +#include "libvpsc/variable.h" + namespace vpsc { Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality) : left(left), @@ -16,31 +38,181 @@ Constraint::Constraint(Variable *left, Variable *right, double gap, bool equalit gap(gap), timeStamp(0), active(false), - visited(false), - equality(equality) + equality(equality), + unsatisfiable(false), + needsScaling(true), + creator(NULL) { - left->out.push_back(this); - right->in.push_back(this); + // In hindsight I think it's probably better to build the constraint DAG + // (by creating variable in/out lists) when needed, rather than in advance + //left->out.push_back(this); + //right->in.push_back(this); } Constraint::~Constraint() { - Constraints::iterator i; - for(i=left->out.begin(); i!=left->out.end(); ++i) { - if(*i==this) break; - } - left->out.erase(i); - for(i=right->in.begin(); i!=right->in.end(); ++i) { - if(*i==this) break; - } - right->in.erase(i); + // see constructor: the following is just way too slow. + // Better to create a + // new DAG on demand than maintain the lists dynamically. + //Constraints::iterator i; + //for(i=left->out.begin(); i!=left->out.end(); i++) { + //if(*i==this) break; + //} + //left->out.erase(i); + //for(i=right->in.begin(); i!=right->in.end(); i++) { + //if(*i==this) break; + //} + //right->in.erase(i); } std::ostream& operator <<(std::ostream &os, const Constraint &c) { - if(&c==NULL) { - os<<"NULL"; - } else { - const char *type=c.equality?"=":"<="; - os<<*c.left<<"+"<<c.gap<<type<<*c.right<<"("<<c.slack()<<")"<<(c.active?"-active":""); - } - return os; + const char *type = c.equality ? "=" : "<="; + std::ostringstream lscale, rscale; + if (c.left->scale != 1) + { + lscale << c.left->scale << "*"; + } + if (c.right->scale != 1) + { + rscale << c.right->scale << "*"; + } + os << lscale.str() << *c.left << "+" << c.gap << type << + rscale.str() << *c.right; + if (c.left->block && c.right->block) + { + os << "(" << c.slack() << ")" << (c.active ? "-active" : "") << + "(lm=" << c.lm << ")"; + } + else + { + os << "(vars have no position)"; + } + return os; +} +#include "libvpsc/block.h" +bool CompareConstraints::operator() ( + Constraint *const &l, Constraint *const &r +) const { + double const sl = + l->left->block->timeStamp > l->timeStamp + ||l->left->block==l->right->block + ?-DBL_MAX:l->slack(); + double const sr = + r->left->block->timeStamp > r->timeStamp + ||r->left->block==r->right->block + ?-DBL_MAX:r->slack(); + if(sl==sr) { + // arbitrary choice based on id + if(l->left->id==r->left->id) { + if(l->right->id<r->right->id) return true; + return false; + } + if(l->left->id<r->left->id) return true; + return false; + } + return sl < sr; +} + + +typedef std::list<std::map<Variable *, double> > VarOffsetMapList; + +class EqualityConstraintSet +{ + public: + EqualityConstraintSet(Variables vs) + { + for (size_t i = 0; i < vs.size(); ++i) + { + std::map<Variable *, double> varSet; + varSet[vs[i]] = 0; + variableGroups.push_back(varSet); + } + } + bool isRedundant(Variable *lhs, Variable *rhs, double sep) + { + VarOffsetMapList::iterator lhsSet = setForVar(lhs); + VarOffsetMapList::iterator rhsSet = setForVar(rhs); + COLA_ASSERT(lhsSet != variableGroups.end()); + COLA_ASSERT(rhsSet != variableGroups.end()); + if (lhsSet == rhsSet) + { + // Check if this is a redundant constraint. + if (fabs(((*lhsSet)[lhs] + sep) - (*rhsSet)[rhs]) < 0.0001) + { + // If so, return true. + return true; + } + } + return false; + } + void mergeSets(Variable *lhs, Variable *rhs, double sep) + { + VarOffsetMapList::iterator lhsSet = setForVar(lhs); + VarOffsetMapList::iterator rhsSet = setForVar(rhs); + if (lhsSet == rhsSet) + { + return; + } + + double rhsOldOffset = (*rhsSet)[rhs]; + double rhsNewOffset = (*lhsSet)[lhs] + sep; + double offset = rhsNewOffset - rhsOldOffset; + + // Update offsets + for (std::map<Variable *, double>::iterator it = rhsSet->begin(); + it != rhsSet->end(); ++it) + { + it->second += offset; + } + + // Merge rhsSet into lhsSet + lhsSet->insert(rhsSet->begin(), rhsSet->end()); + variableGroups.erase(rhsSet); + } + + private: + VarOffsetMapList::iterator setForVar(Variable *var) + { + for (VarOffsetMapList::iterator it = variableGroups.begin(); + it != variableGroups.end(); ++it) + { + if (it->find(var) != it->end()) + { + return it; + } + } + return variableGroups.end(); + } + + VarOffsetMapList variableGroups; +}; + +Constraints constraintsRemovingRedundantEqualities(const Variables& vars, + const Constraints& constraints) +{ + EqualityConstraintSet equalitySets(vars); + Constraints cs = Constraints(constraints.size()); + int csSize = 0; + + for (unsigned i = 0; i < constraints.size(); ++i) + { + Constraint *c = constraints[i]; + if (c->equality) + { + if (!equalitySets.isRedundant(c->left, c->right, c->gap)) + { + // Only add non-redundant equalities + equalitySets.mergeSets(c->left, c->right, c->gap); + cs[csSize++] = c; + } + } + else + { + // Add all non-equalities + cs[csSize++] = c; + } + } + cs.resize(csSize); + return cs; } + + } |