在层次结构中查找根节点 data.frame

Question

我有一个 data.frame 为我提供其行 (DF_in) 的分层信息：

   id parent_id
1   1        NA
2   2        NA
3   3         1
4   4         2
5   5         3
6   6         4
7   7         1
8   8         2
9   9         3
10 10         4

我想找到每一行的 root_id (DF_out):

   id parent_id root_id
1   1        NA      NA
2   2        NA      NA
3   3         1       1
4   4         2       2
5   5         3       1
6   6         4       2
7   7         1       1
8   8         2       2
9   9         3       1
10 10         4       2

通常我更喜欢使用 data.table，但这似乎需要一个递归解决方案，我不知道如何有效地解决这个问题。

DF_in <- data.frame(id = 1:10, parent_id = c(NA, NA, 1:4, 1:4))
# library(data.table)
# setDT(DF_in)

DF_out <- data.frame(id = 1:10, parent_id = c(NA, NA, 1:4, 1:4), root_id = c(NA, NA, rep(1:2, 4)))

Answer 1

快点：

find_root <- function(id, table) {
  par <- table[match(id, table$id), 'parent_id']
  if (is.na(par)) id else find_root(id = par, table)
}

DF_in$root_id <- vapply(DF_in$id, \(x) find_root(x, DF_in), integer(1L))


> DF_in
   id parent_id root_id
1   1        NA       1
2   2        NA       2
3   3         1       1
4   4         2       2
5   5         3       1
6   6         4       2
7   7         1       1
8   8         2       2
9   9         3       1
10 10         4       2

Answer 2

这是另一个使用 dplyr 的解决方案。当然如果需要多次运行这段代码也可以转成函数

library(dplyr)
#> 
#> Attache Paket: 'dplyr'
#> The following objects are masked from 'package:stats':
#> 
#>     filter, lag
#> The following objects are masked from 'package:base':
#> 
#>     intersect, setdiff, setequal, union

id <- c(1:10)

parent_id <- c(NA, NA, 1, 2, 3, 4, 1, 2, 3, 4)

df <- tibble(id = id, parent_id = parent_id)

df %>%
  mutate(
    root_id = pull(
      left_join(
        x = df,
        y = df,
        by = c("parent_id" = "id")),
      "parent_id.y"),
    root_id = ifelse(
      test = is.na(root_id) & !is.na(parent_id),
      yes = parent_id,
      no = root_id
    )
  )
#> # A tibble: 10 x 3
#>       id parent_id root_id
#>    <int>     <dbl>   <dbl>
#>  1     1        NA      NA
#>  2     2        NA      NA
#>  3     3         1       1
#>  4     4         2       2
#>  5     5         3       1
#>  6     6         4       2
#>  7     7         1       1
#>  8     8         2       2
#>  9     9         3       1
#> 10    10         4       2

^{由 reprex package (v2.0.1)}

于 2021-10-12 创建

在层次结构中查找根节点 data.frame

Find root nodes in a hierarchical data.frame

r

data.table