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

## 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 zero 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_dag()`

,
`is_matching()`

,
`knn()`

,
`laplacian_matrix()`

,
`reciprocity()`

,
`subcomponent()`

,
`subgraph()`

,
`topo_sort()`

,
`transitivity()`

,
`unfold_tree()`

,
`which_multiple()`

,
`which_mutual()`

Graph cycles
`feedback_arc_set()`

,
`has_eulerian_path()`

,
`is_dag()`

## Author

Gabor Csardi csardi.gabor@gmail.com

## Examples

```
# No circle in a tree
g <- make_tree(1000, 3)
girth(g)
#> $girth
#> [1] 0
#>
#> $circle
#> + 0/1000 vertices, from e1f90e7:
#>
# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
#> $girth
#> [1] 100
#>
#> $circle
#> + 100/100 vertices, from 58dbc47:
#> [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] 0
#>
#> $circle
#> + 0/1000 vertices, from 3390b9c:
#>
```