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

diff --git a/src/libcola/shortest_paths.cpp b/src/libcola/shortest_paths.cpp
new file mode 100644
index 000000000..4f4183b07
--- /dev/null
+++ b/src/libcola/shortest_paths.cpp
@@ -0,0 +1,100 @@
+// vim: set cindent 
+// vim: ts=4 sw=4 et tw=0 wm=0
+#include "shortest_paths.h"
+#include <float.h>
+#include <cassert>
+#include <iostream>
+#include <libvpsc/pairingheap/PairingHeap.h>
+using namespace std;
+namespace shortest_paths {
+// O(n^3) time.  Slow, but fool proof.  Use for testing.
+void floyd_warshall(
+        unsigned n,
+        double** D, 
+        vector<Edge>& es,
+        double* eweights) 
+{
+    for(unsigned i=0;i<n;i++) {
+        for(unsigned j=0;j<n;j++) {
+            if(i==j) D[i][j]=0;
+            else D[i][j]=DBL_MAX;
+        }
+    }
+    for(unsigned i=0;i<es.size();i++) {
+        unsigned u=es[i].first, v=es[i].second;
+        assert(u<n&&v<n);
+        D[u][v]=D[v][u]=eweights[i];
+    }
+    for(unsigned k=0; k<n; k++) {
+        for(unsigned i=0; i<n; i++) {
+            for(unsigned j=0; j<n; j++) {
+                D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
+            }
+        }
+    }
+}
+void dijkstra_init(Node* vs, vector<Edge>& es, double* eweights) {
+    for(unsigned i=0;i<es.size();i++) {
+        unsigned u=es[i].first, v=es[i].second;
+        vs[u].neighbours.push_back(&vs[v]);
+        vs[u].nweights.push_back(eweights[i]);
+        vs[v].neighbours.push_back(&vs[u]);
+        vs[v].nweights.push_back(eweights[i]);
+    }
+}
+void dijkstra(
+        unsigned s,
+        unsigned n,
+        Node* vs,
+        double* d)
+{
+    assert(s<n);
+    for(unsigned i=0;i<n;i++) {
+        vs[i].id=i;
+        vs[i].d=DBL_MAX;
+        vs[i].p=NULL;
+    }
+    vs[s].d=0;
+    PairingHeap<Node*> Q(&compareNodes);
+    for(unsigned i=0;i<n;i++) {
+        vs[i].qnode = Q.insert(&vs[i]);
+    }
+    while(!Q.isEmpty()) {
+        Node *u=Q.extractMin();
+        d[u->id]=u->d;
+        for(unsigned i=0;i<u->neighbours.size();i++) {
+            Node *v=u->neighbours[i];
+            double w=u->nweights[i];
+            if(v->d>u->d+w) {
+                v->p=u;
+                v->d=u->d+w;
+                Q.decreaseKey(v->qnode,v);
+            }
+        }
+    }
+}
+void dijkstra(
+        unsigned s,
+        unsigned n,
+        double* d,
+        vector<Edge>& es,
+        double* eweights)
+{
+    assert(s<n);
+    Node vs[n];
+    dijkstra_init(vs,es,eweights);
+    dijkstra(s,n,vs,d);
+}
+void johnsons(
+        unsigned n,
+        double** D, 
+        vector<Edge>& es,
+        double* eweights) 
+{
+    Node vs[n];
+    dijkstra_init(vs,es,eweights);
+    for(unsigned k=0;k<n;k++) {
+        dijkstra(k,n,vs,D[k]);
+    }
+}
+}