это репост, поскольку я не представил адекватного объяснения проблемы в первый раз.Сердечное спасибо участнику nsinghs за его помощь в первом раунде!
Проблема ...
Учитывая следующую сеть узлов и ребер, я хотел быполучить все возможные группировки узлов, где все узлы в группе связаны со всеми остальными узлами в этой группе через ребро.Таким образом, в сети ниже узлы «B», «C» и «F» будут находиться в группе, поскольку они полностью взаимосвязаны, а «A» будет принадлежать только группе с самим собой.«D» и «B» будут находиться в группе вместе, но «D» не будет принадлежать группе с «B», «C» и «F», потому что они не связаны напрямую с «C» и «F»через край.Другими словами, правила следующие:
Все члены группы должны быть подключены ко всем остальным членам этой группы напрямую через ребро.
Объект может быть членом нескольких групп.
Нет резервных групп.Если группа может вписаться в большую группу, это не группа.(Например, «B» и «C» сами по себе не являются действительной группой, поскольку они оба вписываются в большую группу «B», «C» и «F»).Объект может быть только в единственной группе (например, AA), если он не принадлежит ни к каким другим группам.
Iпредставили сеть выше в следующем кадре данных (df) ...
x1 <- c("A", "B", "B", "B", "B", "C", "C", "C", "D", "D", "D", "E", "E", "F", "F", "F")
x2 <- c("A", "B", "C", "D", "F", "B", "C", "F", "B", "D", "E", "D", "E", "B", "C", "F")
df <- data.frame(x1, x2)
... где строки с x1 и x2 представляют пары узлов, связанных ребром.Учитывая это df, я хотел бы получить следующие допустимые группы (представленные в визуальной, а также в форме фрейма данных) ...
1 2 3 4
1 A B B D
2 NULL C D E
3 NULL F NULL NULL
** Примечание: порядок имен групп / групп не имеет значения.
То, что я пробовал ...
Я попытался пройти по списку каждого уникального имени узла в столбце x1 df, чтобы определить все узлы, которые каждый узелсвязан с.Затем я использую эту информацию для составления групповых списков.Тем не менее, эти списки групп иногда аннулируются нарушением правила 1. Вот что я имею до сих пор ...
n <- nrow(as.data.frame(unique(df$x1)))
RosterGuide <- as.data.frame(matrix(nrow = n , ncol = 1))
RosterGuide$V1 <- seq.int(nrow(RosterGuide))
RosterGuide$Object <- (unique(df$x1))
colnames(RosterGuide) <- c("V1","Object")
groups_frame <- matrix(, ncol= length(n), nrow = length(n))
for (loopItem in 1:nrow(RosterGuide)) {
object <- subset(RosterGuide$Object, RosterGuide$V1 == loopItem)
group <- as.data.frame(subset(df$x2, df$x1 == object))
groups_frame <- cbind.fill(group, groups_frame, fill = "NULL")
}
Groups <- as.data.frame(groups_frame)
Groups <- subset(Groups, select = - c(object))
colnames(Groups) <- RosterGuide$V1
... этот цикл возвращает фрейм данных 'Группы' ...
1 2 3 4 5 6
1 B D B B B A
2 C E D C C NULL
3 F NULL E F D NULL
4 NULL NULL NULL NULL F NULL
Вот где я.Вы можете видеть, что группа 3 нарушает первое правило, потому что 'B' и 'E' не связаны напрямую с ребром, группа 5 нарушает первое правило, потому что 'F' и 'D' и 'F' и 'C' не являютсянапрямую связана через ребро, и группа 4 нарушает третье правило, потому что это дублирование группы 1 (я меньше беспокоюсь о нарушениях третьего правила, я могу легко решить это).
Я затрудняюсь, пытаясь перейти от фрейма данных «Группы» к действительному выводу, который я предложил выше, таким образом, что он универсален для любого фрейма данных, такого как df (2 столбца, бесконечные строки), который описываетузлы и ребра сети любого размера.
Я понимаю, что это был длинный пост, и я ценю любой вклад, который вы можете иметь.Я также приветствую любую критику того, что я сделал, поскольку я уверен, что это изобилует плохой практикой кодирования.Я довольно новичок в программировании, но мне не терпится научиться, поэтому я не чувствую необходимости тянуть удары.
Спасибо!
Бен