Need help recursively pulling in a parent's parent to create a tree R

user_14450054 0
Viewed 26

I have a dataframe that looks like this:

name manager
John Bill
Bill David
David Sarah
Sarah 
name = c("John","Bill","David","Sarah")
manager = c("Bill","David","Sarah","")
df = data.frame(name,manager)

(Sarah is the top of the ladder) I'm just trying to do a simple lookup to pull in John's manager's manager (David). Ideally I would like a recursive loop in R that will run through my dataset and create an output that lists all the managers above each person such as this:

name manager output
John Bill Bill_David_Sarah
Bill David David_Sarah
David Sarah Sarah
Sarah

Also please note, my data is not ordered in such a manner, and a manager can manage multiple people, its not one to one. Any help would be appreciated thanks!

tree recursion r lookup
1 Answers

Here is a solution with igraph. Create a directed graph from the data.frame, then a sequence of lapply loops extracts the information needed.

name = c("John","Bill","David","Sarah")
manager = c("Bill","David","Sarah","")
df = data.frame(name,manager)

suppressPackageStartupMessages(library(igraph))

g <- graph_from_data_frame(df)
plot(g)


ll <- lapply(V(g), \(v) all_simple_paths(g, from = v, to = V(g)[V(g) != v]))
ll <- lapply(ll, \(l) l[length(l)])
df$output <- sapply(ll[-length(ll)], \(l) {
  if(length(l) > 0) {
    inx <- eval(parse(text = l))[-1]
    nms <- names(ll)[ V(g)[inx] ]
    paste(nms[nms != ""], collapse = "_")
  } else ""
})

df
#>    name manager           output
#> 1  John    Bill Bill_David_Sarah
#> 2  Bill   David      David_Sarah
#> 3 David   Sarah            Sarah
#> 4 Sarah

Created on 2022-05-27 by the reprex package (v2.0.1)

user_82454060
Related