From 0623102c16ecbf5ade1a7ef195659826a6f92548 Mon Sep 17 00:00:00 2001 From: Tim Dwyer Date: Wed, 10 May 2006 07:13:45 +0000 Subject: Apparently a problem was reported with one of the test cases. I can't reproduce the problem, however solve_VPSC code in inkscape was getting quite out of date with that in www.sf.net/projects/adaptagrams. I've updated the code, which may fix the problem, or at least if it's reported again then I'll know it's still an issue. (bzr r803) --- src/removeoverlap/solve_VPSC.cpp | 230 ++++++++++++++++++++++++++++++++------- 1 file changed, 188 insertions(+), 42 deletions(-) (limited to 'src/removeoverlap/solve_VPSC.cpp') diff --git a/src/removeoverlap/solve_VPSC.cpp b/src/removeoverlap/solve_VPSC.cpp index f2a7f0e85..21865c518 100644 --- a/src/removeoverlap/solve_VPSC.cpp +++ b/src/removeoverlap/solve_VPSC.cpp @@ -1,12 +1,13 @@ /** - * \brief Remove overlaps function + * \brief Solve an instance of the "Variable Placement with Separation + * Constraints" problem. * * Authors: * Tim Dwyer * * Copyright (C) 2005 Authors * - * Released under GNU GPL. Read the file 'COPYING' for more information. + * Released under GNU LGPL. Read the file 'COPYING' for more information. */ #include @@ -14,6 +15,8 @@ #include "block.h" #include "blocks.h" #include "solve_VPSC.h" +#include +#include #ifdef RECTANGLE_OVERLAP_LOGGING #include using std::ios; @@ -21,14 +24,22 @@ using std::ofstream; using std::endl; #endif +using std::ostringstream; using std::list; using std::set; -VPSC::VPSC(Variable *vs[], const int n, Constraint *cs[], const int m) : cs(cs), m(m) { - //assert(!constraintGraphIsCyclic(vs,n)); - bs=new Blocks(vs,n); +IncVPSC::IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) + : VPSC(n,vs,m,cs) { + inactive.assign(cs,cs+m); + for(ConstraintList::iterator i=inactive.begin();i!=inactive.end();++i) { + (*i)->active=false; + } +} +VPSC::VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]) : cs(cs), m(m), vs(vs) { + bs=new Blocks(n, vs); #ifdef RECTANGLE_OVERLAP_LOGGING printBlocks(); + assert(!constraintGraphIsCyclic(n,vs)); #endif } VPSC::~VPSC() { @@ -39,11 +50,11 @@ VPSC::~VPSC() { void VPSC::printBlocks() { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); - for(set::iterator i=bs->begin();i!=bs->end();i++) { + for(set::iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; f<<" "<<*b< *vs=bs->totalOrder(); - for(list::iterator i=vs->begin();i!=vs->end();i++) { + for(list::iterator i=vs->begin();i!=vs->end();++i) { Variable *v=*i; if(!v->block->deleted) { bs->mergeLeft(v->block); } } bs->cleanup(); - for(int i=0;islack()<-0.0000001) { #ifdef RECTANGLE_OVERLAP_LOGGING ofstream f(LOGFILE,ios::app); @@ -84,16 +95,16 @@ void VPSC::refine() { bool solved=false; // Solve shouldn't loop indefinately // ... but just to make sure we limit the number of iterations - int maxtries=100; + unsigned maxtries=100; while(!solved&&maxtries>=0) { solved=true; maxtries--; - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); b->setUpOutConstraints(); } - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; Constraint *c=b->findMinLM(); if(c!=NULL && c->lm<0) { @@ -111,7 +122,7 @@ void VPSC::refine() { } } } - for(int i=0;islack()<-0.0000001) { assert(cs[i]->slack()>-0.0000001); throw "Unsatisfied constraint"; @@ -129,26 +140,163 @@ void VPSC::solve() { refine(); } +void IncVPSC::solve() { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"solve_inc()..."<cost(); + do { + lastcost=cost; + satisfy(); + splitBlocks(); + cost = bs->cost(); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" cost="<0.0001); +} /** - * incremental version of solve that should allow refinement after blocks are - * moved. Work in progress. + * incremental version of satisfy that allows refinement after blocks are + * moved. + * + * - move blocks to new positions + * - repeatedly merge across most violated constraint until no more + * violated constraints exist + * + * Note: there is a special case to handle when the most violated constraint + * is between two variables in the same block. Then, we must split the block + * over an active constraint between the two variables. We choose the + * constraint with the most negative lagrangian multiplier. */ -void VPSC::move_and_split() { - //assert(!blockGraphIsCyclic()); - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { - Block *b=*i; - if(!b->deleted) { - b->wposn = b->desiredWeightedPosition(); - b->posn = b->wposn / b->weight; - Variable *v=b->vars->front(); - bs->mergeLeft(b); - // b may be merged away, so get any new block from one of its members - bs->mergeRight(v->block); +void IncVPSC::satisfy() { +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"satisfy_inc()..."<equality || v->slack()<-0.000001)) { + assert(!v->active); + Block *lb = v->left->block, *rb = v->right->block; + if(lb != rb) { + lb->merge(rb,v); + } else { + if(splitCtr++>10000) { + throw "Cycle Error!"; + } + // constraint is within block, need to split first + inactive.push_back(lb->splitBetween(v->left,v->right,lb,rb)); + lb->merge(rb,v); + bs->insert(lb); } } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" finished merges."<cleanup(); + for(unsigned i=0;islack()<-0.0000001) { + //assert(cs[i]->slack()>-0.0000001); + ostringstream s; + s<<"Unsatisfied constraint: "<<*v; + throw s.str().c_str(); + } + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" finished cleanup."<::const_iterator i(bs->begin());i!=bs->end();++i) { + Block *b = *i; + b->wposn = b->desiredWeightedPosition(); + b->posn = b->wposn / b->weight; + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" moved blocks."<::const_iterator i(bs->begin());i!=bs->end();++i) { + Block* b = *i; + Constraint* v=b->findMinLM(); + if(v!=NULL && v->lm < -0.0000001) { + assert(!v->equality); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" found split point: "<<*v<<" lm="<lm<left->block, *l=NULL, *r=NULL; + assert(v->left->block == v->right->block); + double pos = b->posn; + b->split(l,r,v); + l->posn=r->posn=pos; + l->wposn = l->posn * l->weight; + r->wposn = r->posn * r->weight; + bs->insert(l); + bs->insert(r); + b->deleted=true; + inactive.push_back(v); +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" new blocks: "<<*l<<" and "<<*r<cleanup(); - // assert(!blockGraphIsCyclic()); - refine(); +} + +/** + * Scan constraint list for the most violated constraint, or the first equality + * constraint + */ +Constraint* IncVPSC::mostViolated(ConstraintList &l) { + double minSlack = DBL_MAX; + Constraint* v=NULL; +#ifdef RECTANGLE_OVERLAP_LOGGING + ofstream f(LOGFILE,ios::app); + f<<"Looking for most violated..."<slack(); + if(c->equality || slack < minSlack) { + minSlack=slack; + v=c; + deletePoint=i; + if(c->equality) break; + } + } + // Because the constraint list is not order dependent we just + // move the last element over the deletePoint and resize + // downwards. There is always at least 1 element in the + // vector because of search. + if(deletePoint != end && (minSlack<-0.0000001||v->equality)) { + *deletePoint = l[l.size()-1]; + l.resize(l.size()-1); + } +#ifdef RECTANGLE_OVERLAP_LOGGING + f<<" most violated is: "<<*v< @@ -158,23 +306,22 @@ struct node { set in; set out; }; -/* // useful in debugging - cycles would be BAD -bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { +bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) { map varmap; vector graph; - for(int i=0;i::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) { + for(unsigned i=0;i::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();++c) { Variable *l=(*c)->left; varmap[vs[i]]->in.insert(varmap[l]); } - for(vector::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) { + for(vector::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();++c) { Variable *r=(*c)->right; varmap[vs[i]]->out.insert(varmap[r]); } @@ -182,7 +329,7 @@ bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { while(graph.size()>0) { node *u=NULL; vector::iterator i=graph.begin(); - for(;i!=graph.end();i++) { + for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; @@ -193,14 +340,14 @@ bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) { return true; } else { graph.erase(i); - for(set::iterator j=u->out.begin();j!=u->out.end();j++) { + for(set::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } delete u; } } - for(unsigned i=0; i bmap; vector graph; - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; node *u=new node; graph.push_back(u); bmap[b]=u; } - for(set::const_iterator i=bs->begin();i!=bs->end();i++) { + for(set::const_iterator i=bs->begin();i!=bs->end();++i) { Block *b=*i; b->setUpInConstraints(); Constraint *c=b->findMinInConstraint(); @@ -239,7 +386,7 @@ bool VPSC::blockGraphIsCyclic() { while(graph.size()>0) { node *u=NULL; vector::iterator i=graph.begin(); - for(;i!=graph.end();i++) { + for(;i!=graph.end();++i) { u=*i; if(u->in.size()==0) { break; @@ -250,7 +397,7 @@ bool VPSC::blockGraphIsCyclic() { return true; } else { graph.erase(i); - for(set::iterator j=u->out.begin();j!=u->out.end();j++) { + for(set::iterator j=u->out.begin();j!=u->out.end();++j) { node *v=*j; v->in.erase(u); } @@ -262,5 +409,4 @@ bool VPSC::blockGraphIsCyclic() { } return false; } -*/ -- cgit v1.2.3