EVOLUTION-MANAGER
Edit File: isomorphic.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: Decide if two graphs are isomorphic</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 isomorphic {igraph}"><tr><td>isomorphic {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Decide if two graphs are isomorphic</h2> <h3>Description</h3> <p>Decide if two graphs are isomorphic </p> <h3>Usage</h3> <pre> isomorphic(graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ...) is_isomorphic_to( graph1, graph2, method = c("auto", "direct", "vf2", "bliss"), ... ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph1</code></td> <td> <p>The first graph.</p> </td></tr> <tr valign="top"><td><code>graph2</code></td> <td> <p>The second graph.</p> </td></tr> <tr valign="top"><td><code>method</code></td> <td> <p>The method to use. Possible values: ‘auto’, ‘direct’, ‘vf2’, ‘bliss’. See their details below.</p> </td></tr> <tr valign="top"><td><code>...</code></td> <td> <p>Additional arguments, passed to the various methods.</p> </td></tr> </table> <h3>Value</h3> <p>Logical scalar, <code>TRUE</code> if the graphs are isomorphic. </p> <h3>‘auto’ method</h3> <p>It tries to select the appropriate method based on the two graphs. This is the algorithm it uses: </p> <ol> <li><p> If the two graphs do not agree on their order and size (i.e. number of vertices and edges), then return <code>FALSE</code>. </p> </li> <li><p> If the graphs have three or four vertices, then the ‘direct’ method is used. </p> </li> <li><p> If the graphs are directed, then the ‘vf2’ method is used. </p> </li> <li><p> Otherwise the ‘bliss’ method is used. </p> </li></ol> <h3>‘direct’ method</h3> <p>This method only works on graphs with three or four vertices, and it is based on a pre-calculated and stored table. It does not have any extra arguments. </p> <h3>‘vf2’ method</h3> <p>This method uses the VF2 algorithm by Cordella, Foggia et al., see references below. It supports vertex and edge colors and have the following extra arguments: </p> <dl> <dt>vertex.color1, vertex.color2</dt><dd><p>Optional integer vectors giving the colors of the vertices for colored graph isomorphism. If they are not given, but the graph has a “color” vertex attribute, then it will be used. If you want to ignore these attributes, then supply <code>NULL</code> for both of these arguments. See also examples below.</p> </dd> <dt>edge.color1, edge.color2</dt><dd><p>Optional integer vectors giving the colors of the edges for edge-colored (sub)graph isomorphism. If they are not given, but the graph has a “color” edge attribute, then it will be used. If you want to ignore these attributes, then supply <code>NULL</code> for both of these arguments.</p> </dd> </dl> <h3>‘bliss’ method</h3> <p>Uses the BLISS algorithm by Junttila and Kaski, and it works for undirected graphs. For both graphs the <code><a href="canonical_permutation.html">canonical_permutation</a></code> and then the <code><a href="permute.html">permute</a></code> function is called to transfer them into canonical form; finally the canonical forms are compared. Extra arguments: </p> <dl> <dt>sh</dt><dd><p>Character constant, the heuristics to use in the BLISS algorithm for <code>graph1</code> and <code>graph2</code>. See the <code>sh</code> argument of <code><a href="canonical_permutation.html">canonical_permutation</a></code> for possible values.</p> </dd> </dl> <p><code>sh</code> defaults to ‘fm’. </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> <p>LP Cordella, P Foggia, C Sansone, and M Vento: An improved algorithm for matching large graphs, <em>Proc. of the 3rd IAPR TC-15 Workshop on Graphbased Representations in Pattern Recognition</em>, 149–159, 2001. </p> <h3>See Also</h3> <p>Other graph isomorphism: <code><a href="count_isomorphisms.html">count_isomorphisms</a>()</code>, <code><a href="count_subgraph_isomorphisms.html">count_subgraph_isomorphisms</a>()</code>, <code><a href="graph_from_isomorphism_class.html">graph_from_isomorphism_class</a>()</code>, <code><a href="isomorphism_class.html">isomorphism_class</a>()</code>, <code><a href="isomorphisms.html">isomorphisms</a>()</code>, <code><a href="subgraph_isomorphic.html">subgraph_isomorphic</a>()</code>, <code><a href="subgraph_isomorphisms.html">subgraph_isomorphisms</a>()</code> </p> <h3>Examples</h3> <pre> # create some non-isomorphic graphs g1 <- graph_from_isomorphism_class(3, 10) g2 <- graph_from_isomorphism_class(3, 11) isomorphic(g1, g2) # create two isomorphic graphs, by permuting the vertices of the first g1 <- barabasi.game(30, m=2, directed=FALSE) g2 <- permute(g1, sample(vcount(g1))) # should be TRUE isomorphic(g1, g2) isomorphic(g1, g2, method = "bliss") isomorphic(g1, g2, method = "vf2") # colored graph isomorphism g1 <- make_ring(10) g2 <- make_ring(10) isomorphic(g1, g2) V(g1)$color <- rep(1:2, length = vcount(g1)) V(g2)$color <- rep(2:1, length = vcount(g2)) # consider colors by default count_isomorphisms(g1, g2) # ignore colors count_isomorphisms(g1, g2, vertex.color1 = NULL, vertex.color2 = NULL) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>