merged with trunk so I can build again...

(bzr r10092.1.36)

19 files changed, 283 insertions, 191 deletions

diff --git a/src/libvpsc/CMakeLists.txt b/src/libvpsc/CMakeLists.txt
index 4c3398b0f..4099900b5 100644
--- a/src/libvpsc/CMakeLists.txt
+++ b/src/libvpsc/CMakeLists.txt
@@ -1,13 +1,29 @@
-SET(libvpsc_SRC

-block.cpp

-blocks.cpp

-constraint.cpp

-csolve_VPSC.cpp

-generate-constraints.cpp

-remove_rectangle_overlap.cpp

-solve_VPSC.cpp

-variable.cpp

-)

-ADD_LIBRARY(vpsc STATIC ${libvpsc_SRC})

-TARGET_LINK_LIBRARIES(vpsc

-${INKSCAPE_LIBS})
\ No newline at end of file
+
+set(libvpsc_SRC
+	block.cpp
+	blocks.cpp
+	constraint.cpp
+	csolve_VPSC.cpp
+	generate-constraints.cpp
+	remove_rectangle_overlap.cpp
+	solve_VPSC.cpp
+	variable.cpp
+	pairingheap/PairingHeap.cpp
+
+
+	# -------
+	# Headers
+	block.h
+	blocks.h
+	constraint.h
+	csolve_VPSC.h
+	generate-constraints.h
+	pairingheap/PairingHeap.h
+	pairingheap/dsexceptions.h
+	placement_SolveVPSC.h
+	remove_rectangle_overlap.h
+	solve_VPSC.h
+	variable.h
+)
+
+add_inkscape_lib(vpsc_LIB "${libvpsc_SRC}")
diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp
index 221df536a..8171780d4 100644
--- a/src/libvpsc/block.cpp
+++ b/src/libvpsc/block.cpp
@@ -1,8 +1,4 @@
-/**
- * \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>
  *
@@ -72,7 +68,7 @@ void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
 		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) {
+			if ((c->left->block != this && in) || (c->right->block != this && !in)) {
 				h->insert(c);
 			}
 		}
@@ -95,13 +91,7 @@ void Block::merge(Block* b, Constraint* c) {
 	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
- * @param b block to merge into this
- * @param c constraint being merged
- * @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);
@@ -317,10 +307,7 @@ void Block::reset_active_lm(Variable* const v, Variable* const u) {
 		}
 	}
 }
-/**
- * finds the constraint with the minimum lagrange multiplier, that is, the constraint
- * that most wants to split
- */
+
 Constraint *Block::findMinLM() {
 	Constraint *min_lm=NULL;
 	reset_active_lm(vars->front(),NULL);
@@ -363,12 +350,7 @@ bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) {
 	}
 	return false;
 }
