[R] To convert an adjacency list model into a nested set model
Martin Maechler
maechler at stat.math.ethz.ch
Wed Mar 9 10:14:34 CET 2005
>>>>> "Gabor" == Gabor Grothendieck <ggrothendieck at myway.com>
>>>>> on Tue, 8 Mar 2005 17:19:12 +0000 (UTC) writes:
<..............>
Gabor> This is not a direct answer to getting a nesting from
Gabor> an adjacency but the following is easy to do and
Gabor> gives all the same info.
Gabor> Note that if A is the adjacency matrix of children
Gabor> (rows) and ] parents (columns) then A^n is the matrix
Gabor> defining ancestors n generations away and exp(A) is a
Gabor> weighted version of that with A^i weighted by i!
Gabor> (These expressions are mathematics, not R.) Thus:
Gabor> empf <- factor(emp, level = union(emp, boss)) # emp as factor
Gabor> bossf <- factor(boss, level = union(emp, boss)) # ditto for boss
Gabor> adj <- table(empf, bossf) # i,j is 1 if j is boss of i
Gabor> library(rmutil) # http://popgen.unimaas.nl/~jlindsey/rcode.html
Gabor> mexp(adj, type = "series") - diag(length(empf))
just a note on the matrix exponential:
The Matrix package (from CRAN) now also has the matrix
exponential, expm(.) ,
using the ''least dubious '' algorithm of
Moler, C. and Van Loan C. (2003)
"Ninteen dubious ways to compute the exponential of a
matrix, twenty-five years later".
SIAM review 45, 3--49
namely the one also in use by Matlab and Octave
So the above would be something like
library(Matrix)
expm( as(adj, "dgeMatrix") ) - as(diag(length(empf)), "dgeMatrix")
Gabor> giving a matrix whose i,j-th entry is 1/n! if j is
Gabor> n-generations above i.
Gabor> From that you can get the info you need.
More information about the R-help
mailing list