EVOLUTION-MANAGER
Edit File: automorphism_group.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: Generating set of the automorphism group 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 automorphism_group {igraph}"><tr><td>automorphism_group {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Generating set of the automorphism group of a graph</h2> <h3>Description</h3> <p>Compute the generating set of the automorphism group of a graph. </p> <h3>Usage</h3> <pre> automorphism_group( graph, colors, sh = c("fm", "f", "fs", "fl", "flm", "fsm"), details = FALSE ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph, it is treated as undirected.</p> </td></tr> <tr valign="top"><td><code>colors</code></td> <td> <p>The colors of the individual vertices of the graph; only vertices having the same color are allowed to match each other in an automorphism. When omitted, igraph uses the <code>color</code> attribute of the vertices, or, if there is no such vertex attribute, it simply assumes that all vertices have the same color. Pass NULL explicitly if the graph has a <code>color</code> vertex attribute but you do not want to use it.</p> </td></tr> <tr valign="top"><td><code>sh</code></td> <td> <p>The splitting heuristics for the BLISS algorithm. Possible values are: ‘<code>f</code>’: first non-singleton cell, ‘<code>fl</code>’: first largest non-singleton cell, ‘<code>fs</code>’: first smallest non-singleton cell, ‘<code>fm</code>’: first maximally non-trivially connected non-singleton cell, ‘<code>flm</code>’: first largest maximally non-trivially connected non-singleton cell, ‘<code>fsm</code>’: first smallest maximally non-trivially connected non-singleton cell.</p> </td></tr> <tr valign="top"><td><code>details</code></td> <td> <p>Specifies whether to provide additional details about the BLISS internals in the result.</p> </td></tr> </table> <h3>Details</h3> <p>An automorphism of a graph is a permutation of its vertices which brings the graph into itself. The automorphisms of a graph form a group and there exists a subset of this group (i.e. a set of permutations) such that every other permutation can be expressed as a combination of these permutations. These permutations are called the generating set of the automorphism group. </p> <p>This function calculates a possible generating set of the automorphism of a graph using the BLISS algorithm. See also the BLISS homepage at <a href="http://www.tcs.hut.fi/Software/bliss/index.html">http://www.tcs.hut.fi/Software/bliss/index.html</a>. The calculated generating set is not necessarily minimal, and it may depend on the splitting heuristics used by BLISS. </p> <h3>Value</h3> <p>When <code>details</code> is <code>FALSE</code>, a list of vertex permutations that form a generating set of the automorphism group of the input graph. When <code>details</code> is <code>TRUE</code>, a named list with two members: </p> <table summary="R valueblock"> <tr valign="top"><td><code>generators</code></td> <td> <p>Returns the generators themselves</p> </td></tr> <tr valign="top"><td><code>info</code></td> <td> <p>Additional information about the BLISS internals. See <code><a href="automorphisms.html">automorphisms</a></code> for more details.</p> </td></tr> </table> <h3>Author(s)</h3> <p>Tommi Junttila (<a href="http://users.ics.aalto.fi/tjunttil/">http://users.ics.aalto.fi/tjunttil/</a>) for BLISS, Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> for the igraph glue code and Tamas Nepusz <a href="mailto:ntamas@gmail.com">ntamas@gmail.com</a> for this manual page. </p> <h3>References</h3> <p>Tommi Junttila and Petteri Kaski: Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs, <em>Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics.</em> 2007. </p> <h3>See Also</h3> <p><code><a href="canonical_permutation.html">canonical_permutation</a></code>, <code><a href="permute.html">permute</a></code>, <code><a href="automorphisms.html">automorphisms</a></code> </p> <h3>Examples</h3> <pre> ## A ring has n*2 automorphisms, and a possible generating set is one that ## "turns" the ring by one vertex to the left or right g <- make_ring(10) automorphism_group(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>