合并具有共同元素的行

Question

我有一个如下所示的 data.table：

# Load packages
library(data.table)

# Set RNG seed
set.seed(-1)

# Create dummy data
dt <- data.table(foo = sample(letters[1:10], 6),
                 bar = sample(letters[1:10], 6))

dt
#>    foo bar
#> 1:   g   a
#> 2:   h   j
#> 3:   j   e
#> 4:   a   i
#> 5:   d   g
#> 6:   i   c

我想将所有相关元素组合在一起。我的意思是，例如，a和g一起在第一行，所以它们属于一个组 ( a, g)。但是a和i一起在第 4 行，所以i也属于这个组 ( a, g, i)。此外，i与c第 6 行相关联，因此c也属于组 ( a, g, i, c)。在第 5 行，d并g在一起，因此d也属于该组 ( a, g, i, c, d)。

应用此逻辑可得到以下所需结果。

# Desired result
# [[1]]
# [1] a c d g i
# [[2]]
# [1] e h j

我有一些代码可以实现这个结果，但是将mapplya嵌套在while循环中以及对数据结构的一些非常笨拙的处理使我认为这远非最佳。

# Loop counter
i <- 1

# List of groups
res <- list()

while(nrow(dt)>0){
  # Add first row to list
  res[[i]] <- unlist(dt[1])

  # Check each row in dt
  mapply(function(x, y){

    # If there are common elements between current row and current group
    if(length(intersect(c(x, y), res[[i]])) > 0){
      # Add elements from this row to this group
      res[[i]] <<- c(res[[i]], x, y)
    }

  }, dt$foo, dt$bar)

  # Only keep unique elements
  res[[i]] <- unique(res[[i]])

  # Remove rows that have elements in the current group
  dt <- dt[!(foo %in% res[[i]] | bar %in% res[[i]])]

  # Increment loop counter
  i <- i + 1
}

给，

res
#> [[1]]
#> [1] "g" "a" "i" "d" "c"
#> 
#> [[2]]
#> [1] "h" "j" "e"

按要求。

有没有更优雅、更有效的方法来实现这个结果？

Answer 1

您的数据可以被视为具有不同连接性组件的图形。要分析此类数据，您可以使用该库igraph：

只需从边缘数据框创建一个图形：

library(data.table)
library(igraph)

set.seed(-1)

foo = sample(letters[1:10], 6)
bar = sample(letters[1:10], 6)

edges <- data.table(foo, bar)

net <- igraph::graph_from_data_frame(d = edges, directed = F)

然后，您可以找到图形的孤立组件：

components(net)

# $membership
# g h j a d i e c 
# 1 2 2 1 1 1 2 1 
#
# $csize
# [1] 5 3
#
# $no
# [1] 2

或者获取包含在每个组件中的更好的顶点列表：

split(names(V(net)), components(net)$membership)
# $`1`
# [1] "g" "a" "d" "i" "c"
# 
# $`2`
# [1] "h" "j" "e"