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

diff --git a/src/removeoverlap/variable.h b/src/removeoverlap/variable.h
deleted file mode 100644
index b1ab66c95..000000000
--- a/src/removeoverlap/variable.h
+++ /dev/null
@@ -1,51 +0,0 @@
-/**
- *
- * 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