r - R の無向グラフのサイクル

Question

無向グラフがあり、3 つ以上のノードを持つサイクルを検出したいと考えています。これを行う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有望に見えますが、結果を解釈できませんでした。

である必要がない場合、pythonRのライブラリには、必要に応じて十分なsimple_cycles()関数があります。networkx

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]]