EVOLUTION-MANAGER
Edit File: is_chordal.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: Chordality 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 is_chordal {igraph}"><tr><td>is_chordal {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Chordality of a graph</h2> <h3>Description</h3> <p>A graph is chordal (or triangulated) if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes. </p> <h3>Usage</h3> <pre> is_chordal( graph, alpha = NULL, alpham1 = NULL, fillin = FALSE, newgraph = FALSE ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph. It may be directed, but edge directions are ignored, as the algorithm is defined for undirected graphs.</p> </td></tr> <tr valign="top"><td><code>alpha</code></td> <td> <p>Numeric vector, the maximal chardinality ordering of the vertices. If it is <code>NULL</code>, then it is automatically calculated by calling <code><a href="max_cardinality.html">max_cardinality</a></code>, or from <code>alpham1</code> if that is given..</p> </td></tr> <tr valign="top"><td><code>alpham1</code></td> <td> <p>Numeric vector, the inverse of <code>alpha</code>. If it is <code>NULL</code>, then it is automatically calculated by calling <code><a href="max_cardinality.html">max_cardinality</a></code>, or from <code>alpha</code>.</p> </td></tr> <tr valign="top"><td><code>fillin</code></td> <td> <p>Logical scalar, whether to calculate the fill-in edges.</p> </td></tr> <tr valign="top"><td><code>newgraph</code></td> <td> <p>Logical scalar, whether to calculate the triangulated graph.</p> </td></tr> </table> <h3>Details</h3> <p>The chordality of the graph is decided by first performing maximum cardinality search on it (if the <code>alpha</code> and <code>alpham1</code> arguments are <code>NULL</code>), and then calculating the set of fill-in edges. </p> <p>The set of fill-in edges is empty if and only if the graph is chordal. </p> <p>It is also true that adding the fill-in edges to the graph makes it chordal. </p> <h3>Value</h3> <p>A list with three members: </p> <table summary="R valueblock"> <tr valign="top"><td><code>chordal</code></td> <td> <p>Logical scalar, it is <code>TRUE</code> iff the input graph is chordal.</p> </td></tr> <tr valign="top"><td><code>fillin</code></td> <td> <p>If requested, then a numeric vector giving the fill-in edges. <code>NULL</code> otherwise.</p> </td></tr> <tr valign="top"><td><code>newgraph</code></td> <td> <p>If requested, then the triangulated graph, an <code>igraph</code> object. <code>NULL</code> otherwise.</p> </td></tr> </table> <h3>Author(s)</h3> <p>Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> </p> <h3>References</h3> <p>Robert E Tarjan and Mihalis Yannakakis. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. <em>SIAM Journal of Computation</em> 13, 566–579. </p> <h3>See Also</h3> <p><code><a href="max_cardinality.html">max_cardinality</a></code> </p> <h3>Examples</h3> <pre> ## The examples from the Tarjan-Yannakakis paper g1 <- graph_from_literal(A-B:C:I, B-A:C:D, C-A:B:E:H, D-B:E:F, E-C:D:F:H, F-D:E:G, G-F:H, H-C:E:G:I, I-A:H) max_cardinality(g1) is_chordal(g1, fillin=TRUE) g2 <- graph_from_literal(A-B:E, B-A:E:F:D, C-E:D:G, D-B:F:E:C:G, E-A:B:C:D:F, F-B:D:E, G-C:D:H:I, H-G:I:J, I-G:H:J, J-H:I) max_cardinality(g2) is_chordal(g2, fillin=TRUE) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>