-/**
- * 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* const vl, Variable* const vr,
 	       	Block* &lb, Block* &rb) {
 #ifdef RECTANGLE_OVERLAP_LOGGING
@@ -383,11 +365,7 @@ Constraint* Block::splitBetween(Variable* const vl, Variable* const vr,
 	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.
- */
+
 void Block::split(Block* &l, Block* &r, Constraint* c) {
 	c->active=false;
 	l=new Block();
@@ -396,10 +374,6 @@ void Block::split(Block* &l, Block* &r, Constraint* c) {
 	populateSplitBlock(r,c->right,c->left);
 }
 
-/**
- * Computes the cost (squared euclidean distance from desired positions) of the
- * current positions for variables in this block
- */
 double Block::cost() {
 	double c = 0;
 	for (Vit v=vars->begin();v!=vars->end();++v) {
diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h
index fe4a18b78..9c90fc87e 100644
--- a/src/libvpsc/block.h
+++ b/src/libvpsc/block.h
@@ -1,8 +1,4 @@
-/**
- * \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>
  *
@@ -21,6 +17,11 @@ namespace vpsc {
 class Variable;
 class Constraint;
 
+/**
+ * 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.
+ */
 class Block
 {
 	typedef std::vector<Variable*> Variables;
@@ -35,22 +36,57 @@ public:
 	double wposn;
 	Block(Variable* const v=NULL);
     virtual ~Block(void);
-	Constraint* findMinLM();
+
+    /**
+     * finds the constraint with the minimum lagrange multiplier, that is, the constraint
+     * that most wants to split
+     */
+    Constraint* findMinLM();
+
 	Constraint* findMinLMBetween(Variable* const lv, Variable* const rv);
 	Constraint* findMinInConstraint();
 	Constraint* findMinOutConstraint();
 	void deleteMinInConstraint();
 	void deleteMinOutConstraint();
 	double desiredWeightedPosition();
-	void merge(Block *b, Constraint *c, double dist);
+
+    /**
+     * Merges b into this block across c.  Can be either a
+     * right merge or a left merge
+     * @param b block to merge into this
+     * @param c constraint being merged
+     * @param distance separation required to satisfy c
+     */
+    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);
+
+    /**
+     * 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.
+     */
+    void split(Block *&l, Block *&r, Constraint *c);
+
+    /**
+     * 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* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
+
 	void setUpInConstraints();
 	void setUpOutConstraints();
-	double cost();
+
+    /**
+     * Computes the cost (squared euclidean distance from desired positions) of the
+     * current positions for variables in this block
+     */
+    double cost();
+
 	bool deleted;
 	long timeStamp;
 	PairingHeap<Constraint*> *in;
@@ -74,3 +110,13 @@ private:
 
 }
 #endif // SEEN_REMOVEOVERLAP_BLOCK_H
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp
index fe0caacfc..7eff1e6c4 100644
--- a/src/libvpsc/blocks.cpp
+++ b/src/libvpsc/blocks.cpp
@@ -1,9 +1,5 @@
-/**
- * \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
+/*
+ * A block structure defined over the variables.
  *
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
@@ -47,10 +43,6 @@ Blocks::~Blocks(void)
 	clear();
 }
 
-/**
- * returns a list of variables with total ordering determined by the constraint 
- * DAG
- */
 list<Variable*> *Blocks::totalOrder() {
 	list<Variable*> *order = new list<Variable*>;
 	for(int i=0;i<nvs;i++) {
@@ -80,10 +72,7 @@ void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
 #endif
 	order->push_front(v);
 }
-/**
- * Processes incoming constraints, most violated to least, merging with the
- * neighbouring (left) block until no more violated constraints are found
- */
+
 void Blocks::mergeLeft(Block *r) {	
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
@@ -115,9 +104,7 @@ void Blocks::mergeLeft(Block *r) {
 	f<<"merged "<<*r<<endl;
 #endif
 }	
-/**
- * Symmetrical to mergeLeft
- */
+
 void Blocks::mergeRight(Block *l) {	
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
@@ -160,10 +147,7 @@ void Blocks::cleanup() {
 		}
 	}
 }
-/**
- * Splits block b across constraint c into two new blocks, l and r (c's left
- * and right sides respectively)
- */
+
 void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
 	b->split(l,r,c);
 #ifdef RECTANGLE_OVERLAP_LOGGING
@@ -184,10 +168,7 @@ void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
 	insert(l);
 	insert(r);
 }
-/**
- * returns the cost total squared distance of variables from their desired
- * positions
- */
+
 double Blocks::cost() {
 	double c = 0;
 	for(set<Block*>::iterator i=begin();i!=end();++i) {
diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h
index bfe99f271..b711a529f 100644
--- a/src/libvpsc/blocks.h
+++ b/src/libvpsc/blocks.h
@@ -1,10 +1,4 @@
-/**
- * \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>
  *
@@ -24,32 +18,77 @@
 #include <list>
 
 namespace vpsc {
+
 class Block;
 class Variable;
 class Constraint;
+
 /**
  * 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
+ * are satisfied by keeping the variables fixed relative to one another.
+ *
+ * @todo check on this class being copy-n-paste duplicated.
  */
 class Blocks : public std::set<Block*>
 {
 public:
-	Blocks(const int n, Variable* const vs[]);
+    Blocks(const int n, Variable* const vs[]);
+
     virtual ~Blocks(void);
-	void mergeLeft(Block *r);
-	void mergeRight(Block *l);
-	void split(Block *b, Block *&l, Block *&r, Constraint *c);
-	std::list<Variable*> *totalOrder();
-	void cleanup();
-	double cost();
+
+    /**
+     * Processes incoming constraints, most violated to least, merging with the
+     * neighbouring (left) block until no more violated constraints are found.
+     */
+    void mergeLeft(Block *r);
+
+    /**
+     * Symmetrical to mergeLeft.
+     * @see mergeLeft
+     */
+    void mergeRight(Block *l);
+
+    /**
+     * Splits block b across constraint c into two new blocks, l and r (c's left
+     * and right sides respectively).
+     */
+    void split(Block *b, Block *&l, Block *&r, Constraint *c);
+
+    /**
+     * Returns a list of variables with total ordering determined by the constraint 
+     * DAG.
+     */
+    std::list<Variable*> *totalOrder();
+
+    void cleanup();
+
+    /**
+     * Returns the cost total squared distance of variables from their desired
+     * positions.
+     */
+    double cost();
+
 private:
-	void dfsVisit(Variable *v, std::list<Variable*> *order);
-	void removeBlock(Block *doomed);
-	Variable* const *vs;
-	int nvs;
+    void dfsVisit(Variable *v, std::list<Variable*> *order);
+
+    void removeBlock(Block *doomed);
+
+    Variable* const *vs;
+
+    int nvs;
 };
 
 extern long blockTimeCtr;
 }
 #endif // SEEN_REMOVEOVERLAP_BLOCKS_H
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp
index af5da941a..2bd173155 100644
--- a/src/libvpsc/constraint.cpp
+++ b/src/libvpsc/constraint.cpp
@@ -1,7 +1,4 @@
-/**
- * \brief A constraint determines a minimum or exact spacing required between
- * two variables.
- *
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *
diff --git a/src/libvpsc/constraint.h b/src/libvpsc/constraint.h
index 8a8529d7e..a3173359c 100644
--- a/src/libvpsc/constraint.h
+++ b/src/libvpsc/constraint.h
@@ -1,7 +1,4 @@
-/**
- * \brief A constraint determines a minimum or exact spacing required between
- * two variables.
- *
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *
@@ -17,6 +14,11 @@
 #include "variable.h"
 namespace vpsc {
 
+/**
+ * A constraint determines a minimum or exact spacing required between
+ * two variables.
+ *
+ */
 class Constraint
 {
 	friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
diff --git a/src/libvpsc/csolve_VPSC.cpp b/src/libvpsc/csolve_VPSC.cpp
index 5176242d5..24459d09f 100644
--- a/src/libvpsc/csolve_VPSC.cpp
+++ b/src/libvpsc/csolve_VPSC.cpp
@@ -1,5 +1,5 @@
-/**
- * \brief Bridge for C programs to access solve_VPSC (which is in C++)
+/*
+ * Bridge for C programs to access solve_VPSC (which is in C++).
  *
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
diff --git a/src/libvpsc/csolve_VPSC.h b/src/libvpsc/csolve_VPSC.h
index 81e50d990..92179fc77 100644
--- a/src/libvpsc/csolve_VPSC.h
+++ b/src/libvpsc/csolve_VPSC.h
@@ -1,6 +1,8 @@
 /**
- * \brief Bridge for C programs to access solve_VPSC (which is in C++)
- *
+ * @file
+ * Bridge for C programs to access solve_VPSC (which is in C++).
+ */
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *
diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp
index c57966e26..8dd2d9331 100644
--- a/src/libvpsc/generate-constraints.cpp
+++ b/src/libvpsc/generate-constraints.cpp
@@ -1,6 +1,9 @@
 /**
- * \brief Functions to automatically generate constraints for the
+ * @file
+ * Functions to automatically generate constraints for the
  * rectangular node overlap removal problem.
+ */
+/*
  *
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
@@ -16,7 +19,7 @@
 #include "generate-constraints.h"
 #include "constraint.h"
 
-#include "2geom/isnan.h" /* Include last */
+#include <2geom/math-utils.h>
 
 using std::set;
 using std::vector;
diff --git a/src/libvpsc/generate-constraints.h b/src/libvpsc/generate-constraints.h
index 8b858af3f..b8d7cdcd9 100644
--- a/src/libvpsc/generate-constraints.h
+++ b/src/libvpsc/generate-constraints.h
@@ -1,6 +1,10 @@
 /**
- * \brief Functions to automatically generate constraints for the
+ * @file
+ * Functions to automatically generate constraints for the
  * rectangular node overlap removal problem.
+ */
+/* TODO replace file comment with appropriate doc comment on vpsc::Rectangle */
+/*
  *
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
diff --git a/src/libvpsc/pairingheap/PairingHeap.cpp b/src/libvpsc/pairingheap/PairingHeap.cpp
index 202980b70..6e003f99c 100644
--- a/src/libvpsc/pairingheap/PairingHeap.cpp
+++ b/src/libvpsc/pairingheap/PairingHeap.cpp
@@ -1,12 +1,14 @@
 /**
- * \brief Pairing heap datastructure implementation
+ * @file
+ * Pairing heap datastructure implementation.
  *
  * Based on example code in "Data structures and Algorithm Analysis in C++"
  * by Mark Allen Weiss, used and released under the LGPL by permission
  * of the author.
  *
  * No promises about correctness.  Use at your own risk!
- *
+ */
+/*
  * Authors:
  *   Mark Allen Weiss
  *   Tim Dwyer <tgdwyer@gmail.com>
diff --git a/src/libvpsc/pairingheap/PairingHeap.h b/src/libvpsc/pairingheap/PairingHeap.h
index 6159e96c1..62c782d5d 100644
--- a/src/libvpsc/pairingheap/PairingHeap.h
+++ b/src/libvpsc/pairingheap/PairingHeap.h
@@ -1,10 +1,4 @@
-/**
- * \brief Pairing heap datastructure implementation
- *
- * Based on example code in "Data structures and Algorithm Analysis in C++"
- * by Mark Allen Weiss, used and released under the LGPL by permission
- * of the author.
- *
+/*
  * No promises about correctness.  Use at your own risk!
  *
  * Authors:
@@ -67,6 +61,13 @@ public:
 	virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
 };
 
+/**
+ * Pairing heap datastructure implementation.
+ *
+ * Based on example code in "Data structures and Algorithm Analysis in C++"
+ * by Mark Allen Weiss, used and released under the LGPL by permission
+ * of the author.
+ */
 template <class T>
 class PairingHeap
 {
diff --git a/src/libvpsc/remove_rectangle_overlap.cpp b/src/libvpsc/remove_rectangle_overlap.cpp
index 4d2750b9e..381759f3c 100644
--- a/src/libvpsc/remove_rectangle_overlap.cpp
+++ b/src/libvpsc/remove_rectangle_overlap.cpp
@@ -1,5 +1,5 @@
-/** @file
- * @brief remove overlaps between a set of rectangles.
+/*
+ * remove overlaps between a set of rectangles.
  *
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
@@ -28,18 +28,7 @@ using namespace vpsc;
 
 double Rectangle::xBorder=0;
 double Rectangle::yBorder=0;
-/**
- * Takes an array of n rectangles and moves them as little as possible
- * such that rectangles are separated by at least xBorder horizontally
- * and yBorder vertically
- *
- * Works in three passes: 
- * 1) removes some overlap horizontally
- * 2) removes remaining overlap vertically
- * 3) a last horizontal pass removes all overlap starting from original
- *    x-positions - this corrects the case where rectangles were moved 
- *    too much in the first pass.
- */
+
 void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder) {
 	try {
 	// The extra gap avoids numerical imprecision problems
diff --git a/src/libvpsc/remove_rectangle_overlap.h b/src/libvpsc/remove_rectangle_overlap.h
index 1af90a754..3e2f4cc8f 100644
--- a/src/libvpsc/remove_rectangle_overlap.h
+++ b/src/libvpsc/remove_rectangle_overlap.h
@@ -1,5 +1,5 @@
-/** @file
- * @brief Declaration of main internal remove-overlaps function.
+/*
+ * Declaration of main internal remove-overlaps function.
  */
 /* Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
@@ -16,6 +16,18 @@ namespace vpsc {
 	class Rectangle;
 }
 
+/**
+ * Takes an array of n rectangles and moves them as little as possible
+ * such that rectangles are separated by at least xBorder horizontally
+ * and yBorder vertically
+ *
+ * Works in three passes: 
+ * 1) removes some overlap horizontally
+ * 2) removes remaining overlap vertically
+ * 3) a last horizontal pass removes all overlap starting from original
+ *    x-positions - this corrects the case where rectangles were moved 
+ *    too much in the first pass.
+ */
 void removeRectangleOverlap(unsigned n, vpsc::Rectangle *rs[], double xBorder, double yBorder);
 
 
diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp
index ec2c48d46..f9bed649c 100644
--- a/src/libvpsc/solve_VPSC.cpp
+++ b/src/libvpsc/solve_VPSC.cpp
@@ -1,5 +1,5 @@
-/**
- * \brief Solve an instance of the "Variable Placement with Separation
+/*
+ * Solve an instance of the "Variable Placement with Separation
  * Constraints" problem.
  *
  * Authors:
@@ -59,16 +59,7 @@ void Solver::printBlocks() {
 	}
 #endif
 }
-/**
-* Produces a feasible - though not necessarily optimal - solution by
-* examining blocks in the partial order defined by the directed acyclic
-* graph of constraints. For each block (when processing left to right) we
-* maintain the invariant that all constraints to the left of the block
-* (incoming constraints) are satisfied. This is done by repeatedly merging
-* blocks into bigger blocks across violated constraints (most violated
-* first) fixing the position of variables inside blocks relative to one
-* another so that constraints internal to the block are satisfied.
-*/
+
 void Solver::satisfy() {
 	list<Variable*> *vs=bs->totalOrder();
 	for(list<Variable*>::iterator i=vs->begin();i!=vs->end();++i) {
@@ -129,12 +120,7 @@ void Solver::refine() {
 		}
 	}
 }
-/**
- * Calculate the optimal solution. After using satisfy() to produce a
- * feasible solution, refine() examines each block to see if further
- * refinement is possible by splitting the block. This is done repeatedly
- * until no further improvement is possible.
- */
+
 void Solver::solve() {
 	satisfy();
 	refine();
@@ -156,19 +142,7 @@ void IncSolver::solve() {
 #endif
 	} while(fabs(lastcost-cost)>0.0001);
 }
-/**
- * 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 IncSolver::satisfy() {
 #ifdef RECTANGLE_OVERLAP_LOGGING
 	ofstream f(LOGFILE,ios::app);
@@ -270,10 +244,6 @@ void IncSolver::splitBlocks() {
 	bs->cleanup();
 }
 
-/**
- * Scan constraint list for the most violated constraint, or the first equality
- * constraint
- */
 Constraint* IncSolver::mostViolated(ConstraintList &l) {
 	double minSlack = DBL_MAX;
 	Constraint* v=NULL;
diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h
index 0f919a22a..e416ef9c6 100644
--- a/src/libvpsc/solve_VPSC.h
+++ b/src/libvpsc/solve_VPSC.h
@@ -1,7 +1,9 @@
 /**
- * \brief Solve an instance of the "Variable Placement with Separation
+ * @file
+ * Solve an instance of the "Variable Placement with Separation
  * Constraints" problem.
- *
+ */
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *
@@ -32,8 +34,26 @@ class Blocks;
  */
 class Solver {
 public:
-	virtual void satisfy();
-	virtual void solve();
+
+    /**
+     * Produces a feasible - though not necessarily optimal - solution by
+     * examining blocks in the partial order defined by the directed acyclic
+     * graph of constraints. For each block (when processing left to right) we
+     * maintain the invariant that all constraints to the left of the block
+     * (incoming constraints) are satisfied. This is done by repeatedly merging
+     * blocks into bigger blocks across violated constraints (most violated
+     * first) fixing the position of variables inside blocks relative to one
+     * another so that constraints internal to the block are satisfied.
+     */
+    virtual void satisfy();
+
+    /**
+     * Calculate the optimal solution. After using satisfy() to produce a
+     * feasible solution, refine() examines each block to see if further
+     * refinement is possible by splitting the block. This is done repeatedly
+     * until no further improvement is possible.
+     */
+    virtual void solve();
 
 	Solver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
 	virtual ~Solver();
@@ -54,16 +74,51 @@ private:
 
 class IncSolver : public Solver {
 public:
-	unsigned splitCnt;
-	void satisfy();
-	void solve();
-	void moveBlocks();
-	void splitBlocks();
-	IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
+    unsigned splitCnt;
+
+    /**
+     * 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 satisfy();
+
+    void solve();
+
+    void moveBlocks();
+
+    void splitBlocks();
+
+    IncSolver(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
 private:
-	typedef std::vector<Constraint*> ConstraintList;
-	ConstraintList inactive;
-	Constraint* mostViolated(ConstraintList &l);
+
+    typedef std::vector<Constraint*> ConstraintList;
+
+    ConstraintList inactive;
+
+    /**
+     * Scan constraint list for the most violated constraint, or the first equality
+     * constraint.
+     */
+    Constraint* mostViolated(ConstraintList &l);
 };
 }
 #endif // SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/libvpsc/variable.cpp b/src/libvpsc/variable.cpp
index 19dc0746a..29bf8dc5c 100644
--- a/src/libvpsc/variable.cpp
+++ b/src/libvpsc/variable.cpp
@@ -1,5 +1,4 @@
-/**
- *
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *
@@ -8,6 +7,7 @@
  * Released under GNU LGPL.  Read the file 'COPYING' for more information.
  */
 #include "variable.h"
+
 namespace vpsc {
 std::ostream& operator <<(std::ostream &os, const Variable &v) {
 	os << "(" << v.id << "=" << v.position() << ")";
diff --git a/src/libvpsc/variable.h b/src/libvpsc/variable.h
index 25239ff20..022754a7d 100644
--- a/src/libvpsc/variable.h
+++ b/src/libvpsc/variable.h
@@ -1,5 +1,4 @@
-/**
- *
+/*
  * Authors:
  *   Tim Dwyer <tgdwyer@gmail.com>
  *