Объедините строки, которые имеют общие элементы

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).

Применение этой логики c дает следующий желаемый результат.

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

У меня есть некоторый код, который достигает этого результата, но вложив mapply в while l oop вместе с некоторой действительно неуклюжей обработкой структур данных заставляет меня думать, что это далеко не оптимально.

# 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"