EVOLUTION-MANAGER
Edit File: canonical_permutation.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: Canonical permutation 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 canonical_permutation {igraph}"><tr><td>canonical_permutation {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Canonical permutation of a graph</h2> <h3>Description</h3> <p>The canonical permutation brings every isomorphic graphs into the same (labeled) graph. </p> <h3>Usage</h3> <pre> canonical_permutation( 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, 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>Type of the heuristics to use for the BLISS algorithm. See details for possible values.</p> </td></tr> </table> <h3>Details</h3> <p><code>canonical_permutation</code> computes a permutation which brings the graph into canonical form, as defined by the BLISS algorithm. All isomorphic graphs have the same canonical form. </p> <p>See the paper below for the details about BLISS. This and more information is available at <a href="http://www.tcs.hut.fi/Software/bliss/index.html">http://www.tcs.hut.fi/Software/bliss/index.html</a>. </p> <p>The possible values for the <code>sh</code> argument are: </p> <dl> <dt>"f"</dt><dd><p>First non-singleton cell.</p> </dd> <dt>"fl"</dt><dd><p>First largest non-singleton cell.</p> </dd> <dt>"fs"</dt><dd><p>First smallest non-singleton cell.</p> </dd> <dt>"fm"</dt><dd><p>First maximally non-trivially connectec non-singleton cell.</p> </dd> <dt>"flm"</dt><dd><p>Largest maximally non-trivially connected non-singleton cell.</p> </dd> <dt>"fsm"</dt><dd><p>Smallest maximally non-trivially connected non-singleton cell.</p> </dd> </dl> <p> See the paper in references for details about these. </p> <h3>Value</h3> <p>A list with the following members: </p> <table summary="R valueblock"> <tr valign="top"><td><code>labeling</code></td> <td> <p>The canonical permutation which takes the input graph into canonical form. A numeric vector, the first element is the new label of vertex 0, the second element for vertex 1, etc. </p> </td></tr> <tr valign="top"><td><code>info</code></td> <td> <p>Some information about the BLISS computation. A named list with the following members: </p> <dl> <dt>"nof_nodes"</dt><dd><p>The number of nodes in the search tree.</p> </dd> <dt>"nof_leaf_nodes"</dt><dd><p>The number of leaf nodes in the search tree.</p> </dd> <dt>"nof_bad_nodes"</dt><dd><p>Number of bad nodes.</p> </dd> <dt>"nof_canupdates"</dt><dd><p>Number of canrep updates.</p> </dd> <dt>"max_level"</dt><dd><p>Maximum level.</p> </dd> <dt>"group_size"</dt><dd><p>The size of the automorphism group of the input graph, as a string. The string representation is necessary because the group size can easily exceed values that are exactly representable in floating point.</p> </dd> </dl> </td></tr> </table> <h3>Author(s)</h3> <p>Tommi Junttila for BLISS, Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> for the igraph and R interfaces. </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="permute.html">permute</a></code> to apply a permutation to a graph, <code><a href="isomorphic.html">graph.isomorphic</a></code> for deciding graph isomorphism, possibly based on canonical labels. </p> <h3>Examples</h3> <pre> ## Calculate the canonical form of a random graph g1 <- sample_gnm(10, 20) cp1 <- canonical_permutation(g1) cf1 <- permute(g1, cp1$labeling) ## Do the same with a random permutation of it g2 <- permute(g1, sample(vcount(g1))) cp2 <- canonical_permutation(g2) cf2 <- permute(g2, cp2$labeling) ## Check that they are the same el1 <- as_edgelist(cf1) el2 <- as_edgelist(cf2) el1 <- el1[ order(el1[,1], el1[,2]), ] el2 <- el2[ order(el2[,1], el2[,2]), ] all(el1 == el2) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>