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 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()
,
laplacian_matrix()
,
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 2a012e3:
#>
# The worst case running time is for a ring
g <- make_ring(100)
girth(g)
#> $girth
#> [1] 100
#>
#> $circle
#> + 100/100 vertices, from 8f60609:
#> [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] 16
#>
#> $circle
#> + 16/1000 vertices, from 996c8b8:
#> [1] 621 656 162 333 482 437 472 845 142 114 338 717 698 147 401 270
#>