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, 0 insertions, 303 deletions

diff --git a/src/removeoverlap/generate-constraints.cpp b/src/removeoverlap/generate-constraints.cpp
deleted file mode 100644
index 312ad960b..000000000
--- a/src/removeoverlap/generate-constraints.cpp
+++ /dev/null
@@ -1,303 +0,0 @@
-/**
- * \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;
-}