Previously graph layout was done using the Kamada-Kawai layout algorithm

implemented in Boost.  I am replacing this with a custom implementation of
a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

(bzr r1394)

24 files changed, 3184 insertions, 0 deletions

diff --git a/src/libvpsc/COPYING b/src/libvpsc/COPYING
new file mode 100644
index 000000000..6ff1d7b6f
--- /dev/null
+++ b/src/libvpsc/COPYING
@@ -0,0 +1,505 @@
+		  GNU LESSER GENERAL PUBLIC LICENSE
+		       Version 2.1, February 1999
+
+ Copyright (C) 1991, 1999 Free Software Foundation, Inc.
+     51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+[This is the first released version of the Lesser GPL.  It also counts
+ as the successor of the GNU Library Public License, version 2, hence
+ the version number 2.1.]
+
+			    Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+Licenses are intended to guarantee your freedom to share and change
+free software--to make sure the software is free for all its users.
+
+  This license, the Lesser General Public License, applies to some
+specially designated software packages--typically libraries--of the
+Free Software Foundation and other authors who decide to use it.  You
+can use it too, but we suggest you first think carefully about whether
+this license or the ordinary General Public License is the better
+strategy to use in any particular case, based on the explanations below.
+
+  When we speak of free software, we are referring to freedom of use,
+not price.  Our General Public Licenses are designed to make sure that
+you have the freedom to distribute copies of free software (and charge
+for this service if you wish); that you receive source code or can get
+it if you want it; that you can change the software and use pieces of
+it in new free programs; and that you are informed that you can do
+these things.
+
+  To protect your rights, we need to make restrictions that forbid
+distributors to deny you these rights or to ask you to surrender these
+rights.  These restrictions translate to certain responsibilities for
+you if you distribute copies of the library or if you modify it.
+
+  For example, if you distribute copies of the library, whether gratis
+or for a fee, you must give the recipients all the rights that we gave
+you.  You must make sure that they, too, receive or can get the source
+code.  If you link other code with the library, you must provide
+complete object files to the recipients, so that they can relink them
+with the library after making changes to the library and recompiling
+it.  And you must show them these terms so they know their rights.
+
+  We protect your rights with a two-step method: (1) we copyright the
+library, and (2) we offer you this license, which gives you legal
+permission to copy, distribute and/or modify the library.
+
+  To protect each distributor, we want to make it very clear that
+there is no warranty for the free library.  Also, if the library is
+modified by someone else and passed on, the recipients should know
+that what they have is not the original version, so that the original
+author's reputation will not be affected by problems that might be
+introduced by others.
+
+  Finally, software patents pose a constant threat to the existence of
+any free program.  We wish to make sure that a company cannot
+effectively restrict the users of a free program by obtaining a
+restrictive license from a patent holder.  Therefore, we insist that
+any patent license obtained for a version of the library must be
+consistent with the full freedom of use specified in this license.
+
+  Most GNU software, including some libraries, is covered by the
+ordinary GNU General Public License.  This license, the GNU Lesser
+General Public License, applies to certain designated libraries, and
+is quite different from the ordinary General Public License.  We use
+this license for certain libraries in order to permit linking those
+libraries into non-free programs.
+
+  When a program is linked with a library, whether statically or using
+a shared library, the combination of the two is legally speaking a
+combined work, a derivative of the original library.  The ordinary
+General Public License therefore permits such linking only if the
+entire combination fits its criteria of freedom.  The Lesser General
+Public License permits more lax criteria for linking other code with
+the library.
+
+  We call this license the "Lesser" General Public License because it
+does Less to protect the user's freedom than the ordinary General
+Public License.  It also provides other free software developers Less
+of an advantage over competing non-free programs.  These disadvantages
+are the reason we use the ordinary General Public License for many
+libraries.  However, the Lesser license provides advantages in certain
+special circumstances.
+
+  For example, on rare occasions, there may be a special need to
+encourage the widest possible use of a certain library, so that it becomes
+a de-facto standard.  To achieve this, non-free programs must be
+allowed to use the library.  A more frequent case is that a free
+library does the same job as widely used non-free libraries.  In this
+case, there is little to gain by limiting the free library to free
+software only, so we use the Lesser General Public License.
+
+  In other cases, permission to use a particular library in non-free
+programs enables a greater number of people to use a large body of
+free software.  For example, permission to use the GNU C Library in
+non-free programs enables many more people to use the whole GNU
+operating system, as well as its variant, the GNU/Linux operating
+system.
+
+  Although the Lesser General Public License is Less protective of the
+users' freedom, it does ensure that the user of a program that is
+linked with the Library has the freedom and the wherewithal to run
+that program using a modified version of the Library.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.  Pay close attention to the difference between a
+"work based on the library" and a "work that uses the library".  The
+former contains code derived from the library, whereas the latter must
+be combined with the library in order to run.
+
+		  GNU LESSER GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License Agreement applies to any software library or other
+program which contains a notice placed by the copyright holder or
+other authorized party saying it may be distributed under the terms of
+this Lesser General Public License (also called "this License").
+Each licensee is addressed as "you".
+
+  A "library" means a collection of software functions and/or data
+prepared so as to be conveniently linked with application programs
+(which use some of those functions and data) to form executables.
+
+  The "Library", below, refers to any such software library or work
+which has been distributed under these terms.  A "work based on the
+Library" means either the Library or any derivative work under
+copyright law: that is to say, a work containing the Library or a
+portion of it, either verbatim or with modifications and/or translated
+straightforwardly into another language.  (Hereinafter, translation is
+included without limitation in the term "modification".)
+
+  "Source code" for a work means the preferred form of the work for
+making modifications to it.  For a library, complete source code means
+all the source code for all modules it contains, plus any associated
+interface definition files, plus the scripts used to control compilation
+and installation of the library.
+
+  Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running a program using the Library is not restricted, and output from
+such a program is covered only if its contents constitute a work based
+on the Library (independent of the use of the Library in a tool for
+writing it).  Whether that is true depends on what the Library does
+and what the program that uses the Library does.
+  
+  1. You may copy and distribute verbatim copies of the Library's
+complete source code as you receive it, in any medium, provided that
+you conspicuously and appropriately publish on each copy an
+appropriate copyright notice and disclaimer of warranty; keep intact
+all the notices that refer to this License and to the absence of any
+warranty; and distribute a copy of this License along with the
+Library.
+
+  You may charge a fee for the physical act of transferring a copy,
+and you may at your option offer warranty protection in exchange for a
+fee.
+
+  2. You may modify your copy or copies of the Library or any portion
+of it, thus forming a work based on the Library, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) The modified work must itself be a software library.
+
+    b) You must cause the files modified to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    c) You must cause the whole of the work to be licensed at no
+    charge to all third parties under the terms of this License.
+
+    d) If a facility in the modified Library refers to a function or a
+    table of data to be supplied by an application program that uses
+    the facility, other than as an argument passed when the facility
+    is invoked, then you must make a good faith effort to ensure that,
+    in the event an application does not supply such function or
+    table, the facility still operates, and performs whatever part of
+    its purpose remains meaningful.
+
+    (For example, a function in a library to compute square roots has
+    a purpose that is entirely well-defined independent of the
+    application.  Therefore, Subsection 2d requires that any
+    application-supplied function or table used by this function must
+    be optional: if the application does not supply it, the square
+    root function must still compute square roots.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Library,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Library, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote
+it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Library.
+
+In addition, mere aggregation of another work not based on the Library
+with the Library (or with a work based on the Library) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may opt to apply the terms of the ordinary GNU General Public
+License instead of this License to a given copy of the Library.  To do
+this, you must alter all the notices that refer to this License, so
+that they refer to the ordinary GNU General Public License, version 2,
+instead of to this License.  (If a newer version than version 2 of the
+ordinary GNU General Public License has appeared, then you can specify
+that version instead if you wish.)  Do not make any other change in
+these notices.
+
+  Once this change is made in a given copy, it is irreversible for
+that copy, so the ordinary GNU General Public License applies to all
+subsequent copies and derivative works made from that copy.
+
+  This option is useful when you wish to copy part of the code of
+the Library into a program that is not a library.
+
+  4. You may copy and distribute the Library (or a portion or
+derivative of it, under Section 2) in object code or executable form
+under the terms of Sections 1 and 2 above provided that you accompany
+it with the complete corresponding machine-readable source code, which
+must be distributed under the terms of Sections 1 and 2 above on a
+medium customarily used for software interchange.
+
+  If distribution of object code is made by offering access to copy
+from a designated place, then offering equivalent access to copy the
+source code from the same place satisfies the requirement to
+distribute the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  5. A program that contains no derivative of any portion of the
+Library, but is designed to work with the Library by being compiled or
+linked with it, is called a "work that uses the Library".  Such a
+work, in isolation, is not a derivative work of the Library, and
+therefore falls outside the scope of this License.
+
+  However, linking a "work that uses the Library" with the Library
+creates an executable that is a derivative of the Library (because it
+contains portions of the Library), rather than a "work that uses the
+library".  The executable is therefore covered by this License.
+Section 6 states terms for distribution of such executables.
+
+  When a "work that uses the Library" uses material from a header file
+that is part of the Library, the object code for the work may be a
+derivative work of the Library even though the source code is not.
+Whether this is true is especially significant if the work can be
+linked without the Library, or if the work is itself a library.  The
+threshold for this to be true is not precisely defined by law.
+
+  If such an object file uses only numerical parameters, data
+structure layouts and accessors, and small macros and small inline
+functions (ten lines or less in length), then the use of the object
+file is unrestricted, regardless of whether it is legally a derivative
+work.  (Executables containing this object code plus portions of the
+Library will still fall under Section 6.)
+
+  Otherwise, if the work is a derivative of the Library, you may
+distribute the object code for the work under the terms of Section 6.
+Any executables containing that work also fall under Section 6,
+whether or not they are linked directly with the Library itself.
+
+  6. As an exception to the Sections above, you may also combine or
+link a "work that uses the Library" with the Library to produce a
+work containing portions of the Library, and distribute that work
+under terms of your choice, provided that the terms permit
+modification of the work for the customer's own use and reverse
+engineering for debugging such modifications.
+
+  You must give prominent notice with each copy of the work that the
+Library is used in it and that the Library and its use are covered by
+this License.  You must supply a copy of this License.  If the work
+during execution displays copyright notices, you must include the
+copyright notice for the Library among them, as well as a reference
+directing the user to the copy of this License.  Also, you must do one
+of these things:
+
+    a) Accompany the work with the complete corresponding
+    machine-readable source code for the Library including whatever
+    changes were used in the work (which must be distributed under
+    Sections 1 and 2 above); and, if the work is an executable linked
+    with the Library, with the complete machine-readable "work that
+    uses the Library", as object code and/or source code, so that the
+    user can modify the Library and then relink to produce a modified
+    executable containing the modified Library.  (It is understood
+    that the user who changes the contents of definitions files in the
+    Library will not necessarily be able to recompile the application
+    to use the modified definitions.)
+
+    b) Use a suitable shared library mechanism for linking with the
+    Library.  A suitable mechanism is one that (1) uses at run time a
+    copy of the library already present on the user's computer system,
+    rather than copying library functions into the executable, and (2)
+    will operate properly with a modified version of the library, if
+    the user installs one, as long as the modified version is
+    interface-compatible with the version that the work was made with.
+
+    c) Accompany the work with a written offer, valid for at
+    least three years, to give the same user the materials
+    specified in Subsection 6a, above, for a charge no more
+    than the cost of performing this distribution.
+
+    d) If distribution of the work is made by offering access to copy
+    from a designated place, offer equivalent access to copy the above
+    specified materials from the same place.
+
+    e) Verify that the user has already received a copy of these
+    materials or that you have already sent this user a copy.
+
+  For an executable, the required form of the "work that uses the
+Library" must include any data and utility programs needed for
+reproducing the executable from it.  However, as a special exception,
+the materials to be distributed need not include anything that is
+normally distributed (in either source or binary form) with the major
+components (compiler, kernel, and so on) of the operating system on
+which the executable runs, unless that component itself accompanies
+the executable.
+
+  It may happen that this requirement contradicts the license
+restrictions of other proprietary libraries that do not normally
+accompany the operating system.  Such a contradiction means you cannot
+use both them and the Library together in an executable that you
+distribute.
+
+  7. You may place library facilities that are a work based on the
+Library side-by-side in a single library together with other library
+facilities not covered by this License, and distribute such a combined
+library, provided that the separate distribution of the work based on
+the Library and of the other library facilities is otherwise
+permitted, and provided that you do these two things:
+
+    a) Accompany the combined library with a copy of the same work
+    based on the Library, uncombined with any other library
+    facilities.  This must be distributed under the terms of the
+    Sections above.
+
+    b) Give prominent notice with the combined library of the fact
+    that part of it is a work based on the Library, and explaining
+    where to find the accompanying uncombined form of the same work.
+
+  8. You may not copy, modify, sublicense, link with, or distribute
+the Library except as expressly provided under this License.  Any
+attempt otherwise to copy, modify, sublicense, link with, or
+distribute the Library is void, and will automatically terminate your
+rights under this License.  However, parties who have received copies,
+or rights, from you under this License will not have their licenses
+terminated so long as such parties remain in full compliance.
+
+  9. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Library or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Library (or any work based on the
+Library), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Library or works based on it.
+
+  10. Each time you redistribute the Library (or any work based on the
+Library), the recipient automatically receives a license from the
+original licensor to copy, distribute, link with or modify the Library
+subject to these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties with
+this License.
+
+  11. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Library at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Library by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Library.
+
+If any portion of this section is held invalid or unenforceable under any
+particular circumstance, the balance of the section is intended to apply,
+and the section as a whole is intended to apply in other circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  12. If the distribution and/or use of the Library is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Library under this License may add
+an explicit geographical distribution limitation excluding those countries,
+so that distribution is permitted only in or among countries not thus
+excluded.  In such case, this License incorporates the limitation as if
+written in the body of this License.
+
+  13. The Free Software Foundation may publish revised and/or new
+versions of the Lesser General Public License from time to time.
+Such new versions will be similar in spirit to the present version,
+but may differ in detail to address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Library
+specifies a version number of this License which applies to it and
+"any later version", you have the option of following the terms and
+conditions either of that version or of any later version published by
+the Free Software Foundation.  If the Library does not specify a
+license version number, you may choose any version ever published by
+the Free Software Foundation.
+
+  14. If you wish to incorporate parts of the Library into other free
+programs whose distribution conditions are incompatible with these,
+write to the author to ask for permission.  For software which is
+copyrighted by the Free Software Foundation, write to the Free
+Software Foundation; we sometimes make exceptions for this.  Our
+decision will be guided by the two goals of preserving the free status
+of all derivatives of our free software and of promoting the sharing
+and reuse of software generally.
+
+			    NO WARRANTY
+
+  15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO
+WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
+EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
+OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY
+KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE
+LIBRARY IS WITH YOU.  SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME
+THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
+
+  16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
+AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU
+FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR
+CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE
+LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING
+RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A
+FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF
+SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
+DAMAGES.
+
+		     END OF TERMS AND CONDITIONS
+
+           How to Apply These Terms to Your New Libraries
+
+  If you develop a new library, and you want it to be of the greatest
+possible use to the public, we recommend making it free software that
+everyone can redistribute and change.  You can do so by permitting
+redistribution under these terms (or, alternatively, under the terms of the
+ordinary General Public License).
+
+  To apply these terms, attach the following notices to the library.  It is
+safest to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least the
+"copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the library's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Lesser General Public
+    License as published by the Free Software Foundation; either
+    version 2.1 of the License, or (at your option) any later version.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Lesser General Public License for more details.
+
+    You should have received a copy of the GNU Lesser General Public
+    License along with this library; if not, write to the Free Software
+    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+
+Also add information on how to contact you by electronic and paper mail.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the library, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the
+  library `Frob' (a library for tweaking knobs) written by James Random Hacker.
+
+  <signature of Ty Coon>, 1 April 1990
+  Ty Coon, President of Vice
+
+That's all there is to it!
+
+
+
diff --git a/src/libvpsc/Makefile_insert b/src/libvpsc/Makefile_insert
new file mode 100644
index 000000000..78b825b13
--- /dev/null
+++ b/src/libvpsc/Makefile_insert
@@ -0,0 +1,26 @@
+## Makefile.am fragment sourced by src/Makefile.am.
+libvpsc/all: libvpsc/libvpsc.a
+
+libvpsc/clean:
+	rm -f libvpsc/libvpsc.a $(libvpsc_libvpsc_a_OBJECTS)
+
+libvpsc_libvpsc_a_SOURCES = libvpsc/block.cpp\
+	libvpsc/blocks.cpp\
+	libvpsc/constraint.cpp\
+	libvpsc/generate-constraints.cpp\
+	libvpsc/pairingheap/PairingHeap.cpp\
+	libvpsc/remove_rectangle_overlap.cpp\
+	libvpsc/solve_VPSC.cpp\
+	libvpsc/csolve_VPSC.cpp\
+	libvpsc/variable.cpp\
+	libvpsc/isnan.h\
+	libvpsc/block.h\
+	libvpsc/blocks.h\
+	libvpsc/constraint.h\
+	libvpsc/generate-constraints.h\
+	libvpsc/pairingheap/PairingHeap.h\
+	libvpsc/pairingheap/dsexceptions.h\
+	libvpsc/remove_rectangle_overlap.h\
+	libvpsc/solve_VPSC.h\
+	libvpsc/csolve_VPSC.h\
+	libvpsc/variable.h
diff --git a/src/libvpsc/block.cpp b/src/libvpsc/block.cpp
new file mode 100644
index 000000000..69a439cd7
--- /dev/null
+++ b/src/libvpsc/block.cpp
@@ -0,0 +1,404 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+#include <cassert>
+#include "pairingheap/PairingHeap.h"
+#include "constraint.h"
+#include "block.h"
+#include "blocks.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+using std::vector;
+
+void Block::addVariable(Variable* const v) {
+	v->block=this;
+	vars->push_back(v);
+	weight+=v->weight;
+	wposn += v->weight * (v->desiredPosition - v->offset);
+	posn=wposn/weight;
+}
+Block::Block(Variable* const v) {
+	timeStamp=0;
+	posn=weight=wposn=0;
+	in=NULL;
+	out=NULL;
+	deleted=false;
+	vars=new vector<Variable*>;
+	if(v!=NULL) {
+		v->offset=0;
+		addVariable(v);
+	}
+}
+
+double Block::desiredWeightedPosition() {
+	double wp = 0;
+	for (Vit v=vars->begin();v!=vars->end();++v) {
+		wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
+	}
+	return wp;
+}
+Block::~Block(void)
+{
+	delete vars;
+	delete in;
+	delete out;
+}
+void Block::setUpInConstraints() {
+	setUpConstraintHeap(in,true);
+}
+void Block::setUpOutConstraints() {
+	setUpConstraintHeap(out,false);
+}
+void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
+	delete h;
+	h = new PairingHeap<Constraint*>(&compareConstraints);
+	for (Vit i=vars->begin();i!=vars->end();++i) {
+		Variable *v=*i;
+		vector<Constraint*> *cs=in?&(v->in):&(v->out);
+		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) {
+				h->insert(c);
+			}
+		}
+	}
+}	
+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
+ * @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);
+	f<<"    merging: "<<*b<<"dist="<<dist<<endl;
+#endif
+	c->active=true;
+	wposn+=b->wposn-dist*b->weight;
+	weight+=b->weight;
+	posn=wposn/weight;
+	for(Vit 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) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"  merging constraint heaps... "<<endl;
+#endif
+	// We check the top of the heaps to remove possible internal constraints
+	findMinInConstraint();
+	b->findMinInConstraint();
+	in->merge(b->in);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"  merged heap: "<<*in<<endl;
+#endif
+}
+void Block::mergeOut(Block *b) {	
+	findMinOutConstraint();
+	b->findMinOutConstraint();
+	out->merge(b->out);
+}
+Constraint *Block::findMinInConstraint() {
+	Constraint *v = NULL;
+	vector<Constraint*> outOfDate;
+	while (!in->isEmpty()) {
+		v = in->findMin();
+		Block *lb=v->left->block;
+		Block *rb=v->right->block;
+		// rb may not be this if called between merge and mergeIn
+#ifdef RECTANGLE_OVERLAP_LOGGING
+		ofstream f(LOGFILE,ios::app);
+		f<<"  checking constraint ... "<<*v;
+		f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
+#endif
+		if(lb == rb) {
+			// constraint has been merged into the same block
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			if(v->slack()<0) {
+				f<<"  violated internal constraint found! "<<*v<<endl;
+				f<<"     lb="<<*lb<<endl;
+				f<<"     rb="<<*rb<<endl;
+			}
+#endif
+			in->deleteMin();
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			f<<" ... skipping internal constraint"<<endl;
+#endif
+		} else if(v->timeStamp < lb->timeStamp) {
+			// block at other end of constraint has been moved since this
+			in->deleteMin();
+			outOfDate.push_back(v);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			f<<"    reinserting out of date (reinsert later)"<<endl;
+#endif
+		} else {
+			break;
+		}
+	}
+	for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
+		v=*i;
+		v->timeStamp=blockTimeCtr;
+		in->insert(v);
+	}
+	if(in->isEmpty()) {
+		v=NULL;
+	} else {
+		v=in->findMin();
+	}
+	return v;
+}
+Constraint *Block::findMinOutConstraint() {
+	if(out->isEmpty()) return NULL;
+	Constraint *v = out->findMin();
+	while (v->left->block == v->right->block) {
+		out->deleteMin();
+		if(out->isEmpty()) return NULL;
+		v = out->findMin();
+	}
+	return v;
+}
+void Block::deleteMinInConstraint() {
+	in->deleteMin();
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"deleteMinInConstraint... "<<endl;
+	f<<"  result: "<<*in<<endl;
+#endif
+}
+void Block::deleteMinOutConstraint() {
+	out->deleteMin();
+}
+inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) {
+	return c->left->block==this && c->active && last!=c->left;
+}
+inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
+	return c->right->block==this && c->active && last!=c->right;
+}
+
+// computes the derivative of v and the lagrange multipliers
+// of v's out constraints (as the recursive sum of those below.
+// Does not backtrack over u.
+// also records the constraint with minimum lagrange multiplier
+// in min_lm
+double Block::compute_dfdv(Variable* const v, Variable* const u,
+	       	Constraint *&min_lm) {
+	double dfdv=v->weight*(v->position() - v->desiredPosition);
+	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(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
+		}
+	}
+	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(!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* const v, Variable* const u, 
+		const 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* const v, Variable* const u) {
+	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(Cit it=v->in.begin();it!=v->in.end();++it) {
+		Constraint *c=*it;
+		if(canFollowLeft(c,u)) {
+			c->lm=0;
+			reset_active_lm(c->left,v);
+		}
+	}
+}
+/**
+ * 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);
+	compute_dfdv(vars->front(),NULL,min_lm);
+	return min_lm;
+}
+Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const 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* const v, Variable* const u) {
+	b->addVariable(v);
+	for (Cit c=v->in.begin();c!=v->in.end();++c) {
+		if (canFollowLeft(*c,u))
+			populateSplitBlock(b, (*c)->left, v);
+	}
+	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* const vl, Variable* const 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.
+ */
+void Block::split(Block* &l, Block* &r, Constraint* c) {
+	c->active=false;
+	l=new Block();
+	populateSplitBlock(l,c->left,c->right);
+	r=new Block();
+	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) {
+		double diff = (*v)->position() - (*v)->desiredPosition;
+		c += (*v)->weight * diff * diff;
+	}
+	return c;
+}
+ostream& operator <<(ostream &os, const Block& b)
+{
+	os<<"Block:";
+	for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
+		os<<" "<<**v;
+	}
+	if(b.deleted) {
+		os<<" Deleted!";
+	}
+    return os;
+}
diff --git a/src/libvpsc/block.h b/src/libvpsc/block.h
new file mode 100644
index 000000000..81e6c7637
--- /dev/null
+++ b/src/libvpsc/block.h
@@ -0,0 +1,74 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_BLOCK_H
+#define SEEN_REMOVEOVERLAP_BLOCK_H
+
+#include <vector>
+#include <iostream>
+class Variable;
+class Constraint;
+template <class T> class PairingHeap;
+class StupidPriorityQueue;
+
+class Block
+{
+	typedef std::vector<Variable*> Variables;
+	typedef std::vector<Constraint*>::iterator Cit;
+	typedef std::vector<Variable*>::iterator Vit;
+
+	friend std::ostream& operator <<(std::ostream &os,const Block &b);
+public:
+	Variables *vars;
+	double posn;
+	double weight;
+	double wposn;
+	Block(Variable* const v=NULL);
+	~Block(void);
+	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);
+	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();
+	bool deleted;
+	long timeStamp;
+	PairingHeap<Constraint*> *in;
+	PairingHeap<Constraint*> *out;
+private:
+	typedef enum {NONE, LEFT, RIGHT} Direction;
+	typedef std::pair<double, Constraint*> Pair;
+	void reset_active_lm(Variable* const v, Variable* const u);
+	double compute_dfdv(Variable* const v, Variable* const u,
+		       	Constraint *&min_lm);
+	Pair compute_dfdv_between(
+			Variable*, Variable* const, Variable* const,
+		       	const Direction, bool);
+	bool canFollowLeft(Constraint *c, const Variable* const last);
+	bool canFollowRight(Constraint *c, const Variable* const last);
+	void populateSplitBlock(Block *b, Variable* const v, Variable* const u);
+	void addVariable(Variable* const v);
+	void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
+};
+
+#endif // SEEN_REMOVEOVERLAP_BLOCK_H
diff --git a/src/libvpsc/blocks.cpp b/src/libvpsc/blocks.cpp
new file mode 100644
index 000000000..48f0237bf
--- /dev/null
+++ b/src/libvpsc/blocks.cpp
@@ -0,0 +1,196 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#include "blocks.h"
+#include "block.h"
+#include "constraint.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+using std::set;
+using std::vector;
+using std::iterator;
+using std::list;
+using std::copy;
+
+long blockTimeCtr;
+
+Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) {
+	blockTimeCtr=0;
+	for(int i=0;i<nvs;i++) {
+		insert(new Block(vs[i]));
+	}
+}
+Blocks::~Blocks(void)
+{
+	blockTimeCtr=0;
+	for(set<Block*>::iterator i=begin();i!=end();++i) {
+		delete *i;
+	}
+	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++) {
+		vs[i]->visited=false;
+	}
+	for(int i=0;i<nvs;i++) {
+		if(vs[i]->in.size()==0) {
+			dfsVisit(vs[i],order);
+		}
+	}
+	return order;
+}
+// Recursive depth first search giving total order by pushing nodes in the DAG
+// onto the front of the list when we finish searching them
+void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
+	v->visited=true;
+	vector<Constraint*>::iterator it=v->out.begin();
+	for(;it!=v->out.end();++it) {
+		Constraint *c=*it;
+		if(!c->right->visited) {
+			dfsVisit(c->right, order);
+		}
+	}	
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"  order="<<*v<<endl;
+#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);
+	f<<"mergeLeft called on "<<*r<<endl;
+#endif
+	r->timeStamp=++blockTimeCtr;
+	r->setUpInConstraints();
+	Constraint *c=r->findMinInConstraint();
+	while (c != NULL && c->slack()<0) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+		f<<"mergeLeft on constraint: "<<*c<<endl;
+#endif
+		r->deleteMinInConstraint();
+		Block *l = c->left->block;		
+		if (l->in==NULL) l->setUpInConstraints();
+		double dist = c->right->offset - c->left->offset - c->gap;
+		if (r->vars->size() < l->vars->size()) {
+			dist=-dist;
+			std::swap(l, r);
+		}
+		blockTimeCtr++;
+		r->merge(l, c, dist);
+		r->mergeIn(l);
+		r->timeStamp=blockTimeCtr;
+		removeBlock(l);
+		c=r->findMinInConstraint();
+	}		
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"merged "<<*r<<endl;
+#endif
+}	
+/**
+ * Symmetrical to mergeLeft
+ */
+void Blocks::mergeRight(Block *l) {	
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"mergeRight called on "<<*l<<endl;
+#endif	
+	l->setUpOutConstraints();
+	Constraint *c = l->findMinOutConstraint();
+	while (c != NULL && c->slack()<0) {		
+#ifdef RECTANGLE_OVERLAP_LOGGING
+		f<<"mergeRight on constraint: "<<*c<<endl;
+#endif
+		l->deleteMinOutConstraint();
+		Block *r = c->right->block;
+		r->setUpOutConstraints();
+		double dist = c->left->offset + c->gap - c->right->offset;
+		if (l->vars->size() > r->vars->size()) {
+			dist=-dist;
+			std::swap(l, r);
+		}
+		l->merge(r, c, dist);
+		l->mergeOut(r);
+		removeBlock(r);
+		c=l->findMinOutConstraint();
+	}	
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	f<<"merged "<<*l<<endl;
+#endif
+}
+void Blocks::removeBlock(Block *doomed) {
+	doomed->deleted=true;
+	//erase(doomed);
+}
+void Blocks::cleanup() {
+	vector<Block*> bcopy(begin(),end());
+	for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
+		Block *b=*i;
+		if(b->deleted) {
+			erase(b);
+			delete b;
+		}
+	}
+}
+/**
+ * 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
+	ofstream f(LOGFILE,ios::app);
+	f<<"Split left: "<<*l<<endl;
+	f<<"Split right: "<<*r<<endl;
+#endif
+	r->posn = b->posn;
+	r->wposn = r->posn * r->weight;
+	mergeLeft(l);
+	// r may have been merged!
+	r = c->right->block;
+	r->wposn = r->desiredWeightedPosition();
+	r->posn = r->wposn / r->weight;
+	mergeRight(r);
+	removeBlock(b);
+
+	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) {
+		c += (*i)->cost();
+	}
+	return c;
+}
+
diff --git a/src/libvpsc/blocks.h b/src/libvpsc/blocks.h
new file mode 100644
index 000000000..0be1d7636
--- /dev/null
+++ b/src/libvpsc/blocks.h
@@ -0,0 +1,53 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_BLOCKS_H
+#define SEEN_REMOVEOVERLAP_BLOCKS_H
+
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#define LOGFILE "cRectangleOverlap.log"
+#endif
+
+#include <set>
+#include <list>
+
+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
+ */
+class Blocks : public std::set<Block*>
+{
+public:
+	Blocks(const int n, Variable* const vs[]);
+	~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();
+private:
+	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
diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp
new file mode 100644
index 000000000..7c200878b
--- /dev/null
+++ b/src/libvpsc/constraint.cpp
@@ -0,0 +1,47 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#include "constraint.h"
+#include <cassert>
+Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality)
+: left(left),
+  right(right),
+  gap(gap),
+  timeStamp(0),
+  active(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)
+{
+	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/libvpsc/constraint.h b/src/libvpsc/constraint.h
new file mode 100644
index 000000000..3da7449cd
--- /dev/null
+++ b/src/libvpsc/constraint.h
@@ -0,0 +1,58 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#ifndef SEEN_REMOVEOVERLAP_CONSTRAINT_H
+#define SEEN_REMOVEOVERLAP_CONSTRAINT_H
+
+#include <iostream>
+#include "variable.h"
+
+class Constraint
+{
+	friend std::ostream& operator <<(std::ostream &os,const Constraint &c);
+public:
+	Variable *left;
+	Variable *right;
+	double gap;
+	double lm;
+	Constraint(Variable *left, Variable *right, double gap, bool equality=false);
+	~Constraint();
+	inline double slack() const { return right->position() - gap - left->position(); }
+	long timeStamp;
+	bool active;
+	bool visited;
+	bool equality;
+};
+#include <float.h>
+#include "block.h"
+static inline bool compareConstraints(Constraint *const &l, Constraint *const &r) {
+	double const sl = 
+		l->left->block->timeStamp > l->timeStamp
+		||l->left->block==l->right->block
+		?-DBL_MAX:l->slack();
+	double const sr = 
+		r->left->block->timeStamp > r->timeStamp
+		||r->left->block==r->right->block
+		?-DBL_MAX:r->slack();
+	if(sl==sr) {
+		// arbitrary choice based on id
+		if(l->left->id==r->left->id) {
+			if(l->right->id<r->right->id) return true;
+			return false;
+		}
+		if(l->left->id<r->left->id) return true;
+		return false;
+	}
+	return sl < sr;
+}
+
+#endif // SEEN_REMOVEOVERLAP_CONSTRAINT_H
diff --git a/src/libvpsc/csolve_VPSC.cpp b/src/libvpsc/csolve_VPSC.cpp
new file mode 100644
index 000000000..b78b01054
--- /dev/null
+++ b/src/libvpsc/csolve_VPSC.cpp
@@ -0,0 +1,124 @@
+/**
+ * \brief Bridge for C programs to access solve_VPSC (which is in C++)
+ *
+ * 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 "variable.h"
+#include "constraint.h"
+#include "generate-constraints.h"
+#include "solve_VPSC.h"
+#include "csolve_VPSC.h"
+extern "C" {
+Variable* newVariable(int id, double desiredPos, double weight) {
+	return new Variable(id,desiredPos,weight);
+}
+Constraint* newConstraint(Variable* left, Variable* right, double gap) {
+	return new Constraint(left,right,gap);
+}
+VPSC* newVPSC(int n, Variable* vs[], int m, Constraint* cs[]) {
+	return new VPSC(n,vs,m,cs);
+}
+VPSC* newIncVPSC(int n, Variable* vs[], int m, Constraint* cs[]) {
+	return (VPSC*)new IncVPSC(n,vs,m,cs);
+}
+
+int genXConstraints(int n, boxf* bb, Variable** vs, Constraint*** cs,int transitiveClosure) {
+	Rectangle* rs[n];
+	for(int i=0;i<n;i++) {
+		rs[i]=new Rectangle(bb[i].LL.x,bb[i].UR.x,bb[i].LL.y,bb[i].UR.y);
+	}
+	int m = generateXConstraints(n,rs,vs,*cs,transitiveClosure);
+	for(int i=0;i<n;i++) {
+		delete rs[i];
+	}
+	return m;
+}
+int genYConstraints(int n, boxf* bb, Variable** vs, Constraint*** cs) {
+	Rectangle* rs[n];
+	for(int i=0;i<n;i++) {
+		rs[i]=new Rectangle(bb[i].LL.x,bb[i].UR.x,bb[i].LL.y,bb[i].UR.y);
+	}
+	int m = generateYConstraints(n,rs,vs,*cs);
+	for(int i=0;i<n;i++) {
+		delete rs[i];
+	}
+	return m;
+}
+
+Constraint** newConstraints(int m) {
+	return new Constraint*[m];
+}
+void deleteConstraints(int m, Constraint **cs) {
+	for(int i=0;i<m;i++) {
+		delete cs[i];
+	}
+	delete [] cs;
+}
+void deleteConstraint(Constraint* c) {
+	delete c;
+}
+void deleteVariable(Variable* v) {
+	delete v;
+}
+void satisfyVPSC(VPSC* vpsc) {
+	try {
+		vpsc->satisfy();
+	} catch(const char *e) {
+		std::cerr << e << std::endl;
+		exit(1);
+	}
+}
+int getSplitCnt(IncVPSC *vpsc) {
+	return vpsc->splitCnt;
+}
+void deleteVPSC(VPSC *vpsc) {
+	assert(vpsc!=NULL);
+	delete vpsc;
+}
+void solveVPSC(VPSC* vpsc) {
+	vpsc->solve();
+}
+void splitIncVPSC(IncVPSC* vpsc) {
+	vpsc->splitBlocks();
+}
+void setVariableDesiredPos(Variable *v, double desiredPos) {
+	v->desiredPosition = desiredPos;
+}
+double getVariablePos(Variable *v) {
+	return v->position();
+}
+void remapInConstraints(Variable *u, Variable *v, double dgap) {
+	for(Constraints::iterator i=u->in.begin();i!=u->in.end();i++) {
+		Constraint* c=*i;	
+		c->right=v;
+		c->gap+=dgap;
+		v->in.push_back(c);
+	}
+	u->in.clear();
+}
+void remapOutConstraints(Variable *u, Variable *v, double dgap) {
+	for(Constraints::iterator i=u->out.begin();i!=u->out.end();i++) {
+		Constraint* c=*i;	
+		c->left=v;
+		c->gap+=dgap;
+		v->out.push_back(c);
+	}
+	u->out.clear();
+}
+int getLeftVarID(Constraint *c) {
+	return c->left->id;
+}
+int getRightVarID(Constraint *c){
+	return c->right->id;
+}
+double getSeparation(Constraint *c){
+	return c->gap;
+}
+}
diff --git a/src/libvpsc/csolve_VPSC.h b/src/libvpsc/csolve_VPSC.h
new file mode 100644
index 000000000..cd879effe
--- /dev/null
+++ b/src/libvpsc/csolve_VPSC.h
@@ -0,0 +1,54 @@
+/**
+ * \brief Bridge for C programs to access solve_VPSC (which is in C++)
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+#ifndef _CSOLVE_VPSC_H_
+#define _CSOLVE_VPSC_H_
+#ifdef __cplusplus
+extern "C" {
+#endif
+typedef struct Variable Variable;
+Variable* newVariable(int id, double desiredPos, double weight);
+void setVariableDesiredPos(Variable *, double desiredPos);
+double getVariablePos(Variable*);
+
+typedef struct Constraint Constraint;
+Constraint* newConstraint(Variable* left, Variable* right, double gap);
+
+typedef struct VPSC VPSC;
+VPSC* newVPSC(int n, Variable* vs[], int m, Constraint* cs[]);
+void deleteVPSC(VPSC*);
+void deleteConstraint(Constraint*);
+void deleteVariable(Variable*);
+Constraint** newConstraints(int m);
+void deleteConstraints(int m,Constraint**);
+void remapInConstraints(Variable *u, Variable *v, double dgap);
+void remapOutConstraints(Variable *u, Variable *v, double dgap);
+int getLeftVarID(Constraint *c);
+int getRightVarID(Constraint *c);
+double getSeparation(Constraint *c);
+
+#ifndef HAVE_POINTF_S
+typedef struct pointf_s { double x, y; } pointf;
+typedef struct { pointf LL, UR; } boxf;
+#endif
+int genXConstraints(int n, boxf[], Variable** vs, Constraint*** cs,
+		int transitiveClosure);
+int genYConstraints(int n, boxf[], Variable** vs, Constraint*** cs);
+
+void satisfyVPSC(VPSC*);
+void solveVPSC(VPSC*);
+typedef struct IncVPSC IncVPSC;
+VPSC* newIncVPSC(int n, Variable* vs[], int m, Constraint* cs[]);
+void splitIncVPSC(IncVPSC*);
+int getSplitCnt(IncVPSC *vpsc);
+#ifdef __cplusplus
+}
+#endif
+#endif /* _CSOLVE_VPSC_H_ */
diff --git a/src/libvpsc/generate-constraints.cpp b/src/libvpsc/generate-constraints.cpp
new file mode 100644
index 000000000..312ad960b
--- /dev/null
+++ b/src/libvpsc/generate-constraints.cpp
@@ -0,0 +1,303 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#include <set>
+#include <cassert>
+#include "generate-constraints.h"
+#include "constraint.h"
+
+#include "isnan.h" /* Include last */
+
+using std::set;
+using std::vector;
+
+std::ostream& operator <<(std::ostream &os, const Rectangle &r) {
+	os << "{"<<r.minX<<","<<r.maxX<<","<<r.minY<<","<<r.maxY<<"},";
+	return os;
+}
+Rectangle::Rectangle(double x, double X, double y, double Y) 
+: minX(x),maxX(X),minY(y),maxY(Y) {
+		assert(x<=X);
+		assert(y<=Y);
+}
+
+struct Node;
+struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
+
+typedef set<Node*,CmpNodePos> NodeSet;
+
+struct Node {
+	Variable *v;
+	Rectangle *r;
+	double pos;
+	Node *firstAbove, *firstBelow;
+	NodeSet *leftNeighbours, *rightNeighbours;
+	Node(Variable *v, Rectangle *r, double p) : v(v),r(r),pos(p) {
+		firstAbove=firstBelow=NULL;
+		leftNeighbours=rightNeighbours=NULL;
+		assert(r->width()<1e40);
+	}
+	~Node() {
+		delete leftNeighbours;
+		delete rightNeighbours;
+	}
+	void addLeftNeighbour(Node *u) {
+		leftNeighbours->insert(u);
+	}
+	void addRightNeighbour(Node *u) {
+		rightNeighbours->insert(u);
+	}
+	void setNeighbours(NodeSet *left, NodeSet *right) {
+		leftNeighbours=left;
+		rightNeighbours=right;
+		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) {
+			Node *v=*(i);
+			v->addLeftNeighbour(this);
+		}
+	}
+};
+bool CmpNodePos::operator() (const Node* u, const Node* v) const {
+	if (u->pos < v->pos) {
+		return true;
+	}
+	if (v->pos < u->pos) {
+		return false;
+	}
+	if (isNaN(u->pos) != isNaN(v->pos)) {
+		return isNaN(u->pos);
+	}
+	return u < v;
+
+	/* I don't know how important it is to handle NaN correctly
+	 * (e.g. we probably handle it badly in other code anyway, and
+	 * in any case the best we can hope for is to reduce the
+	 * badness of other nodes).
+	 *
+	 * Nevertheless, we try to do the right thing here and in
+	 * event comparison.  The issue is that (on platforms with
+	 * ieee floating point comparison) NaN compares neither less
+	 * than nor greater than any other number, yet sort wants a
+	 * well-defined ordering.  In particular, we want to ensure
+	 * transitivity of equivalence, which normally wouldn't be
+	 * guaranteed if the "middle" item in the transitivity
+	 * involves a NaN.  (NaN is neither less than nor greater than
+	 * other numbers, so tends to be considered as equal to all
+	 * other numbers: even unequal numbers.)
+	 */
+}
+
+NodeSet* getLeftNeighbours(NodeSet &scanline,Node *v) {
+	NodeSet *leftv = new NodeSet;
+	NodeSet::iterator i=scanline.find(v);
+	while(i--!=scanline.begin()) {
+		Node *u=*(i);
+		if(u->r->overlapX(v->r)<=0) {
+			leftv->insert(u);
+			return leftv;
+		}
+		if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
+			leftv->insert(u);
+		}
+	}
+	return leftv;
+}
+NodeSet* getRightNeighbours(NodeSet &scanline,Node *v) {
+	NodeSet *rightv = new NodeSet;
+	NodeSet::iterator i=scanline.find(v);
+	for(++i;i!=scanline.end(); ++i) {
+		Node *u=*(i);
+		if(u->r->overlapX(v->r)<=0) {
+			rightv->insert(u);
+			return rightv;
+		}
+		if(u->r->overlapX(v->r)<=u->r->overlapY(v->r)) {
+			rightv->insert(u);
+		}
+	}
+	return rightv;
+}
+
+typedef enum {Open, Close} EventType;
+struct Event {
+	EventType type;
+	Node *v;
+	double pos;
+	Event(EventType t, Node *v, double p) : type(t),v(v),pos(p) {};
+};
+Event **events;
+int compare_events(const void *a, const void *b) {
+	Event *ea=*(Event**)a;
+	Event *eb=*(Event**)b;
+	if(ea->v->r==eb->v->r) {
+		// when comparing opening and closing from the same rect
+		// open must come first
+		if(ea->type==Open) return -1;
+		return 1;
+	} else if(ea->pos > eb->pos) {
+		return 1;
+	} else if(ea->pos < eb->pos) {
+		return -1;
+	} else if(isNaN(ea->pos) != isNaN(ea->pos)) {
+		/* See comment in CmpNodePos. */
+		return ( isNaN(ea->pos)
+			 ? -1
+			 : 1 );
+	}
+	return 0;
+}
+
+/**
+ * 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(const int n, Rectangle** rs, Variable** vars, Constraint** &cs, const bool useNeighbourLists) {
+	events=new Event*[2*n];
+	int i,m,ctr=0;
+	for(i=0;i<n;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());
+	}
+	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;
+		if(e->type==Open) {
+			scanline.insert(v);
+			if(useNeighbourLists) {
+				v->setNeighbours(
+					getLeftNeighbours(scanline,v),
+					getRightNeighbours(scanline,v)
+				);
+			} else {
+				NodeSet::iterator it=scanline.find(v);
+				if(it--!=scanline.begin()) {
+					Node *u=*it;
+					v->firstAbove=u;
+					u->firstBelow=v;
+				}
+				it=scanline.find(v);
+				if(++it!=scanline.end()) {
+					Node *u=*it;
+					v->firstBelow=u;
+					u->firstAbove=v;
+				}
+			}
+		} else {
+			// Close event
+			int r;
+			if(useNeighbourLists) {
+				for(NodeSet::iterator i=v->leftNeighbours->begin();
+					i!=v->leftNeighbours->end();i++
+				) {
+					Node *u=*i;
+					double sep = (v->r->width()+u->r->width())/2.0;
+					constraints.push_back(new Constraint(u->v,v->v,sep));
+					r=u->rightNeighbours->erase(v);
+				}
+				
+				for(NodeSet::iterator i=v->rightNeighbours->begin();
+					i!=v->rightNeighbours->end();i++
+				) {
+					Node *u=*i;
+					double sep = (v->r->width()+u->r->width())/2.0;
+					constraints.push_back(new Constraint(v->v,u->v,sep));
+					r=u->leftNeighbours->erase(v);
+				}
+			} else {
+				Node *l=v->firstAbove, *r=v->firstBelow;
+				if(l!=NULL) {
+					double sep = (v->r->width()+l->r->width())/2.0;
+					constraints.push_back(new Constraint(l->v,v->v,sep));
+					l->firstBelow=v->firstBelow;
+				}
+				if(r!=NULL) {
+					double sep = (v->r->width()+r->r->width())/2.0;
+					constraints.push_back(new Constraint(v->v,r->v,sep));
+					r->firstAbove=v->firstAbove;
+				}
+			}
+			r=scanline.erase(v);
+			delete v;
+		}
+		delete e;
+	}
+	delete [] events;
+	cs=new Constraint*[m=constraints.size()];
+	for(i=0;i<m;i++) cs[i]=constraints[i];
+	return m;
+}
+
+/**
+ * Prepares constraints in order to apply VPSC vertically to remove ALL overlap.
+ */
+int generateYConstraints(const int n, Rectangle** rs, Variable** vars, Constraint** &cs) {
+	events=new Event*[2*n];
+	int ctr=0,i,m;
+	for(i=0;i<n;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;
+		if(e->type==Open) {
+			scanline.insert(v);
+			NodeSet::iterator i=scanline.find(v);
+			if(i--!=scanline.begin()) {
+				Node *u=*i;
+				v->firstAbove=u;
+				u->firstBelow=v;
+			}
+			i=scanline.find(v);
+			if(++i!=scanline.end())	 {
+				Node *u=*i;
+				v->firstBelow=u;
+				u->firstAbove=v;
+			}
+		} else {
+			// Close event
+			Node *l=v->firstAbove, *r=v->firstBelow;
+			if(l!=NULL) {
+				double sep = (v->r->height()+l->r->height())/2.0;
+				constraints.push_back(new Constraint(l->v,v->v,sep));
+				l->firstBelow=v->firstBelow;
+			}
+			if(r!=NULL) {
+				double sep = (v->r->height()+r->r->height())/2.0;
+				constraints.push_back(new Constraint(v->v,r->v,sep));
+				r->firstAbove=v->firstAbove;
+			}
+			scanline.erase(v);
+			delete v;
+		}
+		delete e;
+	}
+	delete [] events;
+	cs=new Constraint*[m=constraints.size()];
+	for(i=0;i<m;i++) cs[i]=constraints[i];
+	return m;
+}
diff --git a/src/libvpsc/generate-constraints.h b/src/libvpsc/generate-constraints.h
new file mode 100644
index 000000000..56ee9536a
--- /dev/null
+++ b/src/libvpsc/generate-constraints.h
@@ -0,0 +1,78 @@
+/**
+ * \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 LGPL.  Read the file 'COPYING' for more information.
+ */
+#ifndef SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
+#define SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
+#include <iostream>
+
+class Rectangle {	
+	friend std::ostream& operator <<(std::ostream &os, const Rectangle &r);
+public:
+	static double xBorder,yBorder;
+	Rectangle(double x, double X, double y, double Y);
+	double getMaxX() const { return maxX+xBorder; }
+	double getMaxY() const { return maxY+yBorder; }
+	double getMinX() const { return minX; }
+	double getMinY() const { return minY; }
+	double getMinD(unsigned const d) const {
+		return ( d == 0 ? getMinX() : getMinY() );
+	}
+	double getMaxD(unsigned const d) const {
+		return ( d == 0 ? getMaxX() : getMaxY() );
+	}
+	double getCentreX() const { return minX+width()/2.0; }
+	double getCentreY() const { return minY+height()/2.0; }
+	double width() const { return getMaxX()-minX; }
+	double height() const { return getMaxY()-minY; }
+	static void setXBorder(double x) {xBorder=x;}
+	static void setYBorder(double y) {yBorder=y;}
+	void moveCentreX(double x) {
+		moveMinX(x-width()/2.0);
+	}
+	void moveCentreY(double y) {
+		moveMinY(y-height()/2.0);
+	}
+	void moveMinX(double x) {
+		maxX=x+width()-xBorder;
+		minX=x;
+	}
+	void moveMinY(double y) {
+		maxY=y+height()-yBorder;
+		minY=y;
+	}
+	inline double overlapX(Rectangle *r) const {
+		if (getCentreX() <= r->getCentreX() && r->minX < getMaxX())
+			return getMaxX() - r->minX;
+		if (r->getCentreX() <= getCentreX() && minX < r->getMaxX())
+			return r->getMaxX() - minX;
+		return 0;
+	}
+	inline double overlapY(Rectangle *r) const {
+		if (getCentreY() <= r->getCentreY() && r->minY < getMaxY())
+			return getMaxY() - r->minY;
+		if (r->getCentreY() <= getCentreY() && minY < r->getMaxY())
+			return r->getMaxY() - minY;
+		return 0;
+	}
+private:
+	double minX,maxX,minY,maxY;
+};
+
+
+class Variable;
+class Constraint;
+
+// returns number of constraints generated
+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);
+
+
+#endif // SEEN_REMOVEOVERLAP_GENERATE_CONSTRAINTS_H
diff --git a/src/libvpsc/isnan.h b/src/libvpsc/isnan.h
new file mode 100644
index 000000000..388f9144b
--- /dev/null
+++ b/src/libvpsc/isnan.h
@@ -0,0 +1,57 @@
+#ifndef __ISNAN_H__
+#define __ISNAN_H__
+
+/*
+ * Temporary fix for various misdefinitions of isnan().
+ * isnan() is becoming undef'd in some .h files. 
+ * #include this last in your .cpp file to get it right.
+ *
+ * The problem is that isnan and isfinite are part of C99 but aren't part of
+ * the C++ standard (which predates C99).
+ *
+ * Authors:
+ *   Inkscape groupies and obsessive-compulsives
+ *
+ * Copyright (C) 2004 authors
+ *
+ * Released under GNU LGPL, read the file 'COPYING' for more information
+ *
+ * 2005 modification hereby placed in public domain.  Probably supercedes the 2004 copyright
+ * for the code itself.
+ */
+
+#include <math.h>
+/* You might try changing the above to <cmath> if you have problems.
+ * Whether you use math.h or cmath, you may need to edit the .cpp file
+ * and/or other .h files to use the same header file.
+ */
+
+#if defined(__isnan)
+# define isNaN(_a) (__isnan(_a))	/* MacOSX/Darwin definition < 10.4 */
+#elif defined(WIN32) || defined(_isnan)
+# define isNaN(_a) (_isnan(_a)) 	/* Win32 definition */
+#elif defined(isnan) || defined(__FreeBSD__)
+# define isNaN(_a) (isnan(_a))		/* GNU definition */
+#else
+# define isNaN(_a) (std::isnan(_a))
+#endif
+/* If the above doesn't work, then try (a != a).
+ * Also, please report a bug as per http://www.inkscape.org/report_bugs.php,
+ * giving information about what platform and compiler version you're using.
+ */
+
+
+#if defined(__isfinite)
+# define isFinite(_a) (__isfinite(_a))	/* MacOSX/Darwin definition < 10.4 */
+#elif defined(isfinite)
+# define isFinite(_a) (isfinite(_a))
+#else
+# define isFinite(_a) (std::isfinite(_a))
+#endif
+/* If the above doesn't work, then try (finite(_a) && !isNaN(_a)) or (!isNaN((_a) - (_a))).
+ * Also, please report a bug as per http://www.inkscape.org/report_bugs.php,
+ * giving information about what platform and compiler version you're using.
+ */
+
+
+#endif /* __ISNAN_H__ */
diff --git a/src/libvpsc/pairingheap/.dirstamp b/src/libvpsc/pairingheap/.dirstamp
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/src/libvpsc/pairingheap/.dirstamp
diff --git a/src/libvpsc/pairingheap/PairingHeap.cpp b/src/libvpsc/pairingheap/PairingHeap.cpp
new file mode 100644
index 000000000..202980b70
--- /dev/null
+++ b/src/libvpsc/pairingheap/PairingHeap.cpp
@@ -0,0 +1,333 @@
+/**
+ * \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:
+ *   Mark Allen Weiss
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+
+#include <vector>
+#include <list>
+#include "dsexceptions.h"
+#include "PairingHeap.h"
+
+#ifndef PAIRING_HEAP_CPP
+#define PAIRING_HEAP_CPP
+using namespace std;
+/**
+* Construct the pairing heap.
+*/
+template <class T>
+PairingHeap<T>::PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) )
+{
+	root = NULL;
+	counter=0;
+	this->lessThan=lessThan;
+}
+
+
+/**
+* Copy constructor
+*/
+template <class T>
+PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs )
+{
+	root = NULL;
+	counter=rhs->size();
+	*this = rhs;
+}
+
+/**
+* Destroy the leftist heap.
+*/
+template <class T>
+PairingHeap<T>::~PairingHeap( )
+{
+	makeEmpty( );
+}
+
+/**
+* Insert item x into the priority queue, maintaining heap order.
+* Return a pointer to the node containing the new item.
+*/
+template <class T>
+PairNode<T> *
+PairingHeap<T>::insert( const T & x )
+{
+	PairNode<T> *newNode = new PairNode<T>( x );
+
+	if( root == NULL )
+		root = newNode;
+	else
+		compareAndLink( root, newNode );
+	counter++;
+	return newNode;
+}
+template <class T>
+int PairingHeap<T>::size() {
+	return counter;
+}
+/**
+* Find the smallest item in the priority queue.
+* Return the smallest item, or throw Underflow if empty.
+*/
+template <class T>
+const T & PairingHeap<T>::findMin( ) const
+{
+	if( isEmpty( ) )
+		throw Underflow( );
+	return root->element;
+}
+/**
+ * Remove the smallest item from the priority queue.
+ * Throws Underflow if empty.
+ */
+template <class T>
+void PairingHeap<T>::deleteMin( )
+{
+    if( isEmpty( ) )
+        throw Underflow( );
+
+    PairNode<T> *oldRoot = root;
+
+    if( root->leftChild == NULL )
+        root = NULL;
+    else
+        root = combineSiblings( root->leftChild );
+	counter--;
+    delete oldRoot;
+}
+
+/**
+* Test if the priority queue is logically empty.
+* Returns true if empty, false otherwise.
+*/
+template <class T>
+bool PairingHeap<T>::isEmpty( ) const
+{
+	return root == NULL;
+}
+
+/**
+* Test if the priority queue is logically full.
+* Returns false in this implementation.
+*/
+template <class T>
+bool PairingHeap<T>::isFull( ) const
+{
+	return false;
+}
+
+/**
+* Make the priority queue logically empty.
+*/
+template <class T>
+void PairingHeap<T>::makeEmpty( )
+{
+	reclaimMemory( root );
+	root = NULL;
+}
+
+/**
+* Deep copy.
+*/
+template <class T>
+const PairingHeap<T> &
+PairingHeap<T>::operator=( const PairingHeap<T> & rhs )
+{
+	if( this != &rhs )
+	{
+		makeEmpty( );
+		root = clone( rhs.root );
+	}
+
+	return *this;
+}
+
+/**
+* Internal method to make the tree empty.
+* WARNING: This is prone to running out of stack space.
+*/
+template <class T>
+void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const
+{
+	if( t != NULL )
+	{
+		reclaimMemory( t->leftChild );
+		reclaimMemory( t->nextSibling );
+		delete t;
+	}
+}
+
+/**
+* Change the value of the item stored in the pairing heap.
+* Does nothing if newVal is larger than currently stored value.
+* p points to a node returned by insert.
+* newVal is the new value, which must be smaller
+*    than the currently stored value.
+*/
+template <class T>
+void PairingHeap<T>::decreaseKey( PairNode<T> *p,
+										  const T & newVal )
+{
+	if( lessThan(p->element,newVal) )
+		return;    // newVal cannot be bigger
+	p->element = newVal;
+	if( p != root )
+	{
+		if( p->nextSibling != NULL )
+			p->nextSibling->prev = p->prev;
+		if( p->prev->leftChild == p )
+			p->prev->leftChild = p->nextSibling;
+		else
+			p->prev->nextSibling = p->nextSibling;
+
+		p->nextSibling = NULL;
+		compareAndLink( root, p );
+	}
+}
+
+/**
+* Internal method that is the basic operation to maintain order.
+* Links first and second together to satisfy heap order.
+* first is root of tree 1, which may not be NULL.
+*    first->nextSibling MUST be NULL on entry.
+* second is root of tree 2, which may be NULL.
+* first becomes the result of the tree merge.
+*/
+template <class T>
+void PairingHeap<T>::
+compareAndLink( PairNode<T> * & first,
+			   PairNode<T> *second ) const
+{
+	if( second == NULL )
+		return;
+	if( lessThan(second->element,first->element) )
+	{
+		// Attach first as leftmost child of second
+		second->prev = first->prev;
+		first->prev = second;
+		first->nextSibling = second->leftChild;
+		if( first->nextSibling != NULL )
+			first->nextSibling->prev = first;
+		second->leftChild = first;
+		first = second;
+	}
+	else
+	{
+		// Attach second as leftmost child of first
+		second->prev = first;
+		first->nextSibling = second->nextSibling;
+		if( first->nextSibling != NULL )
+			first->nextSibling->prev = first;
+		second->nextSibling = first->leftChild;
+		if( second->nextSibling != NULL )
+			second->nextSibling->prev = second;
+		first->leftChild = second;
+	}
+}
+
+/**
+* Internal method that implements two-pass merging.
+* firstSibling the root of the conglomerate;
+*     assumed not NULL.
+*/
+template <class T>
+PairNode<T> *
+PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const
+{
+	if( firstSibling->nextSibling == NULL )
+		return firstSibling;
+
+	// Allocate the array
+	static vector<PairNode<T> *> treeArray( 5 );
+
+	// Store the subtrees in an array
+	int numSiblings = 0;
+	for( ; firstSibling != NULL; numSiblings++ )
+	{
+		if( numSiblings == (int)treeArray.size( ) )
+			treeArray.resize( numSiblings * 2 );
+		treeArray[ numSiblings ] = firstSibling;
+		firstSibling->prev->nextSibling = NULL;  // break links
+		firstSibling = firstSibling->nextSibling;
+	}
+	if( numSiblings == (int)treeArray.size( ) )
+		treeArray.resize( numSiblings + 1 );
+	treeArray[ numSiblings ] = NULL;
+
+	// Combine subtrees two at a time, going left to right
+	int i = 0;
+	for( ; i + 1 < numSiblings; i += 2 )
+		compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
+
+	int j = i - 2;
+
+	// j has the result of last compareAndLink.
+	// If an odd number of trees, get the last one.
+	if( j == numSiblings - 3 )
+		compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
+
+	// Now go right to left, merging last tree with
+	// next to last. The result becomes the new last.
+	for( ; j >= 2; j -= 2 )
+		compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
+	return treeArray[ 0 ];
+}
+
+/**
+* Internal method to clone subtree.
+* WARNING: This is prone to running out of stack space.
+*/
+template <class T>
+PairNode<T> *
+PairingHeap<T>::clone( PairNode<T> * t ) const
+{
+	if( t == NULL ) 
+		return NULL;
+	else
+	{
+		PairNode<T> *p = new PairNode<T>( t->element );
+		if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
+			p->leftChild->prev = p;
+		if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
+			p->nextSibling->prev = p;
+		return p;
+	}
+}
+template <class T>
+ostream& operator <<(ostream &os, const PairingHeap<T> &b)
+{
+	os<<"Heap:";
+	if (b.root != NULL) {
+		PairNode<T> *r = b.root;
+		list<PairNode<T>*> q;
+		q.push_back(r);
+		while (!q.empty()) {
+			r = q.front();
+			q.pop_front();
+			if (r->leftChild != NULL) {
+				os << *r->element << ">";
+				PairNode<T> *c = r->leftChild;
+				while (c != NULL) {
+					q.push_back(c);
+					os << "," << *c->element;
+					c = c->nextSibling;
+				}
+				os << "|";
+			}
+		}
+	}
+    return os;
+}
+#endif
diff --git a/src/libvpsc/pairingheap/PairingHeap.h b/src/libvpsc/pairingheap/PairingHeap.h
new file mode 100644
index 000000000..63c9badcf
--- /dev/null
+++ b/src/libvpsc/pairingheap/PairingHeap.h
@@ -0,0 +1,124 @@
+/**
+ * \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:
+ *   Mark Allen Weiss
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+#ifndef PAIRING_HEAP_H_
+#define PAIRING_HEAP_H_
+#include <stdlib.h>
+#include <fstream>
+// Pairing heap class
+//
+// CONSTRUCTION: with no parameters
+//
+// ******************PUBLIC OPERATIONS*********************
+// PairNode & insert( x ) --> Insert x
+// deleteMin( minItem )   --> Remove (and optionally return) smallest item
+// T findMin( )  --> Return smallest item
+// bool isEmpty( )        --> Return true if empty; else false
+// bool isFull( )         --> Return true if empty; else false
+// void makeEmpty( )      --> Remove all items
+// void decreaseKey( PairNode p, newVal )
+//                        --> Decrease value in node p
+// ******************ERRORS********************************
+// Throws Underflow as warranted
+
+
+// Node and forward declaration because g++ does
+// not understand nested classes.
+template <class T> 
+class PairingHeap;
+
+template <class T>
+std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
+
+template <class T>
+class PairNode
+{
+	friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
+	T   element;
+	PairNode    *leftChild;
+	PairNode    *nextSibling;
+	PairNode    *prev;
+
+	PairNode( const T & theElement ) :
+	       	element( theElement ),
+		leftChild(NULL), nextSibling(NULL), prev(NULL)
+       	{ }
+	friend class PairingHeap<T>;
+};
+
+template <class T>
+class Comparator
+{
+public:
+	virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
+};
+
+template <class T>
+class PairingHeap
+{
+	friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
+public:
+	PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
+	PairingHeap( const PairingHeap & rhs );
+	~PairingHeap( );
+
+	bool isEmpty( ) const;
+	bool isFull( ) const;
+	int size();
+
+	PairNode<T> *insert( const T & x );
+	const T & findMin( ) const;
+	void deleteMin( );
+	const T extractMin( ) {
+		T v = findMin();
+		deleteMin();
+		return v;
+	}
+	void makeEmpty( );
+	void decreaseKey( PairNode<T> *p, const T & newVal );
+	void merge( PairingHeap<T> *rhs )
+	{	
+		PairNode<T> *broot=rhs->getRoot();
+		if (root == NULL) {
+			if(broot != NULL) {
+				root = broot;
+			}
+		} else {
+			compareAndLink(root, broot);
+		}
+		counter+=rhs->size();
+	}
+
+	const PairingHeap & operator=( const PairingHeap & rhs );
+protected:
+	PairNode<T> * getRoot() {
+		PairNode<T> *r=root;
+		root=NULL;
+		return r;
+	}
+private:
+	PairNode<T> *root;
+	bool (*lessThan)(T const &lhs, T const &rhs);
+	int counter;
+	void reclaimMemory( PairNode<T> *t ) const;
+	void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
+	PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
+	PairNode<T> * clone( PairNode<T> * t ) const;
+};
+
+#include "PairingHeap.cpp"
+#endif
diff --git a/src/libvpsc/pairingheap/dsexceptions.h b/src/libvpsc/pairingheap/dsexceptions.h
new file mode 100644
index 000000000..bef2c78c5
--- /dev/null
+++ b/src/libvpsc/pairingheap/dsexceptions.h
@@ -0,0 +1,9 @@
+#ifndef DSEXCEPTIONS_H_
+#define DSEXCEPTIONS_H_
+
+class Underflow { };
+class Overflow  { };
+class OutOfMemory { };
+class BadIterator { };
+
+#endif
diff --git a/src/libvpsc/placement_SolveVPSC.h b/src/libvpsc/placement_SolveVPSC.h
new file mode 100644
index 000000000..9f1c10cda
--- /dev/null
+++ b/src/libvpsc/placement_SolveVPSC.h
@@ -0,0 +1,53 @@
+/* DO NOT EDIT THIS FILE - it is machine generated */
+#include <jni.h>
+/* Header for class placement_SolveVPSC */
+
+#ifndef _Included_placement_SolveVPSC
+#define _Included_placement_SolveVPSC
+#ifdef __cplusplus
+extern "C" {
+#endif
+/*
+ * Class:     placement_SolveVPSC
+ * Method:    solve
+ * Signature: ([Ljava/lang/String;[D[D[I[I[D[DI)D
+ */
+JNIEXPORT jdouble JNICALL Java_placement_SolveVPSC_solve
+  (JNIEnv *, jobject, jobjectArray, jdoubleArray, jdoubleArray, jintArray, jintArray, jdoubleArray, jdoubleArray, jint);
+
+/*
+ * Class:     placement_SolveVPSC
+ * Method:    generateXConstraints
+ * Signature: ([D[D[D[D[D)I
+ */
+JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateXConstraints
+  (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray);
+
+/*
+ * Class:     placement_SolveVPSC
+ * Method:    generateYConstraints
+ * Signature: ([D[D[D[D[D)I
+ */
+JNIEXPORT jint JNICALL Java_placement_SolveVPSC_generateYConstraints
+  (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray);
+
+/*
+ * Class:     placement_SolveVPSC
+ * Method:    getConstraints
+ * Signature: ([I[I[D)V
+ */
+JNIEXPORT void JNICALL Java_placement_SolveVPSC_getConstraints
+  (JNIEnv *, jobject, jintArray, jintArray, jdoubleArray);
+
+/*
+ * Class:     placement_SolveVPSC
+ * Method:    removeOverlaps
+ * Signature: ([D[D[D[D)V
+ */
+JNIEXPORT void JNICALL Java_placement_SolveVPSC_removeOverlaps
+  (JNIEnv *, jobject, jdoubleArray, jdoubleArray, jdoubleArray, jdoubleArray);
+
+#ifdef __cplusplus
+}
+#endif
+#endif
diff --git a/src/libvpsc/remove_rectangle_overlap.cpp b/src/libvpsc/remove_rectangle_overlap.cpp
new file mode 100644
index 000000000..6f6ace03a
--- /dev/null
+++ b/src/libvpsc/remove_rectangle_overlap.cpp
@@ -0,0 +1,116 @@
+/**
+ * \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"
+#include "solve_VPSC.h"
+#include "variable.h"
+#include "constraint.h"
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
+#include "blocks.h"
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+
+#define EXTRA_GAP 0.0001
+
+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) {
+	assert(0 <= n);
+	try {
+	// The extra gap avoids numerical imprecision problems
+	Rectangle::setXBorder(xBorder+EXTRA_GAP);
+	Rectangle::setYBorder(yBorder+EXTRA_GAP);
+	Variable **vs=new Variable*[n];
+	for(int i=0;i<n;i++) {
+		vs[i]=new Variable(i,0,1);
+	}
+	Constraint **cs;
+	double *oldX = new double[n];
+	int m=generateXConstraints(n,rs,vs,cs,true);
+	for(int i=0;i<n;i++) {
+		oldX[i]=vs[i]->desiredPosition;
+	}
+	VPSC vpsc_x(n,vs,m,cs);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	f<<"Calling VPSC: Horizontal pass 1"<<endl;
+	f.close();
+#endif
+	vpsc_x.solve();
+	for(int i=0;i<n;i++) {
+		rs[i]->moveCentreX(vs[i]->position());
+	}
+	for(int i = 0; i < m; ++i) {
+		delete cs[i];
+	}
+	delete [] cs;
+	// 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(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;
+	f.close();
+#endif
+	vpsc_y.solve();
+	for(int i=0;i<n;i++) {
+		rs[i]->moveCentreY(vs[i]->position());
+		rs[i]->moveCentreX(oldX[i]);
+	}
+	delete [] oldX;
+	for(int i = 0; i < m; ++i) {
+		delete cs[i];
+	}
+	delete [] cs;
+	Rectangle::setYBorder(Rectangle::yBorder-EXTRA_GAP);
+	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;
+	} 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/libvpsc/remove_rectangle_overlap.h b/src/libvpsc/remove_rectangle_overlap.h
new file mode 100644
index 000000000..08b035e31
--- /dev/null
+++ b/src/libvpsc/remove_rectangle_overlap.h
@@ -0,0 +1,21 @@
+#ifndef REMOVE_RECTANGLE_OVERLAP_H_SEEN
+#define REMOVE_RECTANGLE_OVERLAP_H_SEEN
+
+/**
+ * \file Declaration of main internal remove-overlaps function.
+ */
+/*
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+
+class Rectangle;
+
+void removeRectangleOverlap(unsigned n, Rectangle *rs[], double xBorder, double yBorder);
+
+
+#endif /* !REMOVE_RECTANGLE_OVERLAP_H_SEEN */
diff --git a/src/libvpsc/solve_VPSC.cpp b/src/libvpsc/solve_VPSC.cpp
new file mode 100644
index 000000000..44918951d
--- /dev/null
+++ b/src/libvpsc/solve_VPSC.cpp
@@ -0,0 +1,417 @@
+/**
+ * \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.
+ */
+
+#include <cassert>
+#include "constraint.h"
+#include "block.h"
+#include "blocks.h"
+#include "solve_VPSC.h"
+#include <math.h>
+#include <sstream>
+#ifdef RECTANGLE_OVERLAP_LOGGING
+#include <fstream>
+using std::ios;
+using std::ofstream;
+using std::endl;
+#endif
+
+using std::ostringstream;
+using std::list;
+using std::set;
+
+static const double ZERO_UPPERBOUND=-0.0000001;
+
+IncVPSC::IncVPSC(const unsigned n, Variable* const 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* const vs[], const unsigned m, Constraint *cs[]) : m(m), cs(cs), n(n), vs(vs) {
+	bs=new Blocks(n, vs);
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	printBlocks();
+	assert(!constraintGraphIsCyclic(n,vs));
+#endif
+}
+VPSC::~VPSC() {
+	delete bs;
+}
+
+// useful in debugging
+void VPSC::printBlocks() {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+	ofstream f(LOGFILE,ios::app);
+	for(set<Block*>::iterator i=bs->begin();i!=bs->end();++i) {
+		Block *b=*i;
+		f<<"  "<<*b<<endl;
+	}
+	for(unsigned i=0;i<m;i++) {
+		f<<"  "<<*cs[i]<<endl;
+	}
+#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 VPSC::satisfy() {
+	list<Variable*> *vs=bs->totalOrder();
+	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(unsigned i=0;i<m;i++) {
+		if(cs[i]->slack() < ZERO_UPPERBOUND) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			ofstream f(LOGFILE,ios::app);
+			f<<"Error: Unsatisfied constraint: "<<*cs[i]<<endl;
+#endif
+			//assert(cs[i]->slack()>-0.0000001);
+			throw "Unsatisfied constraint";
+		}
+	}
+	delete vs;
+}
+
+void VPSC::refine() {
+	bool solved=false;
+	// Solve shouldn't loop indefinately
+	// ... but just to make sure we limit the number of iterations
+	unsigned maxtries=100;
+	while(!solved&&maxtries>=0) {
+		solved=true;
+		maxtries--;
+		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) {
+			Block *b=*i;
+			Constraint *c=b->findMinLM();
+			if(c!=NULL && c->lm<0) {
+#ifdef RECTANGLE_OVERLAP_LOGGING
+				ofstream f(LOGFILE,ios::app);
+				f<<"Split on constraint: "<<*c<<endl;
+#endif
+				// Split on c
+				Block *l=NULL, *r=NULL;
+				bs->split(b,l,r,c);
+				bs->cleanup();
+				// split alters the block set so we have to restart
+				solved=false;
+				break;
+			}
+		}
+	}
+	for(unsigned i=0;i<m;i++) {
+		if(cs[i]->slack() < ZERO_UPPERBOUND) {
+			assert(cs[i]->slack()>ZERO_UPPERBOUND);
+			throw "Unsatisfied constraint";
+		}
+	}
+}
+/**
+ * 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 VPSC::solve() {
+	satisfy();
+	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 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 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() < ZERO_UPPERBOUND)) {
+		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() < ZERO_UPPERBOUND) {
+			ostringstream s;
+			s<<"Unsatisfied constraint: "<<*v;
+#ifdef RECTANGLE_OVERLAP_LOGGING
+			ofstream f(LOGFILE,ios::app);
+			f<<s.str()<<endl;
+#endif
+			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 < ZERO_UPPERBOUND) {
+			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();
+}
+
+/**
+ * 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<ZERO_UPPERBOUND||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>
+using std::map;
+using std::vector;
+struct node {
+	set<node*> in;
+	set<node*> out;
+};
+// useful in debugging - cycles would be BAD
+bool VPSC::constraintGraphIsCyclic(const unsigned n, Variable *vs[]) {
+	map<Variable*, node*> varmap;
+	vector<node*> graph;
+	for(unsigned i=0;i<n;i++) {
+		node *u=new node;
+		graph.push_back(u);
+		varmap[vs[i]]=u;
+	}
+	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) {
+			Variable *r=(*c)->right;
+			varmap[vs[i]]->out.insert(varmap[r]);
+		}
+	}
+	while(graph.size()>0) {
+		node *u=NULL;
+		vector<node*>::iterator i=graph.begin();
+		for(;i!=graph.end();++i) {
+			u=*i;
+			if(u->in.size()==0) {
+				break;
+			}
+		}
+		if(i==graph.end() && graph.size()>0) {
+			//cycle found!
+			return true;
+		} else {
+			graph.erase(i);
+			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) {
+		delete graph[i];
+	}
+	return false;
+}
+
+// useful in debugging - cycles would be BAD
+bool VPSC::blockGraphIsCyclic() {
+	map<Block*, node*> bmap;
+	vector<node*> graph;
+	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) {
+		Block *b=*i;
+		b->setUpInConstraints();
+		Constraint *c=b->findMinInConstraint();
+		while(c!=NULL) {
+			Block *l=c->left->block;
+			bmap[b]->in.insert(bmap[l]);
+			b->deleteMinInConstraint();
+			c=b->findMinInConstraint();
+		}
+
+		b->setUpOutConstraints();
+		c=b->findMinOutConstraint();
+		while(c!=NULL) {
+			Block *r=c->right->block;
+			bmap[b]->out.insert(bmap[r]);
+			b->deleteMinOutConstraint();
+			c=b->findMinOutConstraint();
+		}
+	}
+	while(graph.size()>0) {
+		node *u=NULL;
+		vector<node*>::iterator i=graph.begin();
+		for(;i!=graph.end();++i) {
+			u=*i;
+			if(u->in.size()==0) {
+				break;
+			}
+		}
+		if(i==graph.end() && graph.size()>0) {
+			//cycle found!
+			return true;
+		} else {
+			graph.erase(i);
+			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++) {
+		delete graph[i];
+	}
+	return false;
+}
+
diff --git a/src/libvpsc/solve_VPSC.h b/src/libvpsc/solve_VPSC.h
new file mode 100644
index 000000000..4cd5559d6
--- /dev/null
+++ b/src/libvpsc/solve_VPSC.h
@@ -0,0 +1,66 @@
+/**
+ * \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.
+ */
+
+//
+// TODO: Really, we should have three classes: VPSC, IncrementalVPSC and
+// StaticVPSC, where the latter two inherit from VPSC.  StaticVPSC would be
+// the equivalent of what is currently VPSC.
+// Also, a lot of the code specific to one or other of these concrete
+// implementations should be moved from Block and Blocks: e.g. mergeLeft etc.
+//
+#ifndef SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
+#define SEEN_REMOVEOVERLAP_SOLVE_VPSC_H
+
+#include <vector>
+class Variable;
+class Constraint;
+class Blocks;
+
+/**
+ * Variable Placement with Separation Constraints problem instance
+ */
+class VPSC {
+public:
+	virtual void satisfy();
+	virtual void solve();
+
+	VPSC(const unsigned n, Variable* const vs[], const unsigned m, Constraint *cs[]);
+	virtual ~VPSC();
+	Constraint** getConstraints(unsigned &m) { m=this->m; return cs; }
+	const Variable* const * getVariables(unsigned &n) { n=this->n; return vs; }
+protected:
+	Blocks *bs;
+	unsigned m;
+	Constraint **cs;
+	unsigned n;
+	const Variable* const *vs;
+	void printBlocks();
+private:
+	void refine();
+	bool constraintGraphIsCyclic(const unsigned n, Variable *vs[]);
+	bool blockGraphIsCyclic();
+};
+
+class IncVPSC : public VPSC {
+public:
+	unsigned splitCnt;
+	void satisfy();
+	void solve();
+	void moveBlocks();
+	void splitBlocks();
+	IncVPSC(const unsigned n, Variable* const 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/libvpsc/variable.cpp b/src/libvpsc/variable.cpp
new file mode 100644
index 000000000..1890f788e
--- /dev/null
+++ b/src/libvpsc/variable.cpp
@@ -0,0 +1,15 @@
+/**
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+#include "variable.h"
+std::ostream& operator <<(std::ostream &os, const Variable &v) {
+	os << "(" << v.id << "=" << v.position() << ")";
+	return os;
+}
+
diff --git a/src/libvpsc/variable.h b/src/libvpsc/variable.h
new file mode 100644
index 000000000..b1ab66c95
--- /dev/null
+++ b/src/libvpsc/variable.h
@@ -0,0 +1,51 @@
+/**
+ *
+ * Authors:
+ *   Tim Dwyer <tgdwyer@gmail.com>
+ *
+ * Copyright (C) 2005 Authors
+ *
+ * Released under GNU LGPL.  Read the file 'COPYING' for more information.
+ */
+#ifndef SEEN_REMOVEOVERLAP_VARIABLE_H
+#define SEEN_REMOVEOVERLAP_VARIABLE_H
+
+#include <vector>
+#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:
+	const int id; // useful in log files
+	double desiredPosition;
+	const double weight;
+	double offset;
+	Block *block;
+	bool visited;
+	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)
+	{
+	}
+	inline double position() const {
+		return block->posn+offset;
+	}
+	//double position() const;
+	~Variable(void){
+		in.clear();
+		out.clear();
+	}
+};
+#endif // SEEN_REMOVEOVERLAP_VARIABLE_H