woohoo

woohoo

Finally!

function u = layout(L, M)
% finds a layout for the graph G(L, M) using Halls energy
%  L is the laplacian of the graph G
%  M is the mass matrix

% calculate composite graph
B = M^(-1/2) * L * M^(-1/2) ;

% v = M^(-1/2) * u
% insert approprate algorithm here [Lanczos, RQI, PI, ACE]
[v, d] = eig(B) ;

% u are the resulting eigenvectors  
% disgard the first column
% the second column is the Fiedler vector
% subsequent columns are the coordinates in n-space
u = M^(1/2) * v ;

end

So for anyone (especially those who wish they did better than a 50 average in first year maths) trying to wrap their heads around Koren et al’s ACE algorithm, the key is that it’s 2 paragraphs identifying the actual method used and 36.5 pages describing a way to make it really fast.

So, armed with this knowledge I now have something already significantly faster than the old iterative O(e^inf) physics model. Hooray for maths!

I just wish it hadn’t taken me a month or more to understand it :-)

So here’s some GNU Octave (and thus it probably works in Matlab too) that plots the example from the ACE paper:

L = [9 -5 0 -4 0;-5 17 -2 -7 -3; 0 -2 4 -2 0;-4 -7 -2 19 -6;0 -3 0 -6 9;]
M = eye(5)

u = layout(L, M)

x = u(:,2) ;
y = u(:,3) ;

plot([x(1);x(2)], [y(1);y(2)], "@16-;;",
     [x(1);x(4)], [y(1);y(4)], "@16-;;",
     [x(2);x(3)], [y(2);y(3)], "@16-;;",
     [x(4);x(5)], [y(4);y(5)], "@16-;;",
     [x(3);x(4)], [y(3);y(4)], "@16-;;",
     [x(2);x(4)], [y(2);y(4)], "@16-;;",
     [x(2);x(5)], [y(2);y(5)], "@16-;;")

Writing a plot function that iterates over the edge list (or for bonus points, the Laplacian) is left as an excercise for the reader.