r - R中无向图中的循环

Question

我有一个无向图，我想做的是检测其中包含三个或更多节点的循环。R中是否有一个库可以做到这一点？如果没有，我可以实现一个简单的算法。

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

我希望它以 1、2、3 和它找到的任何其他周期返回。

Answer 1

好吧，这不会为您提供周期中的实际节点，但它会计算图表中每个等级的周期，所以这是一个开始。

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看起来很有希望，但我无法解释结果。

如果不需要，python 中R的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]]