The girth of a graph is the length of the shortest circle in it.
girth(graph, circle = TRUE)A named list with two components:
Integer constant, the girth of the graph, or Inf if the graph is acyclic.
Numeric vector with the vertex ids in the shortest circle.
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.
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(),
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()
Graph cycles
feedback_arc_set(),
feedback_vertex_set(),
find_cycle(),
has_eulerian_path(),
is_acyclic(),
is_dag(),
simple_cycles()
# No circle in a tree
g <- make_tree(1000, 3)
girth(g)
#> $girth
#> [1] Inf
#>
#> $circle
#> + 0/1000 vertices, from b314221:
#>
# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
#> $girth
#> [1] 100
#>
#> $circle
#> + 100/100 vertices, from 17dae1d:
#> [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 73ea2f3:
#>