EVOLUTION-MANAGER
Edit File: subgraph_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 a graph is subgraph isomorphic to another one</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 subgraph_isomorphic {igraph}"><tr><td>subgraph_isomorphic {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Decide if a graph is subgraph isomorphic to another one</h2> <h3>Description</h3> <p>Decide if a graph is subgraph isomorphic to another one </p> <h3>Usage</h3> <pre> subgraph_isomorphic(pattern, target, method = c("auto", "lad", "vf2"), ...) is_subgraph_isomorphic_to( pattern, target, method = c("auto", "lad", "vf2"), ... ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>pattern</code></td> <td> <p>The smaller graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.</p> </td></tr> <tr valign="top"><td><code>target</code></td> <td> <p>The bigger graph, it might be directed or undirected. Undirected graphs are treated as directed graphs with mutual edges.</p> </td></tr> <tr valign="top"><td><code>method</code></td> <td> <p>The method to use. Possible values: ‘auto’, ‘lad’, ‘vf2’. 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 <code>pattern</code> is isomorphic to a (possibly induced) subgraph of <code>target</code>. </p> <h3>‘auto’ method</h3> <p>This method currently selects ‘lad’, always, as it seems to be superior on most graphs. </p> <h3>‘lad’ method</h3> <p>This is the LAD algorithm by Solnon, see the reference below. It has the following extra arguments: </p> <dl> <dt>domains</dt><dd><p>If not <code>NULL</code>, then it specifies matching restrictions. It must be a list of <code>target</code> vertex sets, given as numeric vertex ids or symbolic vertex names. The length of the list must be <code>vcount(pattern)</code> and for each vertex in <code>pattern</code> it gives the allowed matching vertices in <code>target</code>. Defaults to <code>NULL</code>.</p> </dd> <dt>induced</dt><dd><p>Logical scalar, whether to search for an induced subgraph. It is <code>FALSE</code> by default.</p> </dd> <dt>time.limit</dt><dd><p>The processor time limit for the computation, in seconds. It defaults to <code>Inf</code>, which means no limit.</p> </dd> </dl> <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>References</h3> <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> <p>C. Solnon: AllDifferent-based Filtering for Subgraph Isomorphism, <em>Artificial Intelligence</em> 174(12-13):850–864, 2010. </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="isomorphic.html">isomorphic</a>()</code>, <code><a href="isomorphism_class.html">isomorphism_class</a>()</code>, <code><a href="isomorphisms.html">isomorphisms</a>()</code>, <code><a href="subgraph_isomorphisms.html">subgraph_isomorphisms</a>()</code> </p> <h3>Examples</h3> <pre> # A LAD example pattern <- make_graph(~ 1:2:3:4:5, 1 - 2:5, 2 - 1:5:3, 3 - 2:4, 4 - 3:5, 5 - 4:2:1) target <- make_graph(~ 1:2:3:4:5:6:7:8:9, 1 - 2:5:7, 2 - 1:5:3, 3 - 2:4, 4 - 3:5:6:8:9, 5 - 1:2:4:6:7, 6 - 7:5:4:9, 7 - 1:5:6, 8 - 4:9, 9 - 6:4:8) domains <- list(`1` = c(1,3,9), `2` = c(5,6,7,8), `3` = c(2,4,6,7,8,9), `4` = c(1,3,9), `5` = c(2,4,8,9)) subgraph_isomorphisms(pattern, target) subgraph_isomorphisms(pattern, target, induced = TRUE) subgraph_isomorphisms(pattern, target, domains = domains) # Directed LAD example pattern <- make_graph(~ 1:2:3, 1 -+ 2:3) dring <- make_ring(10, directed = TRUE) subgraph_isomorphic(pattern, dring) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>