EVOLUTION-MANAGER
Edit File: automorphisms.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: Number of automorphisms</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 automorphisms {igraph}"><tr><td>automorphisms {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Number of automorphisms</h2> <h3>Description</h3> <p>Calculate the number of automorphisms of a graph, i.e. the number of isomorphisms to itself. </p> <h3>Usage</h3> <pre> automorphisms(graph, colors, sh = c("fm", "f", "fs", "fl", "flm", "fsm")) </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> </table> <h3>Details</h3> <p>An automorphism of a graph is a permutation of its vertices which brings the graph into itself. </p> <p>This function calculates the number of 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>. If you need the automorphisms themselves, use <code><a href="automorphism_group.html">automorphism_group</a></code> to obtain a compact representation of the automorphism group. </p> <h3>Value</h3> <p>A named list with the following members: </p> <table summary="R valueblock"> <tr valign="top"><td><code>group_size</code></td> <td> <p>The size of the automorphism group of the input graph, as a string. This number is exact if igraph was compiled with the GMP library, and approximate otherwise.</p> </td></tr> <tr valign="top"><td><code>nof_nodes</code></td> <td> <p>The number of nodes in the search tree.</p> </td></tr> <tr valign="top"><td><code>nof_leaf_nodes</code></td> <td> <p>The number of leaf nodes in the search tree.</p> </td></tr> <tr valign="top"><td><code>nof_bad_nodes</code></td> <td> <p>Number of bad nodes.</p> </td></tr> <tr valign="top"><td><code>nof_canupdates</code></td> <td> <p>Number of canrep updates.</p> </td></tr> <tr valign="top"><td><code>max_level</code></td> <td> <p>Maximum level.</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 and Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> for the igraph glue code and 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>, and <code><a href="automorphism_group.html">automorphism_group</a></code> for a compact representation of all automorphisms </p> <h3>Examples</h3> <pre> ## A ring has n*2 automorphisms, you can "turn" it by 0-9 vertices ## and each of these graphs can be "flipped" g <- make_ring(10) automorphisms(g) ## A full graph has n! automorphisms; however, we restrict the vertex ## matching by colors, leading to only 4 automorphisms g <- make_full_graph(4) automorphisms(g, colors=c(1,2,1,2)) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>