草庐IT

r igraph 查找所有循环

codeneng 2023-03-28 原文

r igraph find all cycles

我已指导 igraph 并想获取所有周期。周长函数有效，但只返回最小的周期。 R中有没有办法在长度大于3的图中获取所有循环(没有指向自身和循环的顶点)

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

样本数据

1
2
3
4
5
## 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。让我们得到所有这样的路径。

1
2
3
4
5
6
7
8
9
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。我会回到那个。)

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

1
2
3
4
5
6
7
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 的循环。这些很容易摆脱。

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

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

1
2
3
4
2 -> 4 -> 2
4 -> 2 -> 4
6 -> 7 -> 6
7 -> 6 -> 7

但该列表指出了另一个问题。还有一些你可能认为是重复的循环。例如：

1
2
3
2 -> 7 -> 6 -> 2
7 -> 6 -> 2 -> 7
6 -> 2 -> 7 -> 6

您可能想清除这些。要获得每个循环的一个副本，您始终可以选择以最小顶点编号开始的顶点序列。因此，

1
2
3
4
5
6
7
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

这只是给出了不同的循环。

关于效率和可扩展性的补充

我提供了一个更高效的代码版本
最初提供。但是，它主要是为了
争辩说，除了非常简单的图表，你将无法
产生所有循环。

这里有一些更高效的代码。它消除了许多检查
不能产生循环或将被消除的情况
作为一个冗余循环。为了便于运行测试
我想要的，我把它变成了一个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
## 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
}

但是，除了非常简单的图形外，还有一个组合
可能路径的爆炸，因此找到所有可能的循环是
完全不切实际我将用小得多的图表来说明这一点
比你在评论中提到的那个。

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

1
2
3
4
5
6
7
8
## 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 倍
许多边作为顶点。让我们看一些这样的例子。

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

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

为了重现性，这是我生成上述数据的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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))

  • 此代码适用于小图，但随着图的邻居越来越多，代码会崩溃 R。有没有办法简化它
  • 当然，如果图表很大，检查所有路径将需要循环和内存。上面的代码确实有一些效率低下的地方。我会在答案中添加一点。但如果你连一步都做不了，那也无济于事。你能搜索一对节点吗？答案的一部分说： all_simple_paths(g, v2,v1, mode="out") ？需要一些时间来测试和编写更有效的方法来做到这一点。我将在今天晚些时候添加它。
  • 该代码能够帮助我，但性能使其无法使用。很高兴看到您对答案的更新
  • @Ankit所以我的目标是正确的大小，你的图有多少个顶点和边？
  • 我有 10,000 个向量和 50k 个边
  • 这比以前更好，但仍然放弃了 900 个节点的图形。我将其标记为答案，因为这接近我想要的。谢谢
  • 是的，我很抱歉，但我认为即使对于 100 个节点和 500 个边的图，这也行不通。将有太多的周期来计算它们。
  • iGraph 库有一个函数 girth 来确定最小的循环，它也适用于大图。如果此代码在库中并用 C 构建，性能会提高吗？
  • 它可能表现得更好一些，但我认为对于大型示例没有办法解决这个问题。除了我的答案之外，数字示例的要点是，周期数似乎增长得非常快。对于 1K 节点和 5K 边，我预计周期数会如此之大，以至于没有计算机能够掌握答案。
  • 这对我很有帮助，解释得很好，节奏也很好，非常感谢

igraph查找brsectionnbspcyclegirthr

有关r igraph 查找所有循环的更多相关文章

  1. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少，我以前从未做过这种事情。我的解析器表现得好像有一个无限循环，但没有堆栈跟踪；事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上，以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  4. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

  5. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  6. ruby - Nokogiri 剥离所有属性 - 2

    我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？ 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog

  7. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  8. ruby - 获取模块中定义的所有常量的值 - 2

    我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

  9. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  10. ruby - Ruby 中的闭包和 for 循环 - 2

    我是Ruby的新手，有些闭包逻辑让我感到困惑。考虑这段代码:array=[]foriin(1..5)array[5,5,5,5,5]这对我来说很有意义，因为i被绑定(bind)在循环之外，所以每次循环都会捕获相同的变量。使用每个block可以解决这个问题对我来说也很有意义:array=[](1..5).each{|i|array[1,2,3,4,5]...因为现在每次通过时都单独声明i。但现在我迷路了:为什么我不能通过引入一个中间变量来修复它？array=[]foriin1..5j=iarray[5,5,5,5,5]因为j每次循环都是新的，我认为每次循环都会捕获不同的变量。例如，这绝对

随机推荐