EVOLUTION-MANAGER
Edit File: girth.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: Girth of a graph</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="R.css" /> </head><body> <table width="100%" summary="page for girth {igraph}"><tr><td>girth {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Girth of a graph</h2> <h3>Description</h3> <p>The girth of a graph is the length of the shortest circle in it. </p> <h3>Usage</h3> <pre> girth(graph, circle = TRUE) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph. It may be directed, but the algorithm searches for undirected circles anyway.</p> </td></tr> <tr valign="top"><td><code>circle</code></td> <td> <p>Logical scalar, whether to return the shortest circle itself.</p> </td></tr> </table> <h3>Details</h3> <p>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. </p> <p>This implementation is based on Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph <em>Proceedings of the ninth annual ACM symposium on Theory of computing</em>, 1-10, 1977. The first implementation of this function was done by Keith Briggs, thanks Keith. </p> <h3>Value</h3> <p>A named list with two components: </p> <table summary="R valueblock"> <tr valign="top"><td><code>girth</code></td> <td> <p>Integer constant, the girth of the graph, or 0 if the graph is acyclic.</p> </td></tr> <tr valign="top"><td><code>circle</code></td> <td> <p>Numeric vector with the vertex ids in the shortest circle.</p> </td></tr> </table> <h3>Author(s)</h3> <p>Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> </p> <h3>References</h3> <p>Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph <em>Proceedings of the ninth annual ACM symposium on Theory of computing</em>, 1-10, 1977 </p> <h3>Examples</h3> <pre> # No circle in a tree g <- make_tree(1000, 3) girth(g) # The worst case running time is for a ring g <- make_ring(100) girth(g) # What about a random graph? g <- sample_gnp(1000, 1/1000) girth(g) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>