Группировка отношения многие ко многим из двухколоночной карты
У меня есть таблица SQL, которая отображает, скажем, авторов и книги. Я хотел бы сгруппировать связанных авторов и книги (книги, написанные одним и тем же автором, и авторов, которые совместно написали книгу) и выяснить, насколько велики эти группы. Например, если Ю.К. Роулинг написала в соавторстве с Джунот Диаз, а Джанот Диаз - в соавторстве с Зади Смитом, тогда я бы хотел, чтобы все три автора были в одной группе.
Вот набор игрушечных данных (Мэтью Доул) с некоторыми из отношений, о которых я говорю:
set.seed(1)
authors <- replicate(100,sample(1:3,1))
book_id <- rep(1:100,times=authors)
author_id <- c(lapply(authors,sample,x=1:100,replace=FALSE),recursive=TRUE)
aubk <- data.table(author_id = author_id,book_id = book_id)
aubk[order(book_id,author_id),]
Здесь видно, что авторы 27 и 36 совместно написали книгу 2, поэтому они должны быть в одной группе. То же самое для авторов 63 и 100 для 3; и D, F и L для 4. И так далее.
Я не могу придумать хороший способ сделать это, кроме цикла for, который (как вы можете догадаться) является медленным. Я попробовал немногоdata.table
чтобы избежать ненужного копирования. Есть ли лучший способ сделать это?
aubk$group <- integer(dim(aubk)[1])
library(data.table)
aubk <- data.table(aubk)
#system.time({
for (x in 1:dim(aubk)[1]) {
if(identical(x,1)) {
value <- 1L
} else {
sb <- aubk[1:(x-1),]
index <- match(aubk[x,author_id],sb[,author_id])
if (identical(index,NA_integer_)) {
index <- match(aubk[x,book_id],sb[,book_id])
if (identical(index,NA_integer_)) {
value <- x
} else {
value <- aubk[index,group]
}
} else {
value <- aubk[index,group]
}
}
aubk[x,group:=value]
}
#})
EDIT: Как упоминали @Josh O'Brien и @thelatemail, моя проблема также может быть сформулирована как поиск связанных компонентов графа из списка из двух столбцов, где каждое ребро - строка, а два столбца - это связанные узлы.