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

From: Gabor Grothendieck <ggrothendieck_at_myway.com>
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:
: %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