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.