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

## Usage

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

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 b4e8e7a:
#>

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

``````