[clug] Anyone want to give a talk for this week's PSIG meeting?

[Kevin Pulo]

On Tue, Oct 12, 2010 at 11:35:12AM +1100, Ivan Lazar Miljenovic wrote:

> How do you make a set of vertices and a set of pair-wise relationships
> between those vertices "nice"? :p

Simple.  Define a function f:(n)->(x,y) that maps each node to a point
in the plane (or a point (x,y,z) in 3-space, if you think that'll
help) and one g:(n1,n2,t)->(x,y) that maps each pair of related nodes
and a parameter (between 0 and 1) to a point (such that g(n1,n2,0) =
f(n1), g(n1,n2,1) = f(n2), and g(n1,n2,t) is continuously
differentiable over t [0,1]), in such a way that you minimise
w1*sum(h1(n,m)) + w2*sum(h2(n1,n2,m1,m2)) for all nodes
n,m,n1,n2,m1,m2 such that n != m && n1 != m1 && n2 != m2, where
h1(n,m) is defined as (f(n) == f(m) ? 1 : 0) and h2(n1,n2,m1,m2) is
defined as the number of pairs (t1,t2) such that g(n1,n2,t1) ==
g(m1,m2,t2), for given weights w1 and w2 - or you could choose to find
suitable functions that maximise some other niceness metric, if you
think that'd be better.  Disclaimer: part of my PhD involved graph
drawing.  Are we off-topic yet?  ;)

Kev

-- 
Kevin Pulo
kev at pulo.com.au
http://www.kev.pulo.com.au/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/linux/attachments/20101012/4aa3688c/attachment.pgp>