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=en&lr=lang_en&selm=8j0n05%24n31%241 : %40nnrp1.deja.com : : Assume you have a tree structure like this : Albert : / \ : / \ : Bert Chuck : / | \ : / | \ : / | \ : / | \ : Donna Eddie 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. ______________________________________________ [email protected] mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
