перечислить все возможные подключенные узлы

Скажем, у меня 100 узлов, и я даю каждому уникальный идентификатор от 1: 100.

Если бы мне понадобился список всех комбинаций узлов, я полагаю, что он имел бы длину 2^100. Это если какой-либо узел может отсутствовать на схеме.

Но скажем, у меня есть фрейм данных, который представляет связи между узлами:

head(conn_)
  from  to
2    1   2
3    1   4
4    2   3
5    2   5
6    4   6
7  154 100
8  102 101

Итак, в строке один из этого df указано, что существует соединение от узла 11 к узлу 10

Скажем, я хочу перечислить каждую комбинацию допустимых узлов, но комбинация действительна только в том случае, если нет разорванного соединения между элементами набора. Как я мог это сделать?

Например, если у меня есть узлы 1->2->3->4->5->6->7->8->9, где -> представляет собой двустороннее соединение (1 подключается к 2, а 2 подключается к 1), тогда два действительных подмножества будут {1, 2, 3} & {4, 5, 6}, но недопустимым подмножеством будет {1, 3, 4, 6}. Это было бы недействительно, потому что между двумя элементами в наборе разорвано соединение.

Если один узел подключается к нескольким другим узлам, это считается допустимым соединением, то есть для указанного выше фрейма данных я могу иметь действительный набор {1, 2, 4, 6}

Мне очень сложно найти способ сделать это рекурсивно или с помощью циклов for / while.

Кроме того, если существует максимум пять двусторонних соединений на узел, в случае 100 узлов, то можно ли перечислить все? Как эта проблема разрастается?

редактировать:

Вот пример ввода / вывода:

conn_ =
  from  to
     1   2
     1   4
     2   3
     2   5
     4   6

Expected output : { {1}, {1, 2}, {1, 4}, {1, 2, 4}, {1, 2, 3}, {1, 2, 5}, {1, 4, 6}, {1, 2, 4, 6}, {1, 2, 3, 4}, {1, 2, 3, 4, 6}, {1, 2, 3, 4, 5, 6}, {2}, {2, 3}, {2, 5}, {2, 3, 5}, {3}, {4}, {4, 6} }

Обратите внимание, что {1, 3, 5} отсутствует в выходных данных, потому что не может существовать разрыв между элементами в наборе, но {1, 2, 4, 6} является допустимым, поскольку 1 подключается к 2, а 1 подключается к 4


r enumeration
person Frank    schedule 08.05.2020    source источник
comment
Похоже на проблему с графиком. Итак, сначала используйте пакет igraph, чтобы превратить ваш data.frame в график. Это кажется интересным, но без небольшого воспроизводимого примера (включая полный ожидаемый результат) я не работаю над этим.   -  person Roland    schedule 08.05.2020
comment
Спасибо, посмотрю igraph, лучше, чем DiagrammeR?   -  person Frank    schedule 08.05.2020
comment
Я не понимаю, почему {1, 2, 3, 4} не выводятся.   -  person Roland    schedule 08.05.2020
comment
Ах, пропустил несколько дел, извините!   -  person Frank    schedule 08.05.2020

Ответы (1)


arrow_upward
2
arrow_downward

Вот решение с igraph. Это быстро истощит ваши ресурсы для больших графиков с высокой связностью.

По сути, мы ищем все пути из каждой вершины. Это даст нам каждую комбинацию дважды, поэтому в конце мы разбиваем ее на уникальные комбинации. Кто-то, кто знает о графиках больше, чем я, может создать более эффективное решение.

DF <- read.table(text = "from  to
     1   2
     1   4
     2   3
     2   5
     4   6", header = TRUE)

library(igraph)

g <- graph_from_data_frame(DF, directed = FALSE)
plot(g)

график графика

#all paths starting from each vertex
paths <- unlist(lapply(V(g), function(from) all_simple_paths(g, from)), FALSE)

res <- lapply(paths, names) #extract vertex names from each path
res <- c(as.list(names(V(g))), res)  #add single vertices
res <- lapply(res, sort) #sort
res <- res[!duplicated(res)] #remove duplicates
#for compact printing:
unname(sapply(res, paste, collapse = ","))
#[1] "1"         "2"         "4"         "3"         "5"         "6"         "1,2"       "1,2,3"     "1,2,5"     "1,4"       "1,4,6"     "1,2,4"     "1,2,4,6"   "2,3"      
#[15] "2,5"       "1,2,3,4"   "1,2,4,5"   "4,6"       "1,2,3,4,6" "2,3,5"     "1,2,4,5,6"
person Roland    schedule 08.05.2020
comment
Отлично. Также отличный пакет. Есть ли в пакете способ ускорить его с помощью мемоизации? Если имеется максимум 5 соединений на узел, это дает для случая 100 узлов максимальное время: [100, 5, (5 +4 - 1), (5 + 4 + 4 - 2), (5 + 4 + 4 + 4 - 3) ... ] = [100, 5, 5 + 4n - n]. Итак, я думаю, что максимальное количество путей составляет: 100*(5+4n-n)!, где n - количество узлов. Это кажется правильным? - person Frank; 08.05.2020