girth                 package:igraph                 R Documentation

_G_i_r_t_h _o_f _a _g_r_a_p_h

_D_e_s_c_r_i_p_t_i_o_n:

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

_U_s_a_g_e:

     girth(graph, circle=TRUE)

_A_r_g_u_m_e_n_t_s:

   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.

_D_e_t_a_i_l_s:

     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.

_V_a_l_u_e:

     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.

_A_u_t_h_o_r(_s):

     Gabor Csardi csardi@rmki.kfki.hu

_R_e_f_e_r_e_n_c_e_s:

     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

_E_x_a_m_p_l_e_s:

     # 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)

