[R] To convert an adjacency list model into a nested set model
Gabor Grothendieck
ggrothendieck at myway.com
Tue Mar 8 18:19:12 CET 2005
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.
More information about the R-help
mailing list