spaceblog

DNS Bajaj is a neat tool for checking the delegation of a domain; all admins should add it to their toolbox. (Mine is a bookmark menu full of looking glasses, Sam Spade and other useful remote query tools).

I just saw Walter Zorn’s JavaScript vector graphics library on NTK, this is killer-totally-sweet.

But I’m still trying to find a legitimate use for the insurmountable opportunity that is the block diagrams in CSS.

I’m thinking web UI for umbrella, perhaps network maps in JS vector graphics, and rack diagrams using the CSS technique.

Perhaps they can be bred to form an unholy breed of ubergraphics!

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.

I just brute-forced NXE onto my test nagios server here at home, and hacked up an XML-RPC client in python… mere minutes later umbrella had a new command to update the node attributes with nagios statuses.

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.