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

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