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)

17 files changed, 475 insertions, 169 deletions

diff --git a/src/removeoverlap/block.cpp b/src/removeoverlap/block.cpp
index 7a2ab53af..042d9fc3c 100644
--- a/src/removeoverlap/block.cpp
+++ b/src/removeoverlap/block.cpp
@@ -1,18 +1,20 @@
 /**
- * \brief Remove overlaps function
+ * \brief A block is a group of variables that must be moved together to improve
+ * the goal function without violating already active constraints.
+ * The variables in a block are spanned by a tree of active constraints.
  *
  * 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>
+#include "pairingheap/PairingHeap.h"
 #include "constraint.h"
 #include "block.h"
 #include "blocks.h"
-#include "pairingheap/PairingHeap.h"
 #ifdef RECTANGLE_OVERLAP_LOGGING
 #include <fstream>
 using std::ios;
@@ -21,6 +23,8 @@ using std::endl;
 #endif
 using std::vector;
 
+typedef vector<Constraint*>::iterator Cit;
+
 void Block::addVariable(Variable *v) {
 	v->block=this;
 	vars->push_back(v);
@@ -43,7 +47,7 @@ Block::Block(Variable *v) {
 
 double Block::desiredWeightedPosition() {
 	double wp = 0;
-	for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
+	for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();++v) {
 		wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
 	}
 	return wp;
@@ -63,10 +67,10 @@ void Block::setUpOutConstraints() {
 void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
 	delete h;
 	h = new PairingHeap<Constraint*>(&compareConstraints);
-	for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) {
+	for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();++i) {
 		Variable *v=*i;
 		vector<Constraint*> *cs=in?&(v->in):&(v->out);
-		for (vector<Constraint*>::iterator j=cs->begin();j!=cs->end();j++) {
+		for (Cit j=cs->begin();j!=cs->end();++j) {
 			Constraint *c=*j;
 			c->timeStamp=blockTimeCtr;
 			if (c->left->block != this && in || c->right->block != this && !in) {
@@ -75,6 +79,23 @@ void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
 		}
 	}
 }	
+void Block::merge(Block* b, Constraint* c) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"  merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
+#endif
+	double dist = c->right->offset - c->left->offset - c->gap;
+	Block *l=c->left->block;
+	Block *r=c->right->block;
+	if (vars->size() < b->vars->size()) {
+		r->merge(l,c,dist);
+	} else {
+	       	l->merge(r,c,-dist);
+	}
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  merged block="<<(b->deleted?*this:*b)<<endl;
+#endif
+}
 /**
  * Merges b into this block across c.  Can be either a
  * right merge or a left merge
@@ -83,16 +104,21 @@ void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
  * @param distance separation required to satisfy c
  */
 void Block::merge(Block *b, Constraint *c, double dist) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"    merging: "<<*b<<"dist="<<dist<<endl;
+#endif
 	c->active=true;
 	wposn+=b->wposn-dist*b->weight;
 	weight+=b->weight;
 	posn=wposn/weight;
-	for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();i++) {
+	for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();++i) {
 		Variable *v=*i;
 		v->block=this;
 		v->offset+=dist;
 		vars->push_back(v);
 	}
+	b->deleted=true;
 }
 
 void Block::mergeIn(Block *b) {
@@ -150,7 +176,7 @@ Constraint *Block::findMinInConstraint() {
 			break;
 		}
 	}
