diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libcola/compound_constraints.cpp')
| -rw-r--r-- | src/3rdparty/adaptagrams/libcola/compound_constraints.cpp | 1671 |
1 files changed, 1671 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libcola/compound_constraints.cpp b/src/3rdparty/adaptagrams/libcola/compound_constraints.cpp new file mode 100644 index 0000000..af9fa3e --- /dev/null +++ b/src/3rdparty/adaptagrams/libcola/compound_constraints.cpp @@ -0,0 +1,1671 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libcola - A library providing force-directed network layout using the + * stress-majorization method subject to separation constraints. + * + * Copyright (C) 2006-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 + * Michael Wybrow +*/ + +#include <algorithm> +#include <climits> +#include <sstream> + +#include <libvpsc/variable.h> +#include <libvpsc/constraint.h> +#include <libvpsc/assertions.h> + +#include "libcola/cola.h" +#include "libcola/compound_constraints.h" +#include "libcola/exceptions.h" + +using std::vector; +using vpsc::XDIM; +using vpsc::YDIM; + +namespace cola { + +void SubConstraintInfo::updateVarIDsWithMapping( + const VariableIDMap& idMap, bool forward) +{ + varIndex = idMap.mappingForVariable(varIndex, forward); +} + +//----------------------------------------------------------------------------- +// BoundaryConstraint code +//----------------------------------------------------------------------------- + +class Offset : public SubConstraintInfo +{ + public: + Offset(unsigned ind, double offset) : + SubConstraintInfo(ind), + distOffset(offset) + { + } + double distOffset; +}; + + +BoundaryConstraint::BoundaryConstraint(const vpsc::Dim dim) + : CompoundConstraint(dim), + position(0), + variable(nullptr) +{ +} + + +void BoundaryConstraint::updatePosition(const vpsc::Dim dim) +{ + if (dim == _primaryDim) + { + position = variable->finalPosition; + } +} + + +void BoundaryConstraint::addShape(const unsigned int index, + const double offset) +{ + _subConstraintInfo.push_back(new Offset(index, offset)); +} + + +void BoundaryConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " BoundaryConstraint *boundary%llu = " + "new BoundaryConstraint(vpsc::%cDIM);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y'); + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + fprintf(fp, " boundary%llu->addShape(%u, %g);\n", + (unsigned long long) this, info->varIndex, info->distOffset); + } + fprintf(fp, " ccs.push_back(boundary%llu);\n\n", + (unsigned long long) this); +} + + +std::string BoundaryConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "BoundaryConstraint("; + stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); + stream << "): {"; + bool first = true; + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + if (!first) + { + stream << ", "; + } + stream << "(" << "rect: " << info->varIndex << ", offset: " << info->distOffset << ")"; + first = false; + } + stream << "}"; + return stream.str(); +} + + +void BoundaryConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + if (dim == _primaryDim) + { + // Just one variable is generated, associated with the position + // of the boundary. This variable can float freely. + variable = new vpsc::Variable(vars.size(), position, freeWeight); + vars.push_back(variable); + } +} + + +void BoundaryConstraint::generateSeparationConstraints(const vpsc::Dim dim, + vpsc::Variables& vars, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(bbs); + if (dim == _primaryDim) + { + COLA_ASSERT(variable != nullptr); + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + assertValidVariableIndex(vars, info->varIndex); + vpsc::Constraint *constraint = nullptr; + if (info->distOffset < 0) + { + // Constrain the objects with negative offsets to be + // to the left of the boundary. + constraint = new vpsc::Constraint(vars[info->varIndex], + variable, -info->distOffset); + } + else + { + // Constrain the objects with positive offsets to be + // to the right of the boundary. + constraint = new vpsc::Constraint(variable, + vars[info->varIndex], info->distOffset); + } + constraint->creator = this; + cs.push_back(constraint); + } + } +} + + +SubConstraintAlternatives +BoundaryConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + SubConstraintAlternatives alternatives; + + Offset *info = static_cast<Offset *> + (_subConstraintInfo[_currSubConstraintIndex]); + + assertValidVariableIndex(vs[_primaryDim], info->varIndex); + if (info->distOffset < 0) + { + // Constrain the objects with negative offsets to be + // to the left of the boundary. + vpsc::Constraint constraint = vpsc::Constraint( + vs[_primaryDim][info->varIndex], variable, -info->distOffset); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + } + else + { + // Constrain the objects with positive offsets to be + // to the right of the boundary. + vpsc::Constraint constraint = vpsc::Constraint( + variable, vs[_primaryDim][info->varIndex], info->distOffset); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + } + + //fprintf(stderr, "===== BOUNDARYLINE ALTERNATIVES -======\n"); + return alternatives; +} + + + +//----------------------------------------------------------------------------- +// AlignmentConstraint code +//----------------------------------------------------------------------------- + +AlignmentConstraint::AlignmentConstraint(const vpsc::Dim dim, double position) + : CompoundConstraint(dim), + indicator(nullptr), + variable(nullptr), + _position(position), + _isFixed(false) +{ +} + + +void AlignmentConstraint::addShape(const unsigned int index, + const double offset) +{ + _subConstraintInfo.push_back(new Offset(index, offset)); +} + + +void AlignmentConstraint::updatePosition(const vpsc::Dim dim) +{ + if (dim == _primaryDim) + { + _position = variable->finalPosition; + } +} + + +void AlignmentConstraint::fixPos(double pos) +{ + _position = pos; + _isFixed = true; +} + + +void AlignmentConstraint::unfixPos() +{ + _isFixed = false; +} + + +double AlignmentConstraint::position(void) const +{ + return _position; +} + +bool AlignmentConstraint::isFixed(void) const +{ + return _isFixed; +} + +void AlignmentConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + if (dim == _primaryDim) + { + // Variable representing the position of a guideline. + variable = new vpsc::Variable(vars.size(), _position, freeWeight); + if (_isFixed) + { + variable->fixedDesiredPosition = true; + variable->weight = 100000; + } + vars.push_back(variable); + } +} + + +void AlignmentConstraint::generateSeparationConstraints(const vpsc::Dim dim, + vpsc::Variables& vars, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(bbs); + if (dim == _primaryDim) + { + COLA_ASSERT(variable != nullptr); + // Constrain each object to be offset from the guideline by + // some exact amount. + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + assertValidVariableIndex(vars, info->varIndex); + vpsc::Constraint *constraint = new vpsc::Constraint( + variable, vars[info->varIndex], info->distOffset, true); + constraint->creator = this; + cs.push_back(constraint); + } + } +} + +void AlignmentConstraint::updateShapeOffsetsForDifferentCentres( + const std::vector<double>& offsets, bool forward) +{ + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + if (offsets[info->varIndex] == 0) + { + continue; + } + + if (forward) + { + info->distOffset -= offsets[info->varIndex]; + } + else + { + info->distOffset += offsets[info->varIndex]; + } + } +} + +void AlignmentConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " AlignmentConstraint *alignment%llu = " + "new AlignmentConstraint(vpsc::%cDIM, %g);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', + _position); + if (_isFixed) + { + fprintf(fp, " alignment%llu->fixPos(%g);\n", + (unsigned long long) this, _position); + } + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + fprintf(fp, " alignment%llu->addShape(%u, %g);\n", + (unsigned long long) this, info->varIndex, info->distOffset); + } + fprintf(fp, " ccs.push_back(alignment%llu);\n\n", + (unsigned long long) this); +} + + +std::string AlignmentConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "AlignmentConstraint("; + stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); + stream << ", pos: " << _position; + if (_isFixed) + { + stream << ", fixed: true"; + } +#if 0 + // TODO: buggy. Not the right value. + if (variable) + { + stream << ", varInd: " << variable->id; + } +#endif + stream << "): {"; + bool first = true; + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + Offset *info = static_cast<Offset *> (*o); + if (!first) + { + stream << ", "; + } + stream << "(" << "rect: " << info->varIndex << ", offset: " << info->distOffset << ")"; + first = false; + } + stream << "}"; + return stream.str(); +} + + +SubConstraintAlternatives +AlignmentConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + SubConstraintAlternatives alternatives; + + Offset *info = static_cast<Offset *> + (_subConstraintInfo[_currSubConstraintIndex]); + + assertValidVariableIndex(vs[_primaryDim], info->varIndex); + vpsc::Constraint constraint(variable, vs[_primaryDim][info->varIndex], + info->distOffset, true); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + + //fprintf(stderr, "===== ALIGN ALTERNATIVES -======\n"); + return alternatives; +} + + +//----------------------------------------------------------------------------- +// SeparationConstraint code +//----------------------------------------------------------------------------- + + +class VarIndexPair : public SubConstraintInfo +{ + public: + VarIndexPair(unsigned ind1, unsigned ind2) + : SubConstraintInfo(ind1), + lConstraint(nullptr), + rConstraint(nullptr), + varIndex2(ind2) + { + } + VarIndexPair(AlignmentConstraint *l, AlignmentConstraint *r) + : SubConstraintInfo(0), + lConstraint(l), + rConstraint(r), + varIndex2(0) + { + } + unsigned indexL(void) const + { + return (lConstraint) ? + (unsigned) lConstraint->variable->id : varIndex; + } + unsigned indexR(void) const + { + return (rConstraint) ? + (unsigned) rConstraint->variable->id : varIndex2; + } + void updateVarIDsWithMapping(const VariableIDMap& idMap, bool forward) + { + varIndex = idMap.mappingForVariable(varIndex, forward); + varIndex2 = idMap.mappingForVariable(varIndex2, forward); + } + + AlignmentConstraint *lConstraint; + AlignmentConstraint *rConstraint; + unsigned varIndex2; +}; + + +SeparationConstraint::SeparationConstraint(const vpsc::Dim dim, + unsigned l, unsigned r, double g, bool equality) + : CompoundConstraint(dim), + gap(g), + equality(equality), + vpscConstraint(nullptr) +{ + _subConstraintInfo.push_back(new VarIndexPair(l, r)); +} + + +SeparationConstraint::SeparationConstraint(const vpsc::Dim dim, + AlignmentConstraint *l, AlignmentConstraint *r, double g, + bool equality) + : CompoundConstraint(dim), + gap(g), + equality(equality) +{ + COLA_ASSERT(l); + COLA_ASSERT(r); + + _subConstraintInfo.push_back(new VarIndexPair(l, r)); +} + + +void SeparationConstraint::printCreationCode(FILE *fp) const +{ + assert(_subConstraintInfo.size() == 1); + VarIndexPair *varIndexPair = (VarIndexPair *) _subConstraintInfo.front(); + if (varIndexPair->lConstraint && varIndexPair->rConstraint) + { + fprintf(fp, " SeparationConstraint *separation%llu = " + "new SeparationConstraint(vpsc::%cDIM, alignment%llu, " + "alignment%llu, %g, %s);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', + (unsigned long long) varIndexPair->lConstraint, + (unsigned long long) varIndexPair->rConstraint, gap, + (equality) ? "true" : "false"); + } + else + { + fprintf(fp, " SeparationConstraint *separation%llu = " + "new SeparationConstraint(vpsc::%cDIM, %u, %u, %g, %s);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', + varIndexPair->indexL(), varIndexPair->indexR(), gap, + (equality) ? "true" : "false"); + } + fprintf(fp, " ccs.push_back(separation%llu);\n\n", + (unsigned long long) this); +} + + +std::string SeparationConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "SeparationConstraint("; + stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); + stream << ", sep: " << gap; + stream << ", equality: " << ((equality) ? "true" : "false"); + stream << "): {"; + VarIndexPair *varIndexPair = (VarIndexPair *) _subConstraintInfo.front(); + if (varIndexPair->lConstraint && varIndexPair->rConstraint) + { + stream << "(alignment: " << varIndexPair->indexL() << "), "; + stream << "(alignment: " << varIndexPair->indexR() << "), "; + } + else + { + stream << "(rect: " << varIndexPair->indexL() << "), "; + stream << "(rect: " << varIndexPair->indexR() << "), "; + } + stream << "}"; + return stream.str(); +} + + +void SeparationConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); + + // No additional variables are required! +} + + +SubConstraintAlternatives +SeparationConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + SubConstraintAlternatives alternatives; + + VarIndexPair *info = static_cast<VarIndexPair *> + (_subConstraintInfo[_currSubConstraintIndex]); + + assertValidVariableIndex(vs[_primaryDim], info->indexL()); + assertValidVariableIndex(vs[_primaryDim], info->indexR()); + vpsc::Constraint constraint(vs[_primaryDim][info->indexL()], + vs[_primaryDim][info->indexR()], gap, equality); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + + //fprintf(stderr, "===== SEPARATION ALTERNATIVES -======\n"); + return alternatives; +} + + +void SeparationConstraint::generateSeparationConstraints(const vpsc::Dim dim, + vpsc::Variables& vs, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(bbs); + if (dim == _primaryDim) + { + VarIndexPair *info = + static_cast<VarIndexPair *> (_subConstraintInfo.front()); + + unsigned left = info->indexL(); + unsigned right = info->indexR(); + assertValidVariableIndex(vs, left); + assertValidVariableIndex(vs, right); + vpscConstraint = + new vpsc::Constraint(vs[left], vs[right], gap, equality); + vpscConstraint->creator = this; + cs.push_back(vpscConstraint); + } +} + + +unsigned SeparationConstraint::left(void) const +{ + VarIndexPair *info = + static_cast<VarIndexPair *> (_subConstraintInfo.front()); + + return info->indexL(); +} + + +unsigned SeparationConstraint::right(void) const +{ + VarIndexPair *info = + static_cast<VarIndexPair *> (_subConstraintInfo.front()); + + return info->indexR(); +} + + +void SeparationConstraint::setSeparation(double gap) +{ + this->gap = gap; + if (vpscConstraint != nullptr) + { + vpscConstraint->gap = gap; + } +} + + +//----------------------------------------------------------------------------- +// OrthogonalEdgeConstraint code +//----------------------------------------------------------------------------- + +OrthogonalEdgeConstraint::OrthogonalEdgeConstraint(const vpsc::Dim dim, + unsigned l, unsigned r) + : CompoundConstraint(dim), + left(l), + right(r), + vpscConstraint(nullptr) +{ +} + + +void OrthogonalEdgeConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); + + // No additional variables are required! +} + + +void OrthogonalEdgeConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " /* OrthogonalEdgeConstraint *orthogonal%llu = nullptr; */\n\n", + (unsigned long long) this); +} + + +std::string OrthogonalEdgeConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "OrthogonalEdgeConstraint()"; + return stream.str(); +} + + + +SubConstraintAlternatives +OrthogonalEdgeConstraint::getCurrSubConstraintAlternatives( + vpsc::Variables vs[]) +{ + COLA_UNUSED(vs); + + // XXX: What to do here? + _currSubConstraintIndex = _subConstraintInfo.size(); + return SubConstraintAlternatives(); +} + + +void OrthogonalEdgeConstraint::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(bbs); + if (dim == _primaryDim) + { + assertValidVariableIndex(vs, left); + assertValidVariableIndex(vs, right); + vpscConstraint = new vpsc::Constraint(vs[left], vs[right], 0, true); + vpscConstraint->creator = this; + cs.push_back(vpscConstraint); + } +} + + +void OrthogonalEdgeConstraint::generateTopologyConstraints(const vpsc::Dim k, + const vpsc::Rectangles& rs, vector<vpsc::Variable*> const & vars, + vector<vpsc::Constraint*> & cs) +{ + assertValidVariableIndex(vars, left); + assertValidVariableIndex(vars, right); + double lBound, rBound, pos; + if (k == vpsc::HORIZONTAL) + { + lBound = rs[left]->getCentreY(); + rBound = rs[right]->getCentreY(); + pos = rs[left]->getCentreX(); + } + else + { + lBound = rs[left]->getCentreX(); + rBound = rs[right]->getCentreX(); + pos = rs[left]->getCentreY(); + } + double minBound = std::min(lBound, rBound); + double maxBound = std::max(lBound, rBound); + for (unsigned i = 0; i < rs.size(); ++i) + { + if (i==left || i==right) continue; + vpsc::Rectangle *r = rs[i]; + if (r->allowOverlap()) continue; + double l, rMin, rMax, rCentre; + rectBounds(k, r, rMin, rMax, rCentre, l); + if ( ((rMin >= minBound) && (rMin <= maxBound)) || + ((rMax >= minBound) && (rMax <= maxBound))) + { + double g = l / 2; + if (rCentre < pos) + { + cs.push_back(new vpsc::Constraint(vars[i], vars[left], g)); + } + else + { + cs.push_back(new vpsc::Constraint(vars[left], vars[i], g)); + } + } + } +} + + +void OrthogonalEdgeConstraint::rectBounds(const vpsc::Dim k, + vpsc::Rectangle const *r, double& cmin, double& cmax, + double& centre, double & l) const +{ + if (k == vpsc::HORIZONTAL) + { + cmin = r->getMinY(); + cmax = r->getMaxY(); + centre = r->getCentreX(); + l = r->width(); + } + else + { + cmin = r->getMinX(); + cmax = r->getMaxX(); + centre = r->getCentreY(); + l = r->height(); + } +} + + +//----------------------------------------------------------------------------- +// MultiSeparationConstraint code +//----------------------------------------------------------------------------- + +class AlignmentPair : public SubConstraintInfo +{ + public: + AlignmentPair(AlignmentConstraint *ac1, AlignmentConstraint *ac2) + : SubConstraintInfo(0), + alignment1(ac1), + alignment2(ac2) + { + } + AlignmentConstraint *alignment1; + AlignmentConstraint *alignment2; +}; + + +MultiSeparationConstraint::MultiSeparationConstraint(const vpsc::Dim dim, + double minSep, bool equality) + : CompoundConstraint(dim), + indicator(nullptr), + sep(minSep), + equality(equality) +{ +} + + +void MultiSeparationConstraint::addAlignmentPair(AlignmentConstraint *ac1, + AlignmentConstraint *ac2) +{ + _subConstraintInfo.push_back(new AlignmentPair(ac1, ac2)); +} + + +void MultiSeparationConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " MultiSeparationConstraint *multiSep%llu = " + "new MultiSeparationConstraint(vpsc::%cDIM, %g, %s);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', sep, + (equality) ? "true" : "false"); + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + AlignmentPair *pair = static_cast<AlignmentPair *> (*o); + fprintf(fp, " multiSep%llu->addAlignmentPair(" + "alignment%llu, alignment%llu);\n", + (unsigned long long) this, + (unsigned long long) pair->alignment1, + (unsigned long long) pair->alignment2); + } + fprintf(fp, " ccs.push_back(multiSep%llu);\n\n", + (unsigned long long) this); +} + + +std::string MultiSeparationConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "MultiSeparationConstraint("; + stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); + stream << ", sep: " << sep; + stream << ", equality: " << ((equality) ? "true" : "false"); + stream << "): {"; + bool first = true; + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + if (!first) + { + stream << ", "; + } + AlignmentPair *pair = static_cast<AlignmentPair *> (*o); + stream << "(alignment: " << pair->alignment1->variable->id + << ", alignment: " << pair->alignment2->variable->id << ")"; + first = false; + } + stream << "}"; + return stream.str(); +} + + +void MultiSeparationConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); + + // No additional variables are required! +} + + +SubConstraintAlternatives +MultiSeparationConstraint::getCurrSubConstraintAlternatives( + vpsc::Variables vs[]) +{ + COLA_UNUSED(vs); + + SubConstraintAlternatives alternatives; + + AlignmentPair *info = static_cast<AlignmentPair *> + (_subConstraintInfo[_currSubConstraintIndex]); + + AlignmentConstraint *c1 = info->alignment1; + AlignmentConstraint *c2 = info->alignment2; + if (!c1->variable || !c2->variable) + { + throw InvalidConstraint(this); + } + vpsc::Constraint constraint(c1->variable, c2->variable, sep, equality); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + + //fprintf(stderr, "===== MULTI SEPARATION ALTERNATIVES -======\n"); + return alternatives; +} + + +void MultiSeparationConstraint::setSeparation(double sep) +{ + this->sep = sep; +} + + +void MultiSeparationConstraint::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& gcs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(vs); + COLA_UNUSED(bbs); + + if (dim == _primaryDim) + { + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + AlignmentPair *info = static_cast<AlignmentPair *> (*o); + AlignmentConstraint *c1 = info->alignment1; + AlignmentConstraint *c2 = info->alignment2; + if (!c1->variable || !c2->variable) + { + throw InvalidConstraint(this); + } + vpsc::Constraint *c = new vpsc::Constraint( + c1->variable, c2->variable, sep, equality); + c->creator = this; + gcs.push_back(c); + cs.push_back(c); + } + } +} + + +//----------------------------------------------------------------------------- +// DistributionConstraint code +//----------------------------------------------------------------------------- + +DistributionConstraint::DistributionConstraint(const vpsc::Dim dim) + : CompoundConstraint(dim), + indicator(nullptr) +{ +} + + +void DistributionConstraint::addAlignmentPair(AlignmentConstraint *ac1, + AlignmentConstraint *ac2) +{ + _subConstraintInfo.push_back(new AlignmentPair(ac1, ac2)); +} + + +void DistributionConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); + + // No additional variables are required! +} + + +void DistributionConstraint::setSeparation(double sep) +{ + this->sep = sep; +} + + +void DistributionConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " DistributionConstraint *distribution%llu = " + "new DistributionConstraint(vpsc::%cDIM);\n", + (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y'); + fprintf(fp, " distribution%llu->setSeparation(%g);\n", + (unsigned long long) this, sep); + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + AlignmentPair *pair = static_cast<AlignmentPair *> (*o); + fprintf(fp, " distribution%llu->addAlignmentPair(" + "alignment%llu, alignment%llu);\n", + (unsigned long long) this, + (unsigned long long) pair->alignment1, + (unsigned long long) pair->alignment2); + } + fprintf(fp, " ccs.push_back(distribution%llu);\n\n", + (unsigned long long) this); +} + + +std::string DistributionConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "DistributionConstraint("; + stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); + stream << ", sep: " << sep; + stream << "): {"; + bool first = true; + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + if (!first) + { + stream << ", "; + } + AlignmentPair *pair = static_cast<AlignmentPair *> (*o); + stream << "(alignment: " << pair->alignment1->variable->id + << ", alignment: " << pair->alignment2->variable->id << ")"; + first = false; + } + stream << "}"; + return stream.str(); +} + + +SubConstraintAlternatives +DistributionConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + COLA_UNUSED(vs); + + SubConstraintAlternatives alternatives; + + AlignmentPair *info = static_cast<AlignmentPair *> + (_subConstraintInfo[_currSubConstraintIndex]); + AlignmentConstraint *c1 = info->alignment1; + AlignmentConstraint *c2 = info->alignment2; + if (!c1->variable || !c2->variable) + { + throw InvalidConstraint(this); + } + vpsc::Constraint constraint(c1->variable, c2->variable, sep, true); + alternatives.push_back(SubConstraint(_primaryDim, constraint)); + + //fprintf(stderr, "===== DISTRIBUTION ALTERNATIVES -======\n"); + return alternatives; +} + + +void DistributionConstraint::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& gcs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(vars); + COLA_UNUSED(bbs); + + if (dim == _primaryDim) + { + cs.clear(); + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + AlignmentPair *info = static_cast<AlignmentPair *> (*o); + AlignmentConstraint *c1 = info->alignment1; + AlignmentConstraint *c2 = info->alignment2; + if (!c1->variable || !c2->variable) + { + throw InvalidConstraint(this); + } + vpsc::Constraint *c=new vpsc::Constraint( + c1->variable, c2->variable, sep, true); + c->creator = this; + gcs.push_back(c); + cs.push_back(c); +#if 0 + // The following was an experiment to allow variable distributions + // solved by optimisation rather than satisfying constraints + if(isVariable) { + // set second derivatives of: + // (u + g - v)^2 = g^2 + 2gu + u^2 - 2gv - 2uv + v^2 + (*Q)[make_pair(c1->variable->id,c1->variable->id)]+=w; + (*Q)[make_pair(c2->variable->id,c2->variable->id)]+=w; + (*Q)[make_pair(variable->id,variable->id)]+=w; + (*Q)[make_pair(c1->variable->id,c2->variable->id)]-=w; + (*Q)[make_pair(c2->variable->id,c1->variable->id)]-=w; + (*Q)[make_pair(c1->variable->id,variable->id)]+=w; + (*Q)[make_pair(variable->id,c1->variable->id)]+=w; + (*Q)[make_pair(c2->variable->id,variable->id)]-=w; + (*Q)[make_pair(variable->id,c2->variable->id)]-=w; + } +#endif + } + } +} + + +//----------------------------------------------------------------------------- +// FixedRelativeConstraint code +//----------------------------------------------------------------------------- + +class RelativeOffset : public SubConstraintInfo +{ + public: + RelativeOffset(unsigned indL, unsigned indR, vpsc::Dim dim, + double offset) + : SubConstraintInfo(indL), + varIndex2(indR), + dim(dim), + distOffset(offset) + { + } + void updateVarIDsWithMapping(const VariableIDMap& idMap, bool forward) + { + varIndex = idMap.mappingForVariable(varIndex, forward); + varIndex2 = idMap.mappingForVariable(varIndex2, forward); + } + + unsigned varIndex2; + vpsc::Dim dim; + double distOffset; +}; + + +FixedRelativeConstraint::FixedRelativeConstraint(const vpsc::Rectangles& rs, + std::vector<unsigned> shapeIds, const bool fixedPosition) + : CompoundConstraint(vpsc::XDIM), + m_fixed_position(fixedPosition), + m_shape_vars(shapeIds) +{ + _combineSubConstraints = true; + + // Make sure that m_shape_vars doesn't contain duplicates. + std::sort(m_shape_vars.begin(), m_shape_vars.end()); + std::vector<unsigned>::iterator last = + std::unique(m_shape_vars.begin(), m_shape_vars.end()); + m_shape_vars.erase(last, m_shape_vars.end()); + + unsigned firstId = UINT_MAX; + COLA_ASSERT(m_shape_vars.size() >= 2); + for (std::vector<unsigned>::iterator it = m_shape_vars.begin(); + it != m_shape_vars.end(); ++it) + { + COLA_ASSERT(*it < rs.size()); + + if (it == m_shape_vars.begin()) + { + firstId = *it; + } + else + { + unsigned thisId = *it; + _subConstraintInfo.push_back( + new RelativeOffset(firstId, thisId, vpsc::XDIM, + rs[thisId]->getCentreX() - rs[firstId]->getCentreX())); + _subConstraintInfo.push_back( + new RelativeOffset(firstId, thisId, vpsc::YDIM, + rs[thisId]->getCentreY() - rs[firstId]->getCentreY())); + } + } +} + +void FixedRelativeConstraint::updateVarIDsWithMapping( + const VariableIDMap& idMap, bool forward) +{ + CompoundConstraint::updateVarIDsWithMapping(idMap, forward); + + // We need to map variables in m_shape_vars too, + // since this is used in generateVariables(). + for (size_t i = 0; i < m_shape_vars.size(); ++i) + { + m_shape_vars[i] = idMap.mappingForVariable(m_shape_vars[i], forward); + } +} + + + +void FixedRelativeConstraint::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + COLA_UNUSED(dim); + COLA_UNUSED(vars); + + // No additional variables are required! + + // Fix shape positions if required. + if (m_fixed_position) + { + for (std::vector<unsigned>::iterator it = m_shape_vars.begin(); + it != m_shape_vars.end(); ++it) + { + vars[*it]->fixedDesiredPosition = true; + vars[*it]->weight = 100000; + } + } +} + + +void FixedRelativeConstraint::printCreationCode(FILE *fp) const +{ + fprintf(fp, " std::vector<unsigned> fixedRelativeSet%llu;\n", + (unsigned long long) this); + for (std::vector<unsigned>::const_iterator it = m_shape_vars.begin(); + it != m_shape_vars.end(); ++it) + { + fprintf(fp, " fixedRelativeSet%llu.push_back(%u);\n", + (unsigned long long) this, *it); + } + fprintf(fp, " FixedRelativeConstraint *fixedRelative%llu = " + "new FixedRelativeConstraint(rs, fixedRelativeSet%llu, %s);\n", + (unsigned long long) this, (unsigned long long) this, + (m_fixed_position) ? "true" : "false"); + fprintf(fp, " ccs.push_back(fixedRelative%llu);\n\n", + (unsigned long long) this); +} + + +std::string FixedRelativeConstraint::toString(void) const +{ + std::ostringstream stream; + stream << "FixedRelativeConstraint("; + stream << "fixedPos: " << ((m_fixed_position) ? "true" : "false"); + stream << "): {"; + bool first = true; + for (std::vector<unsigned>::const_iterator it = m_shape_vars.begin(); + it != m_shape_vars.end(); ++it) + { + if (!first) + { + stream << ", "; + } + stream << "(rect: " << *it << ")"; + first = false; + } + stream << "}"; + return stream.str(); +} + + +SubConstraintAlternatives +FixedRelativeConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + COLA_UNUSED(vs); + + SubConstraintAlternatives alternatives; + + RelativeOffset *offset = static_cast<RelativeOffset *> + (_subConstraintInfo[_currSubConstraintIndex]); + + vpsc::Dim dim = offset->dim; + vpsc::Constraint constraint(vs[dim][offset->varIndex], + vs[dim][offset->varIndex2], offset->distOffset, true); + alternatives.push_back(SubConstraint(dim, constraint)); + + //fprintf(stderr, "===== FixedRelativeConstraint ALTERNATIVES -======\n"); + return alternatives; +} + + +void FixedRelativeConstraint::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& ccs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(vars); + COLA_UNUSED(bbs); + + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + RelativeOffset *offset = static_cast<RelativeOffset *> (*o); + if (dim != offset->dim) + { + continue; + } + + assertValidVariableIndex(vars, offset->varIndex); + assertValidVariableIndex(vars, offset->varIndex2); + vpsc::Constraint *c = + new vpsc::Constraint(vars[offset->varIndex], + vars[offset->varIndex2], offset->distOffset, true); + c->creator = this; + ccs.push_back(c); + } +} + + +//----------------------------------------------------------------------------- +// PageBoundaryConstraint code +//----------------------------------------------------------------------------- + +class PageBoundaryShapeOffsets : public SubConstraintInfo +{ + public: + PageBoundaryShapeOffsets(unsigned ind, double xOffset, double yOffset) : + SubConstraintInfo(ind) + { + halfDim[0] = xOffset; + halfDim[1] = yOffset; + } + double halfDim[2]; // half width and height values; +}; + + +PageBoundaryConstraints::PageBoundaryConstraints(double xLow, double xHigh, + double yLow, double yHigh, double weight) + : CompoundConstraint(vpsc::HORIZONTAL) +{ + COLA_ASSERT(xLow < xHigh); + COLA_ASSERT(yLow < yHigh); + + leftMargin[vpsc::XDIM] = xLow; + rightMargin[vpsc::XDIM] = xHigh; + leftMargin[vpsc::YDIM] = yLow; + rightMargin[vpsc::YDIM] = yHigh; + + for (unsigned i = 0; i < 2; ++i) + { + actualLeftMargin[i] = leftMargin[i]; + actualRightMargin[i] = rightMargin[i]; + leftWeight[i] = weight; + rightWeight[i] = weight; + vl[i] = nullptr; + vr[i] = nullptr; + } +} + + +void PageBoundaryConstraints::addShape(unsigned id, double halfW, double halfH) +{ + _subConstraintInfo.push_back(new PageBoundaryShapeOffsets(id, halfW, halfH)); +} + + +void PageBoundaryConstraints::printCreationCode(FILE *fp) const +{ + fprintf(fp, " PageBoundaryConstraints *pageBoundary%llu = " + "new PageBoundaryConstraints(%g, %g, %g, %g, %g);\n", + (unsigned long long) this, leftMargin[vpsc::XDIM], + rightMargin[vpsc::XDIM], leftMargin[vpsc::YDIM], + rightMargin[vpsc::YDIM], leftWeight[0]); + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + PageBoundaryShapeOffsets *offsets = + static_cast<PageBoundaryShapeOffsets *> (*o); + fprintf(fp, " pageBoundary%llu->addShape(%u, %g, %g);\n", + (unsigned long long) this, offsets->varIndex, + offsets->halfDim[XDIM], offsets->halfDim[YDIM]); + } + fprintf(fp, " ccs.push_back(pageBoundary%llu);\n\n", + (unsigned long long) this); +} + + +std::string PageBoundaryConstraints::toString(void) const +{ + std::ostringstream stream; + stream << "PageBoundaryConstraints("; + stream << "xLow: " << leftMargin[vpsc::XDIM]; + stream << ", xHigh: " << rightMargin[vpsc::XDIM]; + stream << ", yLow: " << leftMargin[vpsc::YDIM]; + stream << ", yHigh: " << rightMargin[vpsc::YDIM]; + stream << ", weight: " << leftWeight[0]; + stream << "): {"; + bool first = true; + for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + if (!first) + { + stream << ", "; + } + PageBoundaryShapeOffsets *offsets = + static_cast<PageBoundaryShapeOffsets *> (*o); + stream << "(rect: " << offsets->varIndex; + stream << ", halfWidth: " << offsets->halfDim[XDIM]; + stream << ", halfHeight: " << offsets->halfDim[YDIM]; + stream <<")"; + first = false; + } + stream << "}"; + return stream.str(); +} + +SubConstraintAlternatives +PageBoundaryConstraints::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) +{ + COLA_UNUSED(vs); + + // Page boundary constraints do not need to be evaluated at the + // time of makeFeasible, so we return an empty list here. + _currSubConstraintIndex = _subConstraintInfo.size(); + return SubConstraintAlternatives(); +} + + +void PageBoundaryConstraints::updatePosition(const vpsc::Dim dim) +{ + if (vl[dim]) + { + actualLeftMargin[dim] = vl[dim]->finalPosition; + } + + if (vr[dim]) + { + actualRightMargin[dim] = vr[dim]->finalPosition; + } +} + + +double PageBoundaryConstraints::getActualLeftMargin(const vpsc::Dim dim) +{ + return actualLeftMargin[dim]; +} + + +double PageBoundaryConstraints::getActualRightMargin(const vpsc::Dim dim) +{ + return actualRightMargin[dim]; +} + + +void PageBoundaryConstraints::generateVariables(const vpsc::Dim dim, + vpsc::Variables& vars) +{ + // create 2 dummy vars, based on the dimension we are in + if (leftWeight[dim]) + { + vars.push_back(vl[dim] = new vpsc::Variable(vars.size(), + leftMargin[dim], leftWeight[dim])); + vl[dim]->fixedDesiredPosition = true; + } + + if (rightWeight[dim]) + { + vars.push_back(vr[dim] = new vpsc::Variable(vars.size(), + rightMargin[dim], rightWeight[dim])); + vr[dim]->fixedDesiredPosition = true; + } +} + + +void PageBoundaryConstraints::generateSeparationConstraints( + const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + COLA_UNUSED(bbs); + // For each of the "real" variables, create a constraint that puts + // that var between our two new dummy vars, depending on the dimension. + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + PageBoundaryShapeOffsets *info = + static_cast<PageBoundaryShapeOffsets *> (*o); + assertValidVariableIndex(vs, info->varIndex); + if (vl[dim]) + { + vpsc::Constraint *constraint = new vpsc::Constraint(vl[dim], + vs[info->varIndex], info->halfDim[dim]); + constraint->creator = this; + cs.push_back(constraint); + } + + if (vr[dim]) + { + vpsc::Constraint *constraint = new vpsc::Constraint( + vs[info->varIndex], vr[dim], info->halfDim[dim]); + constraint->creator = this; + cs.push_back(constraint); + } + } +} + + +//----------------------------------------------------------------------------- +// Support code +//----------------------------------------------------------------------------- + + +struct GenerateVariables +{ + GenerateVariables(const vpsc::Dim dim, vpsc::Variables& vars) + : dim(dim), + vars(vars) + { + } + void operator() (CompoundConstraint *c) + { + c->generateVariables(dim, vars); + } + + const vpsc::Dim dim; + vpsc::Variables& vars; +}; + + +struct GenerateSeparationConstraints +{ + GenerateSeparationConstraints(const vpsc::Dim dim, vpsc::Variables& vars, + vpsc::Constraints& cs, vpsc::Rectangles& bbs) + : dim(dim), + vars(vars), + cs(cs), + bbs(bbs) + { + } + void operator() (CompoundConstraint *c) + { + c->generateSeparationConstraints(dim, vars, cs, bbs); + } + const vpsc::Dim dim; + vpsc::Variables& vars; + vpsc::Constraints& cs; + vpsc::Rectangles& bbs; +}; + + +void generateVariablesAndConstraints(CompoundConstraints& ccs, + const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& cs, + vpsc::Rectangles& bbs) +{ + for_each(ccs.begin(), ccs.end(), + GenerateVariables(dim, vars)); + for_each(ccs.begin(), ccs.end(), + GenerateSeparationConstraints(dim, vars, cs, bbs)); +} + + +void generateVariables(CompoundConstraints& ccs, const vpsc::Dim dim, + vpsc::Variables& vars) +{ + for_each(ccs.begin(), ccs.end(), + GenerateVariables(dim, vars)); +} + + +CompoundConstraint::CompoundConstraint(vpsc::Dim primaryDim, + unsigned int priority) : + _primaryDim(primaryDim), + _secondaryDim((vpsc::Dim) ((primaryDim + 1) % 2)), + _priority(priority), + _combineSubConstraints(false), + _currSubConstraintIndex(0) +{ +} + + +CompoundConstraint::~CompoundConstraint() +{ + // Free memory from the subConstraintInfo list. + for_each(_subConstraintInfo.begin(), _subConstraintInfo.end(), delete_object()); + _subConstraintInfo.clear(); +} + + +vpsc::Dim CompoundConstraint::dimension(void) const +{ + return _primaryDim; +} + + +unsigned int CompoundConstraint::priority(void) const +{ + return _priority; +} + + +void CompoundConstraint::printCreationCode(FILE *fp) const +{ + COLA_UNUSED(fp); + + // Do nothing. Subclasses can implement this. +} + +void CompoundConstraint::updateVarIDsWithMapping(const VariableIDMap& idMap, + bool forward) +{ + for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); + o != _subConstraintInfo.end(); ++o) + { + (*o)->updateVarIDsWithMapping(idMap, forward); + } +} + + +std::list<unsigned> CompoundConstraint::subConstraintObjIndexes(void) const +{ + std::list<unsigned> idList; + for (size_t i = 0; i < _subConstraintInfo.size(); ++i) + { + idList.push_back(_subConstraintInfo[i]->varIndex); + } + return idList; +} + + +bool CompoundConstraint::subConstraintsRemaining(void) const +{ + return _currSubConstraintIndex < _subConstraintInfo.size(); +} + + +void CompoundConstraint::markAllSubConstraintsAsInactive(void) +{ + for (size_t i = 0; i < _subConstraintInfo.size(); ++i) + { + _subConstraintInfo[i]->satisfied = false; + } + _currSubConstraintIndex = 0; +} + + +void CompoundConstraint::markCurrSubConstraintAsActive(const bool satisfiable) +{ + _subConstraintInfo[_currSubConstraintIndex]->satisfied = satisfiable; + + _currSubConstraintIndex++; +} + + +void CompoundConstraint::assertValidVariableIndex(const vpsc::Variables& vars, + const unsigned index) +{ + if (index >= vars.size()) + { + throw InvalidVariableIndexException(this, index); + } +} + + +bool CompoundConstraint::shouldCombineSubConstraints(void) const +{ + return _combineSubConstraints; +} + + +UnsatisfiableConstraintInfo::UnsatisfiableConstraintInfo( + const vpsc::Constraint *c) + : leftVarIndex(c->left->id), + rightVarIndex(c->right->id), + separation(c->gap), + equality(c->equality), + cc((CompoundConstraint *)c->creator) +{ +} + +// Variable mapping. + +VariableIDMap::VariableIDMap() +{ +} + +VariableIDMap::~VariableIDMap() +{ +} + +typedef std::pair<unsigned, unsigned> IDPair; +typedef std::list<IDPair> IDPairList; + +bool VariableIDMap::addMappingForVariable(const unsigned from, + const unsigned to) +{ + bool found = false; + for (IDPairList::iterator it = m_mapping.begin(); it != m_mapping.end(); + ++it) + { + IDPair& ids = *it; + + if (ids.first == from) + { + found = true; + break; + } + } + + if (!found) + { + m_mapping.push_back(std::make_pair(from, to)); + return true; + } + //fprintf(stderr, "VariableIDMap: mapping already exists for var %u\n", from); + return false; +} + +void VariableIDMap::printCreationCode(FILE *fp) const +{ + fprintf(fp, " cola::VariableIDMap idMap;\n"); + for (IDPairList::const_iterator it = m_mapping.begin(); + it != m_mapping.end(); ++it) + { + fprintf(fp, " idMap.addMappingForVariable(%u, %u);\n", + it->first, it->second); + } + fprintf(fp, " \n"); +} + +unsigned VariableIDMap::mappingForVariable(const unsigned var, + bool forward) const +{ + for (IDPairList::const_iterator it = m_mapping.begin(); + it != m_mapping.end(); ++it) + { + const IDPair& ids = *it; + + if (forward) + { + if (ids.first == var) + { + return ids.second; + } + } + else // (!forward) + { + if (ids.second == var) + { + return ids.first; + } + } + } + + //fprintf(stderr, "Warning: mapping not found for var %u\n", var); + + // Just return original variable index. + return var; +} + +void VariableIDMap::clear(void) +{ + m_mapping.clear(); +} + + +} // namespace cola + |