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)

1 files changed, 188 insertions, 42 deletions

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 <tgdwyer@gmail.com>
  *
  * 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 <cassert>
@@ -14,6 +15,8 @@
 #include "block.h"
 #include "blocks.h"
 #include "solve_VPSC.h"
+#include <math.h>
+#include <sstream>
 #ifdef RECTANGLE_OVERLAP_LOGGING
 #include <fstream>
 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<Block*>::iterator i=bs->begin();i!=bs->end();i++) {
+	for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
 		Block *b=*i;
 		f<<"  "<<*b<<endl;
 	}
-	for(int i=0;i<m;i++) {
+	for(unsigned i=0;i<m;i++) {
 		f<<"  "<<*cs[i]<<endl;
 	}
 #endif
@@ -60,14 +71,14 @@ void VPSC::printBlocks() {
 */
 void VPSC::satisfy() {
 	list<Variable*> *vs=bs->totalOrder();
-	for(list<Variable*>::iterator i=vs->begin();i!=vs->end();i++) {
+	for(list<Variable*>::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;i<m;i++) {
+	for(unsigned i=0;i<m;i++) {
 		if(cs[i]->slack()<-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<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
+		for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();++i) {
 			Block *b=*i;
 			b->setUpInConstraints();
 			b->setUpOutConstraints();
 		}
-		for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
+		for(set<Block*>::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;i<m;i++) {
+	for(unsigned i=0;i<m;i++) {
 		if(cs[i]->slack()<-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()..."<<endl;
+#endif
+	double lastcost,cost = bs->cost();
+	do {
+		lastcost=cost;
+		satisfy();
+		splitBlocks();
+		cost = bs->cost();
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  cost="<<cost<<endl;
+#endif
+	} while(fabs(lastcost-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<Block*>::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()..."<<endl;
+#endif
+	splitBlocks();
+	long splitCtr = 0;
+	Constraint* v = NULL;
+	while((v=mostViolated(inactive))&&(v->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."<<endl;
+#endif
+	bs->cleanup();
+	for(unsigned i=0;i<m;i++) {
+		v=cs[i];
+		if(v->slack()<-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."<<endl;
+	printBlocks();
+#endif
+}
+void IncVPSC::moveBlocks() {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"moveBlocks()..."<<endl;
+#endif
+	for(set<Block*>::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."<<endl;
+#endif
+}
+void IncVPSC::splitBlocks() {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+#endif
+	moveBlocks();
+	splitCnt=0;
+	// Split each block if necessary on min LM
+	for(set<Block*>::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="<<v->lm<<endl;
+#endif
+			splitCnt++;
+			Block *b = v->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<<endl;
+#endif
+		}
+	}
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  finished splits."<<endl;
+#endif
 	bs->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..."<<endl;
+#endif
+	ConstraintList::iterator end = l.end();
+	ConstraintList::iterator deletePoint = end;
+	for(ConstraintList::iterator i=l.begin();i!=end;++i) {
+		Constraint *c=*i;
+		double slack = c->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<<endl;
+#endif
+	return v;
 }
 
 #include <map>
@@ -158,23 +306,22 @@ struct node {
 	set<node*> in;
 	set<node*> 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<Variable*, node*> varmap;
 	vector<node*> graph;
-	for(int i=0;i<n;i++) {
+	for(unsigned i=0;i<n;i++) {
 		node *u=new node;
 		graph.push_back(u);
 		varmap[vs[i]]=u;
 	}
-	for(int i=0;i<n;i++) {
-		for(vector<Constraint*>::iterator c=vs[i]->in.begin();c!=vs[i]->in.end();c++) {
+	for(unsigned i=0;i<n;i++) {
+		for(vector<Constraint*>::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<Constraint*>::iterator c=vs[i]->out.begin();c!=vs[i]->out.end();c++) {
+		for(vector<Constraint*>::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<node*>::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<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
+			for(set<node*>::iterator j=u->out.begin();j!=u->out.end();++j) {
 				node *v=*j;
 				v->in.erase(u);
 			}
 			delete u;
 		}
 	}
-	for(unsigned i=0; i<graph.size(); i++) {
+	for(unsigned i=0; i<graph.size(); ++i) {
 		delete graph[i];
 	}
 	return false;
@@ -210,13 +357,13 @@ bool VPSC::constraintGraphIsCyclic(Variable *vs[], const int n) {
 bool VPSC::blockGraphIsCyclic() {
 	map<Block*, node*> bmap;
 	vector<node*> graph;
-	for(set<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
+	for(set<Block*>::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<Block*>::const_iterator i=bs->begin();i!=bs->end();i++) {
+	for(set<Block*>::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<node*>::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<node*>::iterator j=u->out.begin();j!=u->out.end();j++) {
+			for(set<node*>::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;
 }
-*/