rigraph 查找所有循环
r igraph find all cycles
我已经指导 igraph 并想要获取所有循环。周长功能有效,但仅 returns 最小周期。 R中有没有办法获取长度大于3的图中的所有循环(没有顶点指向自身和循环)
它不是直接在igraph中的函数,但是你当然可以把它编码出来。要找到一个循环,您从某个节点开始,转到某个相邻节点,然后找到一条返回原始节点的简单路径。由于您没有提供任何样本数据,我将用一个简单的例子来说明。
示例数据
## Sample graph
library(igraph)
set.seed(1234)
g = erdos.renyi.game(7, 0.29, directed=TRUE)
plot(g, edge.arrow.size=0.5)
寻找周期
让我从一个节点和一个邻居开始。节点 2 连接到节点 4。所以一些循环可能看起来像 2 -> 4 ->(节点不是 2 或 4) -> 2。让我们得到所有这样的路径。
v1 = 2
v2 = 4
lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
[[1]]
[1] 2 4 2
[[2]]
[1] 2 4 3 5 7 6 2
[[3]]
[1] 2 4 7 6 2
我们看到有 3 个循环,从 2 开始,以 4 为第二个节点。 (我知道你说的长度大于 3。我会回来的。)
现在我们只需要对每个节点 v1 和 v1 的每个邻居 v2 执行此操作。
Cycles = NULL
for(v1 in V(g)) {
for(v2 in neighbors(g, v1, mode="out")) {
Cycles = c(Cycles,
lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p)))
}
}
这在整个图中给出了 17 个循环。不过,您可能需要考虑两个问题,具体取决于您希望如何使用它。首先,你说你想要长度大于 3 的循环,所以我假设你不想要看起来像 2 -> 4 -> 2 的循环。这些很容易摆脱。
LongCycles = Cycles[which(sapply(Cycles, length) > 3)]
LongCycles 有 13 个循环,消除了 4 个短循环
2 -> 4 -> 2
4 -> 2 -> 4
6 -> 7 -> 6
7 -> 6 -> 7
但该列表指出了另一个问题。仍然有一些您可能认为是重复的循环。例如:
2 -> 7 -> 6 -> 2
7 -> 6 -> 2 -> 7
6 -> 2 -> 7 -> 6
您可能想要清除这些。要只获得每个循环的一个副本,您始终可以选择以最小顶点编号开始的顶点序列。因此,
LongCycles[sapply(LongCycles, min) == sapply(LongCycles, `[`, 1)]
[[1]]
[1] 2 4 3 5 7 6 2
[[2]]
[1] 2 4 7 6 2
[[3]]
[1] 2 7 6 2
这给出了不同的周期。
关于效率和可扩展性的补充
我提供了一个更高效的代码版本
原来提供。然而,它主要是为了
争辩说,除了非常简单的图表,你将无法
产生 所有周期 。
这是一些更高效的代码。它消除了检查许多
无法产生循环或将被淘汰的情况
作为一个冗余循环。为了方便 运行 测试
我想要的,我把它变成了一个函数。
## More efficient version
FindCycles = function(g) {
Cycles = NULL
for(v1 in V(g)) {
if(degree(g, v1, mode="in") == 0) { next }
GoodNeighbors = neighbors(g, v1, mode="out")
GoodNeighbors = GoodNeighbors[GoodNeighbors > v1]
for(v2 in GoodNeighbors) {
TempCyc = lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
TempCyc = TempCyc[which(sapply(TempCyc, length) > 3)]
TempCyc = TempCyc[sapply(TempCyc, min) == sapply(TempCyc, `[`, 1)]
Cycles = c(Cycles, TempCyc)
}
}
Cycles
}
但是,除了非常简单的图形,还有一个组合
可能路径的爆炸,因此找到所有可能的循环是
完全不切实际,我将用更小的图表来说明这一点
比你在评论中提到的那个。
首先,我将从一些小图开始,其中的边数
大约是顶点数的两倍。生成我的代码
下面是示例,但我想关注周期数,所以我
将从结果开始。
## ecount ~ 2 * vcount
Nodes Edges Cycles
10 21 15
20 41 18
30 65 34
40 87 424
50 108 3433
55 117 22956
但是你报告说你的数据有大约 5 倍
许多边作为顶点。让我们看一些这样的例子。
## ecount ~ 5 * vcount
Nodes Edges Cycles
10 48 3511
12 61 10513
14 71 145745
以此作为循环数的增长,使用10K节点
具有 50K 边似乎是不可能的。顺便说一句,花了几个
分钟计算具有 14 个顶点和 71 条边的示例。
为了可重复性,以下是我生成上述数据的方式。
set.seed(1234)
g10 = erdos.renyi.game(10, 0.2, directed=TRUE)
ecount(g10)
length(FindCycles(g10))
set.seed(1234)
g20 = erdos.renyi.game(20, 0.095 , directed=TRUE)
ecount(g20)
length(FindCycles(g20))
set.seed(1234)
g30 = erdos.renyi.game(30, 0.056 , directed=TRUE)
ecount(g30)
length(FindCycles(g30))
set.seed(1234)
g40 = erdos.renyi.game(40, 0.042 , directed=TRUE)
ecount(g40)
length(FindCycles(g40))
set.seed(1234)
g50 = erdos.renyi.game(50, 0.038 , directed=TRUE)
ecount(g50)
length(FindCycles(g50))
set.seed(1234)
g55 = erdos.renyi.game(55, 0.035 , directed=TRUE)
ecount(g55)
length(FindCycles(g55))
##########
set.seed(1234)
h10 = erdos.renyi.game(10, 0.55, directed=TRUE)
ecount(h10)
length(FindCycles(h10))
set.seed(1234)
h12 = erdos.renyi.game(12, 0.46, directed=TRUE)
ecount(h12)
length(FindCycles(h12))
set.seed(1234)
h14 = erdos.renyi.game(14, 0.39, directed=TRUE)
ecount(h14)
length(FindCycles(h14))
我已经指导 igraph 并想要获取所有循环。周长功能有效,但仅 returns 最小周期。 R中有没有办法获取长度大于3的图中的所有循环(没有顶点指向自身和循环)
它不是直接在igraph中的函数,但是你当然可以把它编码出来。要找到一个循环,您从某个节点开始,转到某个相邻节点,然后找到一条返回原始节点的简单路径。由于您没有提供任何样本数据,我将用一个简单的例子来说明。
示例数据
## Sample graph
library(igraph)
set.seed(1234)
g = erdos.renyi.game(7, 0.29, directed=TRUE)
plot(g, edge.arrow.size=0.5)
寻找周期
让我从一个节点和一个邻居开始。节点 2 连接到节点 4。所以一些循环可能看起来像 2 -> 4 ->(节点不是 2 或 4) -> 2。让我们得到所有这样的路径。
v1 = 2
v2 = 4
lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
[[1]]
[1] 2 4 2
[[2]]
[1] 2 4 3 5 7 6 2
[[3]]
[1] 2 4 7 6 2
我们看到有 3 个循环,从 2 开始,以 4 为第二个节点。 (我知道你说的长度大于 3。我会回来的。)
现在我们只需要对每个节点 v1 和 v1 的每个邻居 v2 执行此操作。
Cycles = NULL
for(v1 in V(g)) {
for(v2 in neighbors(g, v1, mode="out")) {
Cycles = c(Cycles,
lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p)))
}
}
这在整个图中给出了 17 个循环。不过,您可能需要考虑两个问题,具体取决于您希望如何使用它。首先,你说你想要长度大于 3 的循环,所以我假设你不想要看起来像 2 -> 4 -> 2 的循环。这些很容易摆脱。
LongCycles = Cycles[which(sapply(Cycles, length) > 3)]
LongCycles 有 13 个循环,消除了 4 个短循环
2 -> 4 -> 2
4 -> 2 -> 4
6 -> 7 -> 6
7 -> 6 -> 7
但该列表指出了另一个问题。仍然有一些您可能认为是重复的循环。例如:
2 -> 7 -> 6 -> 2
7 -> 6 -> 2 -> 7
6 -> 2 -> 7 -> 6
您可能想要清除这些。要只获得每个循环的一个副本,您始终可以选择以最小顶点编号开始的顶点序列。因此,
LongCycles[sapply(LongCycles, min) == sapply(LongCycles, `[`, 1)]
[[1]]
[1] 2 4 3 5 7 6 2
[[2]]
[1] 2 4 7 6 2
[[3]]
[1] 2 7 6 2
这给出了不同的周期。
关于效率和可扩展性的补充
我提供了一个更高效的代码版本 原来提供。然而,它主要是为了 争辩说,除了非常简单的图表,你将无法 产生 所有周期 。
这是一些更高效的代码。它消除了检查许多 无法产生循环或将被淘汰的情况 作为一个冗余循环。为了方便 运行 测试 我想要的,我把它变成了一个函数。
## More efficient version
FindCycles = function(g) {
Cycles = NULL
for(v1 in V(g)) {
if(degree(g, v1, mode="in") == 0) { next }
GoodNeighbors = neighbors(g, v1, mode="out")
GoodNeighbors = GoodNeighbors[GoodNeighbors > v1]
for(v2 in GoodNeighbors) {
TempCyc = lapply(all_simple_paths(g, v2,v1, mode="out"), function(p) c(v1,p))
TempCyc = TempCyc[which(sapply(TempCyc, length) > 3)]
TempCyc = TempCyc[sapply(TempCyc, min) == sapply(TempCyc, `[`, 1)]
Cycles = c(Cycles, TempCyc)
}
}
Cycles
}
但是,除了非常简单的图形,还有一个组合 可能路径的爆炸,因此找到所有可能的循环是 完全不切实际,我将用更小的图表来说明这一点 比你在评论中提到的那个。
首先,我将从一些小图开始,其中的边数 大约是顶点数的两倍。生成我的代码 下面是示例,但我想关注周期数,所以我 将从结果开始。
## ecount ~ 2 * vcount
Nodes Edges Cycles
10 21 15
20 41 18
30 65 34
40 87 424
50 108 3433
55 117 22956
但是你报告说你的数据有大约 5 倍 许多边作为顶点。让我们看一些这样的例子。
## ecount ~ 5 * vcount
Nodes Edges Cycles
10 48 3511
12 61 10513
14 71 145745
以此作为循环数的增长,使用10K节点 具有 50K 边似乎是不可能的。顺便说一句,花了几个 分钟计算具有 14 个顶点和 71 条边的示例。
为了可重复性,以下是我生成上述数据的方式。
set.seed(1234)
g10 = erdos.renyi.game(10, 0.2, directed=TRUE)
ecount(g10)
length(FindCycles(g10))
set.seed(1234)
g20 = erdos.renyi.game(20, 0.095 , directed=TRUE)
ecount(g20)
length(FindCycles(g20))
set.seed(1234)
g30 = erdos.renyi.game(30, 0.056 , directed=TRUE)
ecount(g30)
length(FindCycles(g30))
set.seed(1234)
g40 = erdos.renyi.game(40, 0.042 , directed=TRUE)
ecount(g40)
length(FindCycles(g40))
set.seed(1234)
g50 = erdos.renyi.game(50, 0.038 , directed=TRUE)
ecount(g50)
length(FindCycles(g50))
set.seed(1234)
g55 = erdos.renyi.game(55, 0.035 , directed=TRUE)
ecount(g55)
length(FindCycles(g55))
##########
set.seed(1234)
h10 = erdos.renyi.game(10, 0.55, directed=TRUE)
ecount(h10)
length(FindCycles(h10))
set.seed(1234)
h12 = erdos.renyi.game(12, 0.46, directed=TRUE)
ecount(h12)
length(FindCycles(h12))
set.seed(1234)
h14 = erdos.renyi.game(14, 0.39, directed=TRUE)
ecount(h14)
length(FindCycles(h14))