用更聪明的算法在R中完成递归搜索功能？

Question

我知道这是比R相关的算法，但我想知道解决方案是否存在于任何存在的R包中。此代码示例标识员工的第一个经理，即VP。是否有更快的方法对大量数据进行此操作？好像是深度第一次搜索。这能用graph.dfs来实现吗？

x <- data.frame(employee=c('xy', 'abc', 'zz', 'xx', 'yy', 'ww'), manager=c('abc', 'zz', 'xx', 'yy', 'ww', 'uu'), level=c('dir', 'man', 'vp', 'vp', 'man', 'vp'))
emps <- as.character(unique(x$employee))
x$employee<-as.character(x$employee)
x$manager<-as.character(x$manager)

findVP <- function(emp){
    employee <- x[which(x$employee == emp),]
    if(employee$level == 'vp'){
        return (emp)
    } else{
        findVP(x[which(x$employee == emp),]$manager)
    }
}


sapply(emps, findVP)

预期输出(如果员工是副总裁，则应返回自己)：

emp  first_VP_manager
"xy" "zz"
"abc" "zz"
"zz" "zz"
"xx" "xx"
"yy" "ww"
"ww" "ww"

Answer 1

我不是igraph的专家，但是如果你想使用图形数据结构，你可以做一些类似的事情。

## Setup an edgelist
vps <- x[x$level=='vp', 'employee']
mat <- rbind(as.matrix(x[!(x$employee %in% vps),2:1]), cbind('vp', vps))

## Make a graph and look at it
library(igraph)
g <- graph_from_edgelist(mat)
plot(g, layout=layout.reingold.tilford(g, root="vp"))

​

​

## Leaves of graph (thought there would be a function for this?)
leaves <- V(g)[degree(g, mode='out')==0]

## Get the vps for each branch, print result
res <- lapply(all_simple_paths(g, from='vp', to=leaves), function(x) names(x)[-1])

setNames(res, sapply(res, `[`, 1))         
# $zz
# [1] "zz"  "abc" "xy" 
# 
# $ww
# [1] "ww" "yy"
# 
# $xx
# [1] "xx"