Girth of a graph

The girth of a graph is the length of the shortest circle in it.

girth(graph, circle = TRUE)

Arguments

graph

The input graph. It may be directed, but the algorithm searches for undirected circles anyway.

circle

Logical scalar, whether to return the shortest circle itself.

Value

A named list with two components:

girth

Integer constant, the girth of the graph, or 0 if the graph is acyclic.

circle

Numeric vector with the vertex ids in the shortest circle.

Details

The current implementation works for undirected graphs only, directed graphs are treated as undirected graphs. Loop edges and multiple edges are ignored. If the graph is a forest (i.e. acyclic), then Inf is returned.

This implementation is based on Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing, 1-10, 1977. The first implementation of this function was done by Keith Briggs, thanks Keith.

References

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

See also

Other structural.properties: bfs(), component_distribution(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

Graph cycles feedback_arc_set(), has_eulerian_path(), is_acyclic(), is_dag()

Author

Gabor Csardi csardi.gabor@gmail.com

Examples

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

# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
#> $girth
#> [1] 100
#> 
#> $circle
#> + 100/100 vertices, from 784a63a:
#>   [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] 12
#> 
#> $circle
#> + 12/1000 vertices, from 54fcb51:
#>  [1] 903 811 514 822 850 938 125 275 732 518 446 475
#>