图的围长 — girth • igraph 网络分析库

图的围长是图中最短环的长度。

用法

girth(graph, circle = TRUE)

参数

graph: 输入图。它可以是有向图，但算法无论如何都会搜索无向环。
circle: 逻辑标量，是否返回最短环本身。

值

一个包含两个组件的命名列表

girth: 整数常量，图的围长，如果图是无环的，则为Inf。
circle: 最短环中的顶点 ID 的数值向量。

详细信息

当前的实现仅适用于无向图，有向图被视为无向图。忽略环边和多重边。如果图是森林（即无环），则返回Inf。

此实现基于 Alon Itai 和 Michael Rodeh：Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing, 1-10, 1977。此函数的第一个实现由 Keith Briggs 完成，感谢 Keith。

参考文献

Alon Itai 和 Michael Rodeh：Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing, 1-10, 1977

参见

其他 structural.properties：bfs()、component_distribution()、connect()、constraint()、coreness()、degree()、dfs()、distance_table()、edge_density()、feedback_arc_set()、feedback_vertex_set()、is_acyclic()、is_dag()、is_matching()、k_shortest_paths()、knn()、reciprocity()、subcomponent()、subgraph()、topo_sort()、transitivity()、unfold_tree()、which_multiple()、which_mutual()

图环 feedback_arc_set()、feedback_vertex_set()、find_cycle()、has_eulerian_path()、is_acyclic()、is_dag()、simple_cycles()

作者

Gabor Csardi csardi.gabor@gmail.com

示例


# No circle in a tree
g <- make_tree(1000, 3)
girth(g)
#> $girth
#> [1] Inf
#> 
#> $circle
#> + 0/1000 vertices, from 3ccfc63:
#> 

# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
#> $girth
#> [1] 100
#> 
#> $circle
#> + 100/100 vertices, from c69c731:
#>   [1]  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68
#>  [19]  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86
#>  [37]  87  88  89  90  91  92  93  94  95  96  97  98  99 100   1   2   3   4
#>  [55]   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22
#>  [73]  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40
#>  [91]  41  42  43  44  45  46  47  48  49  50
#> 

# What about a random graph?
g <- sample_gnp(1000, 1 / 1000)
girth(g)
#> $girth
#> [1] Inf
#> 
#> $circle
#> + 0/1000 vertices, from e74590d:
#>