查找图中的所有简单环。

此函数列出图中所有指定环长度范围内的简单环。 如果一个环没有重复的顶点，则称之为简单环。

多重边和自环会被考虑在内。请注意，典型的图具有指数级的环，并且多重边的存在会加剧这种组合爆炸。

用法

simple_cycles(
  graph,
  mode = c("out", "in", "all", "total"),
  min = NULL,
  max = NULL
)

参数

graph

输入图。

mode

字符常量，指定如何处理有向图。 out 遵循边的方向， in 遵循边的反方向，all 忽略边的方向。 在无向图中会被忽略。

min

要考虑的环长度的下限。 NULL 表示没有限制。

max

要考虑的环长度的上限。 NULL 表示没有限制。

值

一个具名列表，包含两个条目

vertices

以顶点形式表示的环的列表。

edges

以边形式表示的环的列表。

参见

图环 feedback_arc_set(), feedback_vertex_set(), find_cycle(), girth(), has_eulerian_path(), is_acyclic(), is_dag()

C 库中的相关文档

simple_cycles().

示例

g <- graph_from_literal(A -+ B -+ C -+ A -+ D -+ E +- F -+ A, E -+ E, A -+ F, simplify = FALSE)
simple_cycles(g)
#> $vertices
#> $vertices[[1]]
#> + 3/6 vertices, named, from 51c1db1:
#> [1] A B C
#> 
#> $vertices[[2]]
#> + 2/6 vertices, named, from 51c1db1:
#> [1] A F
#> 
#> $vertices[[3]]
#> + 1/6 vertex, named, from 51c1db1:
#> [1] E
#> 
#> 
#> $edges
#> $edges[[1]]
#> + 3/9 edges from 51c1db1 (vertex names):
#> [1] A->B B->C C->A
#> 
#> $edges[[2]]
#> + 2/9 edges from 51c1db1 (vertex names):
#> [1] A->F F->A
#> 
#> $edges[[3]]
#> + 1/9 edge from 51c1db1 (vertex names):
#> [1] E->E
#> 
#> 
simple_cycles(g, mode = "all") # ignore edge directions
#> $vertices
#> $vertices[[1]]
#> + 3/6 vertices, named, from 51c1db1:
#> [1] A B C
#> 
#> $vertices[[2]]
#> + 4/6 vertices, named, from 51c1db1:
#> [1] A D E F
#> 
#> $vertices[[3]]
#> + 4/6 vertices, named, from 51c1db1:
#> [1] A D E F
#> 
#> $vertices[[4]]
#> + 2/6 vertices, named, from 51c1db1:
#> [1] A F
#> 
#> $vertices[[5]]
#> + 1/6 vertex, named, from 51c1db1:
#> [1] E
#> 
#> 
#> $edges
#> $edges[[1]]
#> + 3/9 edges from 51c1db1 (vertex names):
#> [1] A->B B->C C->A
#> 
#> $edges[[2]]
#> + 4/9 edges from 51c1db1 (vertex names):
#> [1] A->D D->E F->E F->A
#> 
#> $edges[[3]]
#> + 4/9 edges from 51c1db1 (vertex names):
#> [1] A->D D->E F->E A->F
#> 
#> $edges[[4]]
#> + 2/9 edges from 51c1db1 (vertex names):
#> [1] F->A A->F
#> 
#> $edges[[5]]
#> + 1/9 edge from 51c1db1 (vertex names):
#> [1] E->E
#> 
#> 
simple_cycles(g, mode = "all", min = 2, max = 3) # limit cycle lengths
#> $vertices
#> $vertices[[1]]
#> + 3/6 vertices, named, from 51c1db1:
#> [1] A B C
#> 
#> $vertices[[2]]
#> + 2/6 vertices, named, from 51c1db1:
#> [1] A F
#> 
#> 
#> $edges
#> $edges[[1]]
#> + 3/9 edges from 51c1db1 (vertex names):
#> [1] A->B B->C C->A
#> 
#> $edges[[2]]
#> + 2/9 edges from 51c1db1 (vertex names):
#> [1] F->A A->F
#> 
#>