笔迹查找所有循环 [英] r igraph find all cycles

问题描述

我已指导igraph，并希望获取所有循环。周长函数有效，但仅返回最小周期。 R中有一种方法可以获取图中大于3的图形中的所有循环（没有顶点指向其自身和循环）

I have directed igraph and want to fetch all the cycles. girth function works but only returns the smallest cycle. Is there a way in R to fetch all the cycles in a graph of length greater then 3 (no vertex pointing to itself and loops)

推荐答案

它不是igraph中的直接函数，但是您当然可以对其进行编码。要查找循环，请从某个节点开始，转到某个相邻节点，然后找到返回原始节点的简单路径。由于您未提供任何示例数据，因此我将举一个简单的示例进行说明。

It is not directly a function in igraph, but of course you can code it up. To find a cycle, you start at some node, go to some neighboring node and then find a simple path back to the original node. Since you did not provide any sample data, I will illustrate with a simple example.

## 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。让我们获得所有类似的路径。

Let me start with just one node and one neighbor. Node 2 connects to Node 4. So some cycles may look like 2 -> 4 -> (Nodes other than 2 or 4) -> 2. Let's get all of the paths like that.

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

我们看到有三个周期从2开始，第二个节点为4。 （我知道您说的长度大于3。我会再说一遍。）

We see that there are three cycles starting at 2 with 4 as the second node. (I know that you said length greater than 3. I will come back to that.)

现在，我们只需要对每个节点v1和每个邻居v2进行此操作v1。

Now we just need to do that for every node v1 and every neighbor v2 of v1.

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的循环。这些很容易消除。

This gives 17 cycles in the whole graph. There are two issues though that you may need to look at depending on how you want to use this. First, you said that you wanted cycles of length greater than 3, so I assume that you do not want the cycles that look like 2 -> 4 -> 2. These are easy to get rid of.

LongCycles = Cycles[which(sapply(Cycles, length) > 3)]

LongCycles有13个周期消除了4个短周期

LongCycles has 13 cycles having eliminated the 4 short cycles

2 -> 4 -> 2
4 -> 2 -> 4
6 -> 7 -> 6
7 -> 6 -> 7

但是该列表指出了另一个问题。您可能还会循环一些重复的事情。例如：

But that list points out the other problem. There still are some that you cycles that you might think of as duplicates. For example:

2 -> 7 -> 6 -> 2
7 -> 6 -> 2 -> 7
6 -> 2 -> 7 -> 6

您可能想将它们除掉。要仅获得每个循环的一个副本，您始终可以选择以最小的顶点号开始的顶点序列。因此，

You might want to weed these out. To get just one copy of each cycle, you can always choose the vertex sequence that starts with the smallest vertex number. Thus,

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

这仅给出了不同的循环。

This gives just the distinct cycles.

---

我正在提供最初提供的
代码的高效版本。但是，主要是出于
的目的，除了非常简单的图形外，您将无法
生成所有循环。

I am providing a much more efficient version of the code that I originally provided. However, it is primarily for the purpose of arguing that, except for very simple graphs, you will not be able produce all cycles.

这是一些更有效的代码。它消除了检查许多
不能产生一个循环或将被淘汰的
作为冗余循环的情况。为了使运行所需的测试
变得容易，我将其变成一个函数。

Here is some more efficient code. It eliminates checking many cases that either cannot produce a cycle or will be eliminated as a redundant cycle. In order to make it easy to run the tests that I want, I made it into a function.

## 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
}

但是，除了非常简单的图形外，还有可能的路径组合的
爆炸，因此找到所有可能的周期是
完全不切实际的，我将用更小的$ b $来说明这一点b，而不是您在评论中提到的那个。

However, except for very simple graphs, there is a combinatorial explosion of possible paths and so finding all possible cycles is completely impractical I will illustrate this with graphs much smaller than the one that you mention in the comments.

首先，我将从一些小图开始，其中边
的数量大约是边数的两倍。顶点。生成我的
示例的代码如下，但我想关注循环数，所以我
将从结果开始。

First, I will start with some small graphs where the number of edges is approximately twice the number of vertices. Code to generate my examples is below but I want to focus on the number of cycles, so I will just start with the results.

## 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倍于顶点的边。让我们来看这样的例子。

But you report that your data has approximately 5 times as many edges as vertices. Let's look at some examples like that.

## ecount ~ 5 * vcount
Nodes  Edges    Cycles
10      48        3511
12      61       10513
14      71      145745

以此为使用10K节点
和50K边来增加周期数似乎是不可能的。顺便说一句，计算具有14个顶点和71条边的示例花了几分钟
分钟。

With this as the growth of the number of cycles, using 10K nodes with 50K edges seems to be out of the question. BTW, it took several minutes to compute the example with 14 vertices and 71 edges.

为实现可再现性，这是我生成上述数据的方式。

For reproducibility, here is how I generated the above data.

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

这篇关于笔迹查找所有循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！