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

[Gesmann, Markus]

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



************LNSCNTMCS01***************************************************
The information in this E-Mail and in any attachments is CONFIDENTIAL and may be privileged.  If you are NOT the intended recipient, please destroy this message and notify the sender immediately.  You should NOT retain, copy or use this E-mail for any purpose, nor disclose all or any part of its contents to any other person or persons.

Any views expressed in this message are those of the individual sender, EXCEPT where the sender specifically states them to be the views of Lloyd's.

Lloyd's may monitor the content of E-mails sent and received via its
network for viruses or unauthorised use and for other lawful
business purposes."

Lloyd's is authorised under the Financial Services and Markets Act 2000