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)

1 files changed, 124 insertions, 0 deletions

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;
+}
+}