girth

0th

Percentile

Girth of a graph

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

Keywords
graphs
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.
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 (ie. 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.

Value

  • A named list with two components:
  • girthInteger constant, the girth of the graph, or 0 if the graph is acyclic.
  • circleNumeric vector with the vertex ids in the shortest circle.

concept

Girth

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

Aliases
  • girth
Examples
# No circle in a tree
g <- graph.tree(1000, 3)
girth(g)

# The worst case running time is for a ring
g <- graph.ring(100)
girth(g)

# What about a random graph?
g <- erdos.renyi.game(1000, 1/1000)
girth(g)
Documentation reproduced from package igraph, version 0.5.5-3, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.