From: Gabor Grothendieck <ggrothendieck_at_myway.com>

Date: Wed 09 Mar 2005 - 04:19:12 EST

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 Received on Wed Mar 09 04:49:48 2005

Date: Wed 09 Mar 2005 - 04:19:12 EST

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.

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 Received on Wed Mar 09 04:49:48 2005

*
This archive was generated by hypermail 2.1.8
: Fri 03 Mar 2006 - 03:30:41 EST
*