在R中无向图中的循环

Question

在R中无向图中的循环

3

我有一个无向图，想要检测其中三个或更多节点的环。在R中是否有相应的库可用？如果没有，是否有简单的算法可以实现此功能。

test <- data.frame(start=c(1,2,3,4), stop=c(2,3,1,5))

我希望您返回1、2、3和任何其他发现的周期。

格式要求：

我希望您返回1、2、3和任何其他发现的周期。

- yoda230

1

必须使用 R 吗？我在我的回答中添加了一个 Python 解决方案。 - David Marx

我更喜欢使用R，因为我习惯了它，但之前也用过Python做过一些东西，所以我很乐意尝试。谢谢。 - yoda230

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Marx · Accepted Answer

好的，这并不会给你在你的循环中实际的节点，但它将计算你图中每个等级的循环次数，所以这是一个开始。

library(igraph)
test <- data.frame(start=c(1,2,3,4), stop=c(2,3,1,5))
g <- graph.data.frame(test)

cycles <- t(sapply(3:dim(test)[1], function(x) {v=graph.motifs.no(g, size=x); c(x,v)}))
colnames(cycles) <- c("size","count")

     size count
[1,]    3     1
[2,]    4     0

我建议你尝试使用igraph库：虽然我没有在里面为你找到解决方案，但我认为那里可能会有你的答案。 graph.motifs看起来很有前途，但我无法解释结果。

如果不一定要用R，则Python中的networkx库有一个simple_cycles()函数，应该可以满足您的需求。

import networkx as nx
from networkx.algorithms.cycles import simple_cycles
g = nx.DiGraph()
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(3,1)
g.add_edge(4,1)
simple_cycles(g)

# [[1,2,3,1],[1,2,3,4,1]]