-	for(vector<Constraint*>::iterator i=outOfDate.begin();i!=outOfDate.end();i++) {
+	for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
 		v=*i;
 		v->timeStamp=blockTimeCtr;
 		in->insert(v);
@@ -197,35 +223,92 @@ inline bool Block::canFollowRight(Constraint *c, Variable *last) {
 // in min_lm
 double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) {
 	double dfdv=v->weight*(v->position() - v->desiredPosition);
-	for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
+	for(Cit it=v->out.begin();it!=v->out.end();++it) {
 		Constraint *c=*it;
 		if(canFollowRight(c,u)) {
 			dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
-			if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
+			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
 		}
 	}
-	for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
+	for(Cit it=v->in.begin();it!=v->in.end();++it) {
 		Constraint *c=*it;
 		if(canFollowLeft(c,u)) {
 			dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
-			if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
+			if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
 		}
 	}
 	return dfdv;
 }
 
+
+// computes dfdv for each variable and uses the sum of dfdv on either side of
+// the constraint c to compute the lagrangian multiplier lm_c.
+// The top level v and r are variables between which we want to find the
+// constraint with the smallest lm.  
+// When we find r we pass NULL to subsequent recursive calls, 
+// thus r=NULL indicates constraints are not on the shortest path.
+// Similarly, m is initially NULL and is only assigned a value if the next
+// variable to be visited is r or if a possible min constraint is returned from
+// a nested call (rather than NULL).
+// Then, the search for the m with minimum lm occurs as we return from
+// the recursion (checking only constraints traversed left-to-right 
+// in order to avoid creating any new violations).
+// We also do not consider equality constraints as potential split points
+Block::Pair Block::compute_dfdv_between(Variable* r, Variable* v, Variable* u, 
+		Direction dir = NONE, bool changedDirection = false) {
+	double dfdv=v->weight*(v->position() - v->desiredPosition);
+	Constraint *m=NULL;
+	for(Cit it(v->in.begin());it!=v->in.end();++it) {
+		Constraint *c=*it;
+		if(canFollowLeft(c,u)) {
+			if(dir==RIGHT) { 
+				changedDirection = true; 
+			}
+			if(c->left==r) {
+			       	r=NULL;
+			        if(!c->equality) m=c; 
+			}
+			Pair p=compute_dfdv_between(r,c->left,v,
+					LEFT,changedDirection);
+			dfdv -= c->lm = -p.first;
+			if(r && p.second) 
+				m = p.second;
+		}
+	}
+	for(Cit it(v->out.begin());it!=v->out.end();++it) {
+		Constraint *c=*it;
+		if(canFollowRight(c,u)) {
+			if(dir==LEFT) { 
+				changedDirection = true; 
+			}
+			if(c->right==r) {
+			       	r=NULL; 
+			        if(!c->equality) m=c; 
+			}
+			Pair p=compute_dfdv_between(r,c->right,v,
+					RIGHT,changedDirection);
+			dfdv += c->lm = p.first;
+			if(r && p.second) 
+				m = changedDirection && !c->equality && c->lm < p.second->lm 
+					? c 
+					: p.second;
+		}
+	}
+	return Pair(dfdv,m);
+}
+
 // resets LMs for all active constraints to 0 by
 // traversing active constraint tree starting from v,
 // not back tracking over u
 void Block::reset_active_lm(Variable *v, Variable *u) {
-	for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
+	for(Cit it=v->out.begin();it!=v->out.end();++it) {
 		Constraint *c=*it;
 		if(canFollowRight(c,u)) {
 			c->lm=0;
 			reset_active_lm(c->right,v);
 		}
 	}
-	for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
+	for(Cit it=v->in.begin();it!=v->in.end();++it) {
 		Constraint *c=*it;
 		if(canFollowLeft(c,u)) {
 			c->lm=0;
@@ -243,26 +326,51 @@ Constraint *Block::findMinLM() {
 	compute_dfdv(vars->front(),NULL,min_lm);
 	return min_lm;
 }
+Constraint *Block::findMinLMBetween(Variable* lv, Variable* rv) {
+	Constraint *min_lm=NULL;
+	reset_active_lm(vars->front(),NULL);
+	min_lm=compute_dfdv_between(rv,lv,NULL).second;
+	return min_lm;
+}
 
 // populates block b by traversing the active constraint tree adding variables as they're 
 // visited.  Starts from variable v and does not backtrack over variable u.
 void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) {
 	b->addVariable(v);
-	for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) {
+	for (Cit c=v->in.begin();c!=v->in.end();++c) {
 		if (canFollowLeft(*c,u))
 			populateSplitBlock(b, (*c)->left, v);
 	}
-	for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) {
+	for (Cit c=v->out.begin();c!=v->out.end();++c) {
 		if (canFollowRight(*c,u)) 
 			populateSplitBlock(b, (*c)->right, v);
 	}
 }
 /**
+ * Block needs to be split because of a violated constraint between vl and vr.
+ * We need to search the active constraint tree between l and r and find the constraint
+ * with min lagrangrian multiplier and split at that point.
+ * Returns the split constraint
+ */
+Constraint* Block::splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"  need to split between: "<<*vl<<" and "<<*vr<<endl;
+#endif
+	Constraint *c=findMinLMBetween(vl, vr);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  going to split on: "<<*c<<endl;
+#endif
+	split(lb,rb,c);
+	deleted = true;
+	return c;
+}
+/**
  * Creates two new blocks, l and r, and splits this block across constraint c,
  * placing the left subtree of constraints (and associated variables) into l
- * and the right into r 
+ * and the right into r.
  */
-void Block::split(Block *&l, Block *&r, Constraint *c) {
+void Block::split(Block* &l, Block* &r, Constraint* c) {
 	c->active=false;
 	l=new Block();
 	populateSplitBlock(l,c->left,c->right);
@@ -276,7 +384,7 @@ void Block::split(Block *&l, Block *&r, Constraint *c) {
  */
 double Block::cost() {
 	double c = 0;
-	for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
+	for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();++v) {
 		double diff = (*v)->position() - (*v)->desiredPosition;
 		c += (*v)->weight * diff * diff;
 	}
@@ -285,8 +393,11 @@ double Block::cost() {
 ostream& operator <<(ostream &os, const Block &b)
 {
 	os<<"Block:";
-	for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
+	for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();++v) {
 		os<<" "<<**v;
 	}
+	if(b.deleted) {
+		os<<" Deleted!";
+	}
     return os;
 }
diff --git a/src/removeoverlap/block.h b/src/removeoverlap/block.h
index 7905309bb..997009a55 100644
--- a/src/removeoverlap/block.h
+++ b/src/removeoverlap/block.h
@@ -1,12 +1,14 @@
 /**
- * \brief Remove overlaps function
+ * \brief A block is a group of variables that must be moved together to improve
+ * the goal function without violating already active constraints.
+ * The variables in a block are spanned by a tree of active constraints.
  *
  * 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.
  */
 
 #ifndef SEEN_REMOVEOVERLAP_BLOCK_H
@@ -29,16 +31,19 @@ public:
 	double wposn;
 	Block(Variable *v=NULL);
 	~Block(void);
-	Constraint *findMinLM();
-	Constraint *findMinInConstraint();
-	Constraint *findMinOutConstraint();
+	Constraint* findMinLM();
+	Constraint* findMinLMBetween(Variable* lv, Variable* rv);
+	Constraint* findMinInConstraint();
+	Constraint* findMinOutConstraint();
 	void deleteMinInConstraint();
 	void deleteMinOutConstraint();
 	double desiredWeightedPosition();
 	void merge(Block *b, Constraint *c, double dist);
+	void merge(Block *b, Constraint *c);
 	void mergeIn(Block *b);
 	void mergeOut(Block *b);
 	void split(Block *&l, Block *&r, Constraint *c);
+	Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
 	void setUpInConstraints();
 	void setUpOutConstraints();
 	double cost();
@@ -47,8 +52,12 @@ public:
 	PairingHeap<Constraint*> *in;
 	PairingHeap<Constraint*> *out;
 private:
+	typedef enum {NONE, LEFT, RIGHT} Direction;
+	typedef std::pair<double, Constraint*> Pair;
 	void reset_active_lm(Variable *v, Variable *u);
 	double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm);
+	Pair compute_dfdv_between(
+			Variable*, Variable*, Variable*, Direction, bool);
 	bool canFollowLeft(Constraint *c, Variable *last);
 	bool canFollowRight(Constraint *c, Variable *last);
 	void populateSplitBlock(Block *b, Variable *v, Variable *u);
diff --git a/src/removeoverlap/blocks.cpp b/src/removeoverlap/blocks.cpp
index 13da8e15e..62b7e99f5 100644
--- a/src/removeoverlap/blocks.cpp
+++ b/src/removeoverlap/blocks.cpp
@@ -10,7 +10,7 @@
  *
  * 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 "blocks.h"
@@ -30,7 +30,7 @@ using std::copy;
 
 long blockTimeCtr;
 
-Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) {
+Blocks::Blocks(const int n, Variable *vs[]) : vs(vs),nvs(n) {
 	blockTimeCtr=0;
 	for(int i=0;i<nvs;i++) {
 		insert(new Block(vs[i]));
@@ -39,7 +39,7 @@ Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) {
 Blocks::~Blocks(void)
 {
 	blockTimeCtr=0;
-	for(set<Block*>::iterator i=begin();i!=end();i++) {
+	for(set<Block*>::iterator i=begin();i!=end();++i) {
 		delete *i;
 	}
 	clear();
@@ -66,7 +66,7 @@ list<Variable*> *Blocks::totalOrder() {
 void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
 	v->visited=true;
 	vector<Constraint*>::iterator it=v->out.begin();
-	for(;it!=v->out.end();it++) {
+	for(;it!=v->out.end();++it) {
 		Constraint *c=*it;
 		if(!c->right->visited) {
 			dfsVisit(c->right, order);
@@ -149,9 +149,8 @@ void Blocks::removeBlock(Block *doomed) {
 	//erase(doomed);
 }
 void Blocks::cleanup() {
-	vector<Block*> bcopy(size());
-	copy(begin(),end(),bcopy.begin());
-	for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();i++) {
+	vector<Block*> bcopy(begin(),end());
+	for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
 		Block *b=*i;
 		if(b->deleted) {
 			erase(b);
@@ -189,7 +188,7 @@ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
  */
 double Blocks::cost() {
 	double c = 0;
-	for(set<Block*>::iterator i=begin();i!=end();i++) {
+	for(set<Block*>::iterator i=begin();i!=end();++i) {
 		c += (*i)->cost();
 	}
 	return c;
diff --git a/src/removeoverlap/blocks.h b/src/removeoverlap/blocks.h
index 437af6310..1a603eb41 100644
--- a/src/removeoverlap/blocks.h
+++ b/src/removeoverlap/blocks.h
@@ -1,12 +1,16 @@
 /**
- * \brief Remove overlaps function
+ * \brief A block structure defined over the variables
+ *
+ * A block structure defined over the variables such that each block contains
+ * 1 or more variables, with the invariant that all constraints inside a block
+ * are satisfied by keeping the variables fixed relative to one another
  *
  * 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.
  */
 
 #ifndef SEEN_REMOVEOVERLAP_BLOCKS_H
@@ -30,7 +34,7 @@ class Constraint;
 class Blocks : public std::set<Block*>
 {
 public:
-	Blocks(Variable *vs[], const int n);
+	Blocks(const int n, Variable *vs[]);
 	~Blocks(void);
 	void mergeLeft(Block *r);
 	void mergeRight(Block *l);
diff --git a/src/removeoverlap/constraint.cpp b/src/removeoverlap/constraint.cpp
index bb889c4d9..7c200878b 100644
--- a/src/removeoverlap/constraint.cpp
+++ b/src/removeoverlap/constraint.cpp
@@ -1,29 +1,47 @@
 /**
- * \brief Remove overlaps function
+ * \brief A constraint determines a minimum or exact spacing required between
+ * two variables.
  *
  * 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 "constraint.h"
 #include <cassert>
-Constraint::Constraint(Variable *left, Variable *right, double gap)
+Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality)
 : left(left),
   right(right),
   gap(gap),
   timeStamp(0),
   active(false),
-  visited(false)
+  visited(false),
+  equality(equality)
 {
 	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);
+}
 std::ostream& operator <<(std::ostream &os, const Constraint &c)
 {
-	os<<*c.left<<"+"<<c.gap<<"<="<<*c.right<<"("<<c.slack()<<"):lts="<<c.left->block->timeStamp<<",cts="<<c.timeStamp;
+	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;
 }
diff --git a/src/removeoverlap/constraint.h b/src/removeoverlap/constraint.h
index de8ccebd4..b207932b2 100644
--- a/src/removeoverlap/constraint.h
+++ b/src/removeoverlap/constraint.h
@@ -1,12 +1,13 @@
 /**
- * \brief Remove overlaps function
+ * \brief A constraint determines a minimum or exact spacing required between
+ * two variables.
  *
  * 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.
  */
 
 #ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H
@@ -23,13 +24,13 @@ public:
 	Variable *right;
 	double gap;
 	double lm;
-	Constraint(Variable *left, Variable *right, double gap);
-	~Constraint(void){};
-	inline double slack() const { return right->position() - gap - left->position(); }
-	//inline bool operator<(Constraint const &o) const { return slack() < o.slack(); }
+	Constraint(Variable *left, Variable *right, double gap, bool equality=false);
+	~Constraint();
+	inline double Constraint::slack() const { return right->position() - gap - left->position(); }
 	long timeStamp;
 	bool active;
 	bool visited;
+	bool equality;
 };
 #include <float.h>
 #include "block.h"
diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp
index a8bfe28e7..312ad960b 100644
--- a/src/removeoverlap/generate-constraints.cpp
+++ b/src/removeoverlap/generate-constraints.cpp
@@ -1,12 +1,13 @@
 /**
- * \brief Remove overlaps function
+ * \brief Functions to automatically generate constraints for the
+ * rectangular node overlap removal 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 <set>
@@ -58,11 +59,11 @@ struct Node {
 	void setNeighbours(NodeSet *left, NodeSet *right) {
 		leftNeighbours=left;
 		rightNeighbours=right;
-		for(NodeSet::iterator i=left->begin();i!=left->end();i++) {
+		for(NodeSet::iterator i=left->begin();i!=left->end();++i) {
 			Node *v=*(i);
 			v->addRightNeighbour(this);
 		}
-		for(NodeSet::iterator i=right->begin();i!=right->end();i++) {
+		for(NodeSet::iterator i=right->begin();i!=right->end();++i) {
 			Node *v=*(i);
 			v->addLeftNeighbour(this);
 		}
@@ -116,7 +117,7 @@ NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
 NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
 	NodeSet *rightv = new NodeSet;
 	NodeSet::iterator i=scanline.find(v);
-	for(i++;i!=scanline.end(); i++) {
+	for(++i;i!=scanline.end(); ++i) {
 		Node *u=*(i);
 		if(u->r->overlapX(v->r)<=0) {
 			rightv->insert(u);
@@ -159,17 +160,15 @@ int compare_events(const void *a, const void *b) {
 }
 
 /**
- * Prepares variables and constraints in order to apply VPSC horizontally.
+ * Prepares constraints in order to apply VPSC horizontally.  Assumes variables have already been created.
  * useNeighbourLists determines whether or not a heuristic is used to deciding whether to resolve
  * all overlap in the x pass, or leave some overlaps for the y pass.
  */
-int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs, bool useNeighbourLists) {
+int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) {
 	events=new Event*[2*n];
 	int i,m,ctr=0;
-	vector<Constraint*> constraints;
-	vars=new Variable*[n];
 	for(i=0;i<n;i++) {
-		vars[i]=new Variable(i,rs[i]->getCentreX(),weights[i]);
+		vars[i]->desiredPosition=rs[i]->getCentreX();
 		Node *v = new Node(vars[i],rs[i],rs[i]->getCentreX());
 		events[ctr++]=new Event(Open,v,rs[i]->getMinY());
 		events[ctr++]=new Event(Close,v,rs[i]->getMaxY());
@@ -177,6 +176,7 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl
 	qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
 
 	NodeSet scanline;
+	vector<Constraint*> constraints;
 	for(i=0;i<2*n;i++) {
 		Event *e=events[i];
 		Node *v=e->v;
@@ -247,21 +247,20 @@ int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variabl
 }
 
 /**
- * Prepares variables and constraints in order to apply VPSC vertically to remove ALL overlap.
+ * Prepares constraints in order to apply VPSC vertically to remove ALL overlap.
  */
-int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vars, Constraint **&cs) {
+int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) {
 	events=new Event*[2*n];
 	int ctr=0,i,m;
-	vector<Constraint*> constraints;
-	vars=new Variable*[n];
 	for(i=0;i<n;i++) {
-		vars[i]=new Variable(i,rs[i]->getCentreY(),weights[i]);
+		vars[i]->desiredPosition=rs[i]->getCentreY();
 		Node *v = new Node(vars[i],rs[i],rs[i]->getCentreY());
 		events[ctr++]=new Event(Open,v,rs[i]->getMinX());
 		events[ctr++]=new Event(Close,v,rs[i]->getMaxX());
 	}
 	qsort((Event*)events, (size_t)2*n, sizeof(Event*), compare_events );
 	NodeSet scanline;
+	vector<Constraint*> constraints;
 	for(i=0;i<2*n;i++) {
 		Event *e=events[i];
 		Node *v=e->v;
diff --git a/src/removeoverlap/generate-constraints.h b/src/removeoverlap/generate-constraints.h
index ad9ccb1f9..56ee9536a 100644
--- a/src/removeoverlap/generate-constraints.h
+++ b/src/removeoverlap/generate-constraints.h
@@ -1,14 +1,14 @@
 /**
- * \brief Remove overlaps function
+ * \brief Functions to automatically generate constraints for the
+ * rectangular node overlap removal 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.
  */
-
 #ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
 #define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
 #include <iostream>
@@ -71,8 +71,8 @@ class Variable;
 class Constraint;
 
 // returns number of constraints generated
-int generateXConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs,bool useNeighbourLists);
+int generateXConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists);
+int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs);
 
-int generateYConstraints(Rectangle *rs[], double weights[], const int n, Variable **&vs, Constraint **&cs);
 
 #endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
diff --git a/src/removeoverlap/remove_rectangle_overlap-test.cpp b/src/removeoverlap/remove_rectangle_overlap-test.cpp
index 9999d027e..87cf4cbb0 100644
--- a/src/removeoverlap/remove_rectangle_overlap-test.cpp
+++ b/src/removeoverlap/remove_rectangle_overlap-test.cpp
@@ -60,7 +60,7 @@ test_case(unsigned const n_rects, double const rect2coords[][4])
                               rect2coords[i][2],
                               rect2coords[i][3]);
     }
-    removeRectangleOverlap(rs, n_rects, 0.0, 0.0);
+    removeRectangleOverlap(n_rects,rs,0.0, 0.0);
     for (unsigned i = 0; i < n_rects; ++i) {
         UTEST_ASSERT(possibly_eq(rs[i]->width(), (rect2coords[i][1] -
                                                   rect2coords[i][0]  )));
diff --git a/src/removeoverlap/remove_rectangle_overlap.cpp b/src/removeoverlap/remove_rectangle_overlap.cpp
index 9f98d5811..6f6ace03a 100755
--- a/src/removeoverlap/remove_rectangle_overlap.cpp
+++ b/src/removeoverlap/remove_rectangle_overlap.cpp
@@ -1,3 +1,14 @@
+/**
+ * \brief remove overlaps between a set of rectangles.
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+
 #include <iostream>
 #include <cassert>
 #include "generate-constraints.h"
@@ -28,24 +39,23 @@ double Rectangle::yBorder=0;
  *    x-positions - this corrects the case where rectangles were moved 
  *    too much in the first pass.
  */
-void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBorder) {
+void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) {
 	assert(0 <= n);
 	try {
 	// The extra gap avoids numerical imprecision problems
 	Rectangle::setXBorder(xBorder+EXTRA_GAP);
 	Rectangle::setYBorder(yBorder+EXTRA_GAP);
-	double *ws=new double[n];
+	Variable **vs=new Variable*[n];
 	for(int i=0;i<n;i++) {
-		ws[i]=1;
+		vs[i]=new Variable(i,0,1);
 	}
-	Variable **vs;
 	Constraint **cs;
 	double *oldX = new double[n];
-	int m=generateXConstraints(rs,ws,n,vs,cs,true);
+	int m=generateXConstraints(n,rs,vs,cs,true);
 	for(int i=0;i<n;i++) {
 		oldX[i]=vs[i]->desiredPosition;
 	}
-	VPSC vpsc_x(vs,n,cs,m);
+	VPSC vpsc_x(n,vs,m,cs);
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
 	f<<"Calling VPSC: Horizontal pass 1"<<endl;
@@ -54,9 +64,7 @@ void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBord
 	vpsc_x.solve();
 	for(int i=0;i<n;i++) {
 		rs[i]->moveCentreX(vs[i]->position());
-		delete vs[i];
 	}
-	delete [] vs;
 	for(int i = 0; i < m; ++i) {
 		delete cs[i];
 	}
@@ -64,8 +72,8 @@ void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBord
 	// Removing the extra gap here ensures things that were moved to be adjacent to
 	// one another above are not considered overlapping
 	Rectangle::setXBorder(Rectangle::xBorder-EXTRA_GAP);
-	m=generateYConstraints(rs,ws,n,vs,cs);
-	VPSC vpsc_y(vs,n,cs,m);
+	m=generateYConstraints(n,rs,vs,cs);
+	VPSC vpsc_y(n,vs,m,cs);
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	f.open(LOGFILE,ios::app);
 	f<<"Calling VPSC: Vertical pass"<<endl;
@@ -75,34 +83,31 @@ void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBord
 	for(int i=0;i<n;i++) {
 		rs[i]->moveCentreY(vs[i]->position());
 		rs[i]->moveCentreX(oldX[i]);
-		delete vs[i];
 	}
-	delete [] vs;
 	delete [] oldX;
 	for(int i = 0; i < m; ++i) {
 		delete cs[i];
 	}
 	delete [] cs;
 	Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
-	m=generateXConstraints(rs,ws,n,vs,cs,false);
-	VPSC vpsc_x2(vs,n,cs,m);
+	m=generateXConstraints(n,rs,vs,cs,false);
+	VPSC vpsc_x2(n,vs,m,cs);
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	f.open(LOGFILE,ios::app);
 	f<<"Calling VPSC: Horizontal pass 2"<<endl;
 	f.close();
 #endif
 	vpsc_x2.solve();
+	for(int i = 0; i < m; ++i) {
+		delete cs[i];
+	}
+	delete [] cs;
 	for(int i=0;i<n;i++) {
 		rs[i]->moveCentreX(vs[i]->position());
 		delete vs[i];
 	}
 	delete [] vs;
-	for(int i = 0; i < m; ++i) {
-		delete cs[i];
-	}
-	delete [] cs;
-	delete [] ws;
-	} catch (char *str) {
+	} catch (char const *str) {
 		std::cerr<<str<<std::endl;
 		for(int i=0;i<n;i++) {
 			std::cerr << *rs[i]<<std::endl;
diff --git a/src/removeoverlap/remove_rectangle_overlap.h b/src/removeoverlap/remove_rectangle_overlap.h
index 9dc84f83a..08b035e31 100755
--- a/src/removeoverlap/remove_rectangle_overlap.h
+++ b/src/removeoverlap/remove_rectangle_overlap.h
@@ -10,12 +10,12 @@
  *
  * 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.
  */
 
 class Rectangle;
 
-void removeRectangleOverlap(Rectangle *rs[], int n, double xBorder, double yBorder);
+void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder);
 
 
 #endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */
diff --git a/src/removeoverlap/removeoverlap.cpp b/src/removeoverlap/removeoverlap.cpp
index 9d7beb45f..d79fa9eab 100644
--- a/src/removeoverlap/removeoverlap.cpp
+++ b/src/removeoverlap/removeoverlap.cpp
@@ -7,7 +7,7 @@
 *
 * 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 "util/glib-list-iterators.h"
 #include "sp-item.h"
@@ -29,7 +29,7 @@ void removeoverlap(GSList const *const items, double const xGap, double const yG
 	std::list<SPItem *> selected;
 	selected.insert<GSListConstIterator<SPItem *> >(selected.end(), items, NULL);
 	if (selected.empty()) return;
-	int n=selected.size();
+	unsigned n=selected.size();
 
 	//Check 2 or more selected objects
 	if (n < 2) return;
@@ -62,7 +62,7 @@ void removeoverlap(GSList const *const items, double const xGap, double const yG
 		rs[i++] = new Rectangle(min[X], max[X],
 					min[Y], max[Y]);
 	}
-	removeRectangleOverlap(rs, n, 0.0, 0.0);
+	removeRectangleOverlap(n, rs, 0.0, 0.0);
 	i=0;
 	for (std::list<SPItem *>::iterator it(selected.begin());
 		it != selected.end();
diff --git a/src/removeoverlap/removeoverlap.h b/src/removeoverlap/removeoverlap.h
index b904f52f1..2fb26e794 100644
--- a/src/removeoverlap/removeoverlap.h
+++ b/src/removeoverlap/removeoverlap.h
@@ -6,7 +6,7 @@
  *
  * 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.
  */
 
 #ifndef SEEN_REMOVEOVERLAP_H
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;
 }
-*/
 
diff --git a/src/removeoverlap/solve_VPSC.h b/src/removeoverlap/solve_VPSC.h
index c7da502fb..9f6244a5a 100644
--- a/src/removeoverlap/solve_VPSC.h
+++ b/src/removeoverlap/solve_VPSC.h
@@ -1,17 +1,18 @@
 /**
-* \brief Remove overlaps function
-*
-* Authors:
-*   Tim Dwyer <tgdwyer@gmail.com>
-*
-* Copyright (C) 2005 Authors
-*
-* Released under GNU GPL.  Read the file 'COPYING' for more information.
-*/
-
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
 #ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
 #define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
 
+#include <vector>
 class Variable;
 class Constraint;
 class Blocks;
@@ -21,21 +22,36 @@ class Blocks;
  */
 class VPSC {
 public:
-	void satisfy();
-	void solve();
+	virtual void satisfy();
+	virtual void solve();
 
-	void move_and_split();
-	VPSC(Variable *vs[], const int n, Constraint *cs[], const int m);
-	~VPSC();
+	VPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]);
+	virtual ~VPSC();
+	Constraint** getConstraints() { return cs; }
+	Variable** getVariables() { return vs; }
 protected:
 	Blocks *bs;
-	void refine();
-private:
+	Constraint **cs;
+	unsigned m;
+	Variable **vs;
 	void printBlocks();
-	bool constraintGraphIsCyclic(Variable *vs[], const int n);
+private:
+	void refine();
+	bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]);
 	bool blockGraphIsCyclic();
-	Constraint **cs;
-	int m;
 };
 
+class IncVPSC : public VPSC {
+public:
+	unsigned splitCnt;
+	void satisfy();
+	void solve();
+	void moveBlocks();
+	void splitBlocks();
+	IncVPSC(const unsigned n, Variable *vs[], const unsigned m, Constraint *cs[]);
+private:
+	typedef std::vector<Constraint*> ConstraintList;
+	ConstraintList inactive;
+	Constraint* mostViolated(ConstraintList &l);
+};
 #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
diff --git a/src/removeoverlap/variable.cpp b/src/removeoverlap/variable.cpp
index 0cf2e28a7..1890f788e 100644
--- a/src/removeoverlap/variable.cpp
+++ b/src/removeoverlap/variable.cpp
@@ -1,12 +1,11 @@
 /**
- * \brief Remove overlaps function
  *
  * 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 "variable.h"
 std::ostream& operator <<(std::ostream &os, const Variable &v) {
@@ -14,7 +13,3 @@ std::ostream& operator <<(std::ostream &os, const Variable &v) {
 	return os;
 }
 
-#include "block.h"
-double Variable::position() const {
-	return block->posn+offset;
-}
diff --git a/src/removeoverlap/variable.h b/src/removeoverlap/variable.h
index e682dd7df..86e16737e 100644
--- a/src/removeoverlap/variable.h
+++ b/src/removeoverlap/variable.h
@@ -1,14 +1,12 @@
 /**
- * \brief Remove overlaps function
  *
  * 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.
  */
-
 #ifndef SEEN_REMOVEOVERLAP_VARIABLE_H
 #define SEEN_REMOVEOVERLAP_VARIABLE_H
 
@@ -16,30 +14,35 @@
 #include <iostream>
 class Block;
 class Constraint;
+#include "block.h"
 
+typedef std::vector<Constraint*> Constraints;
 class Variable
 {
 	friend std::ostream& operator <<(std::ostream &os, const Variable &v);
 public:
-	static const unsigned int _TOSTRINGBUFFSIZE=20;
 	const int id; // useful in log files
 	double desiredPosition;
 	const double weight;
 	double offset;
 	Block *block;
 	bool visited;
-	std::vector<Constraint*> in;
-	std::vector<Constraint*> out;
+	Constraints in;
+	Constraints out;
 	char *toString();
 	inline Variable(const int id, const double desiredPos, const double weight)
 		: id(id)
 		, desiredPosition(desiredPos)
 		, weight(weight)
 		, offset(0)
+		, block(NULL)
 		, visited(false)
 	{
 	}
-	double position() const;
+	inline double Variable::position() const {
+		return block->posn+offset;
+	}
+	//double position() const;
 	~Variable(void){
 		in.clear();
 		out.clear();