[R] To convert an adjacency list model into a nested set model

[Gabor Grothendieck]

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.