将数据集与结果数据集迭代连接

Question

我正在尝试查找循环路径，在一个有2列的数据帧中

例如：

Col1 Col2 
A    B 
C    A 
B    D 
D    C

Table

因此，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 find all cycles)

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)，然后识别每个组件的循环。