spaceblog

graph maths

shifted the eigenvectors used for the coordinates by one, and got a better layout for the nodes at the leaves of the tree, which made it possible to take a screenshot host colouring I added on Sunday, which was pretty trivial but the algorithm was placing all the wireless nodes at the same point in 3-space.

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.

Pie Day!

and keeping with the mathematics, here’s an octave version of conway’s game of life! thanks sasha! happy birthday!

N=100;
axis([0 N+1 0 N+1], "manual","square", "nolabel");
H=diag(ones(1, N-1), 1) + diag(ones(1, N-1), -1) + eye(N);
A=round(rand(N));
for i =1:1000;
 An = H*A*H-A;
 A(find(An<2 | An>3)) = 0;
 A(find(An==3)) = 1;

 [x, y] = find(A);
 plot(x, y, 'o;;');
 pause(0.2);
end;

that should answer benno’s question.

Happy Pie Day!