r - 回溯一棵树的两列数据的父/路径

Question

我有一个如下序列化的树数据：关系：P 到 C 是“一对多”，C 到 P 是“一对一”。所以 P 列可能有重复值，但 C 列有唯一值。

P, C
1, 2
1, 3
3, 4
2, 5
4, 6
# in data.frame
df <- data.frame(P=c(1,1,3,2,4), C=c(2,3,4,5,6))

1.我如何有效地实现一个功能func，以便：

func(df, val)返回到根的完整路径向量（在本例中为 1）。

例如：

func(df, 3) returns c(1,2,3)
func(df, 5)  returns c(1,2,5)
func(df, 6) returns c(1,3,4,6)

2. 或者，快速转换df为这样的查找表也适用于我：

C, Paths
2, c(1,2)
3, c(1,3)
4, c(1,3,4)
5, c(1,2,5)
6, c(1,2,4,6)

标签： rigraph

Answer 1

这是使用的解决方案igraph

library(igraph)
g <- graph_from_data_frame(df)
df <- within(df,
             Path <- sapply(match(as.character(C),names(V(g))), 
                            function(k) toString(names(unlist(all_simple_paths(g,1,k))))))

这样

> df
  P C       Path
1 1 2       1, 2
2 1 3       1, 3
3 3 4    1, 3, 4
4 2 5    1, 2, 5
5 4 6 1, 3, 4, 6