Итеративное соединение набора данных с результирующим набором данных

Question

Я пытаюсь найти круговой путь в кадре данных с 2 столбцами

Например:

Col1 Col2 
A    B 
C    A 
B    D 
D    C

Таблица

Итак, A-B-D-C-A является круговым маршрутом

df <- sqldf("Select * from circuit as 'A' INNER JOIN circuit as 'B' ON A.'To'= B.'FROM'")
result <- df[df$`FROM`==df$`TO..4`,]

Это дает мне все двунаправленные маршруты, есть ли способ, которым я могу выполнить соединение итеративно и найти все возможные круговые маршруты?

Answer 1

В дополнение к моему комментарию выше, я думаю, что хорошей отправной точкой для решения вашего вопроса будет перевод вашей структуры в график.

df <- read.table(text =
    "Col1 Col2
    A B
    C A
    B D
    D C", header = T)

library(igraph)
ig <- graph_from_data_frame(df)

Мы можем построить график

plot(ig)

Мне не совсем ясно, каким должен быть ожидаемый результат, и, как указано, ваши выборочные данные кажутся слишком упрощенными, чтобы вывести более общее решение. Сказав это и в данном конкретном случае, вы можете извлечь все циклы графа, которые соответствуют всем круговым путям вашей структуры, начиная с любой точки / вершины (адаптировано из r igraph найти все циклы )

cycles <- list()
for (v1 in V(ig)) {
    for (v2 in neighbors(ig, v1)) {
        cycles[length(cycles) + 1] = lapply(
                all_simple_paths(ig, v2, v1),
                function(p) c(v1, p))
    }
}
cycles
#[[1]]
#  B D C A
#1 3 4 2 1
#
#[[2]]
#  A B D C
#2 1 3 4 2
#
#[[3]]
#  D C A B
#3 4 2 1 3
#
#[[4]]
#  C A B D
#4 2 1 3 4

Ваш примерный график содержит четыре цикла; например, первый цикл в list равен B -> D -> C -> A -> B, второй цикл - A -> B -> D -> C -> A и т. д.

Если у вас есть несколько отключенных циклических подграфов, я сначала разбил бы ваш график на эти компоненты (например, используя decompose.graph), а затем идентифицировал бы циклы для компонента.