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, 68 deletions

diff --git a/src/removeoverlap/block.h b/src/removeoverlap/block.h
deleted file mode 100644
index 997009a55..000000000
--- a/src/removeoverlap/block.h
+++ /dev/null
@@ -1,68 +0,0 @@
-/**
- * \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
-{
-	friend std::ostream& operator <<(std::ostream &os,const Block &b);
-public:
-	std::vector<Variable*> *vars;
-	double posn;
-	double weight;
-	double wposn;
-	Block(Variable *v=NULL);
-	~Block(void);
-	Constraint* findMinLM();
-	Constraint* findMinLMBetween(Variable* lv, Variable* rv);
-	Constraint* findMinInConstraint();
-	Constraint* findMinOutConstraint();
-	void deleteMinInConstraint();
-	void deleteMinOutConstraint();
-	double desiredWeightedPosition();
-	void merge(Block *b, Constraint *c, double dist);
-	void merge(Block *b, Constraint *c);
-	void mergeIn(Block *b);
-	void mergeOut(Block *b);
-	void split(Block *&l, Block *&r, Constraint *c);
-	Constraint* splitBetween(Variable* vl, Variable* vr, Block* &lb, Block* &rb);
-	void setUpInConstraints();
-	void setUpOutConstraints();
-	double cost();
-	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 *v, Variable *u);
-	double compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm);
-	Pair compute_dfdv_between(
-			Variable*, Variable*, Variable*, Direction, bool);
-	bool canFollowLeft(Constraint *c, Variable *last);
-	bool canFollowRight(Constraint *c, Variable *last);
-	void populateSplitBlock(Block *b, Variable *v, Variable *u);
-	void addVariable(Variable *v);
-	void setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in);
-};
-
-#endif // SEEN_REMOVEOVERLAP_BLOCK_H