Re: [R] To convert an adjacency list model into a nested set model
Gabor == Gabor Grothendieck [EMAIL PROTECTED] on Tue, 8 Mar 2005 17:19:12 + (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. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
[R] To convert an adjacency list model into a nested set model
Dear R-help I am wondering if somebody wrote some code to convert an adjacency list model into a nested set model. In principal I want to do the same as John Celko mentioned it here with SQL: http://groups.google.co.uk/groups?hl=enlr=lang_enselm=8j0n05%24n31%241 %40nnrp1.deja.com Assume you have a tree structure like this Albert / \ / \ BertChuck /| \ / | \ /| \ / | \ DonnaEddie Fred in an adjacency list model: emp=c(Albert, Bert, Chuck, Donna, Eddie, Fred) boss=c(NA, Albert, Albert, Chuck, Chuck, Chuck) print(Personnel-data.frame(emp, boss)) emp boss 1 Albert NA 2 Bert Albert 3 Chuck Albert 4 Donna Chuck 5 Eddie Chuck 6 Fred Chuck Then it is quite hard to find the all the supervisors of one employee. John's suggestion is to convert the adjacency list model into a nested set model. The organizational chart would look like this as a directed graph: Albert (1,12) /\ /\ Bert (2,3)Chuck (4,11) /| \ / | \ /| \ / | \ Donna (5,6) Eddie (7,8) Fred (9,10) The data is than stored in the following form: lft=c(1,2,4,5,7,9) rgt=c(12,3,11,6,8,10) print(Per-data.frame(emp, lft, rgt)) emp lft rgt 1 Albert 1 12 2 Bert 2 3 3 Chuck 4 11 4 Donna 5 6 5 Eddie 7 8 6 Fred 9 10 To find now the supervisor of an employee all you have to do is to look where the employees lft figure is between lft and rgt. The supervisors of Eddie are therefore subset(Per, lft 7 rgt 7) emp lft rgt 1 Albert 1 12 3 Chuck 4 11 In the site mentioned above John provides also some code to transform a adjacency list model into a nested set model. Does somebody know if there is already a package for this in R? Kind Regards Markus Gesmann LNSCNTMCS01*** The information in this E-Mail and in any attachments is CONFIDENTIAL and may be privileged. If you are NOT the intended recipient, please destroy this message and notify the sender immediately. You should NOT retain, copy or use this E-mail for any purpose, nor disclose all or any part of its contents to any other person or persons. Any views expressed in this message are those of the individual sender, EXCEPT where the sender specifically states them to be the views of Lloyd's. Lloyd's may monitor the content of E-mails sent and received via its network for viruses or unauthorised use and for other lawful business purposes. Lloyd's is authorised under the Financial Services and Markets Act 2000 __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Re: [R] To convert an adjacency list model into a nested set model
Gesmann, Markus Markus.Gesmann at lloyds.com writes: : : Dear R-help : : I am wondering if somebody wrote some code to convert an adjacency list : model into a nested set model. : In principal I want to do the same as John Celko mentioned it here with : SQL: : http://groups.google.co.uk/groups?hl=enlr=lang_enselm=8j0n05%24n31%241 : %40nnrp1.deja.com : : Assume you have a tree structure like this : Albert : / \ :/ \ : BertChuck :/| \ : / | \ :/| \ : / | \ : DonnaEddie Fred : : in an adjacency list model: : : emp=c(Albert, Bert, Chuck, Donna, Eddie, Fred) : boss=c(NA, Albert, Albert, Chuck, Chuck, Chuck) : print(Personnel-data.frame(emp, boss)) : emp boss : 1 Albert NA : 2 Bert Albert : 3 Chuck Albert : 4 Donna Chuck : 5 Eddie Chuck : 6 Fred Chuck : : Then it is quite hard to find the all the supervisors of one employee. : John's suggestion is to convert the adjacency list model into a nested : set model. : The organizational chart would look like this as a directed graph: : : Albert (1,12) : /\ : /\ : Bert (2,3)Chuck (4,11) :/| \ : / | \ :/| \ : / | \ : Donna (5,6) Eddie (7,8) Fred (9,10) : : The data is than stored in the following form: : : lft=c(1,2,4,5,7,9) : rgt=c(12,3,11,6,8,10) : print(Per-data.frame(emp, lft, rgt)) : emp lft rgt : 1 Albert 1 12 : 2 Bert 2 3 : 3 Chuck 4 11 : 4 Donna 5 6 : 5 Eddie 7 8 : 6 Fred 9 10 : : To find now the supervisor of an employee all you have to do is to look : where the employees lft figure is between lft and rgt. The supervisors : of Eddie are therefore : subset(Per, lft 7 rgt 7) : emp lft rgt : 1 Albert 1 12 : 3 Chuck 4 11 : : In the site mentioned above John provides also some code to transform a : adjacency list model into a nested set model. : Does somebody know if there is already a package for this in R? : : Kind Regards : : Markus Gesmann : This is not a direct answer to getting a nesting from an adjacency but the following is easy to do and gives all the same info. Note that if A is the adjacency matrix of children (rows) and ] parents (columns) then A^n is the matrix defining ancestors n generations away and exp(A) is a weighted version of that with A^i weighted by i! (These expressions are mathematics, not R.) Thus: empf - factor(emp, level = union(emp, boss)) # emp as factor bossf - factor(boss, level = union(emp, boss)) # ditto for boss adj - table(empf, bossf) # i,j is 1 if j is boss of i library(rmutil) # http://popgen.unimaas.nl/~jlindsey/rcode.html mexp(adj, type = series) - diag(length(empf)) giving a matrix whose i,j-th entry is 1/n! if j is n-generations above i. From that you can get the info you need. __ R-help@stat.math.ethz.ch mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
