EVOLUTION-MANAGER
Edit File: dominator_tree.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: Dominator tree</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 dominator_tree {igraph}"><tr><td>dominator_tree {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Dominator tree</h2> <h3>Description</h3> <p>Dominator tree of a directed graph. </p> <h3>Usage</h3> <pre> dominator_tree(graph, root, mode = c("out", "in", "all", "total")) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>A directed graph. If it is not a flowgraph, and it contains some vertices not reachable from the root vertex, then these vertices will be collected and returned as part of the result.</p> </td></tr> <tr valign="top"><td><code>root</code></td> <td> <p>The id of the root (or source) vertex, this will be the root of the tree.</p> </td></tr> <tr valign="top"><td><code>mode</code></td> <td> <p>Constant, must be ‘<code>in</code>’ or ‘<code>out</code>’. If it is ‘<code>in</code>’, then all directions are considered as opposite to the original one in the input graph.</p> </td></tr> </table> <h3>Details</h3> <p>A flowgraph is a directed graph with a distinguished start (or root) vertex <i>r</i>, such that for any vertex <i>v</i>, there is a path from <i>r</i> to <i>v</i>. A vertex <i>v</i> dominates another vertex <i>w</i> (not equal to <i>v</i>), if every path from <i>r</i> to <i>w</i> contains <i>v</i>. Vertex <i>v</i> is the immediate dominator or <i>w</i>, <i>v=idom(w)</i>, if <i>v</i> dominates <i>w</i> and every other dominator of <i>w</i> dominates <i>v</i>. The edges <i>{(idom(w),w)| w is not r}</i> form a directed tree, rooted at <i>r</i>, called the dominator tree of the graph. Vertex <i>v</i> dominates vertex <i>w</i> if and only if <i>v</i> is an ancestor of <i>w</i> in the dominator tree. </p> <p>This function implements the Lengauer-Tarjan algorithm to construct the dominator tree of a directed graph. For details see the reference below. </p> <h3>Value</h3> <p>A list with components: </p> <table summary="R valueblock"> <tr valign="top"><td><code>dom</code></td> <td> <p> A numeric vector giving the immediate dominators for each vertex. For vertices that are unreachable from the root, it contains <code>NaN</code>. For the root vertex itself it contains minus one. </p> </td></tr> <tr valign="top"><td><code>domtree</code></td> <td> <p> A graph object, the dominator tree. Its vertex ids are the as the vertex ids of the input graph. Isolate vertices are the ones that are unreachable from the root. </p> </td></tr> <tr valign="top"><td><code>leftout</code></td> <td> <p> A numeric vector containing the vertex ids that are unreachable from the root. </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>Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for finding dominators in a flowgraph, <em>ACM Transactions on Programming Languages and Systems (TOPLAS)</em> I/1, 121–141, 1979. </p> <h3>Examples</h3> <pre> ## The example from the paper g <- graph_from_literal(R-+A:B:C, A-+D, B-+A:D:E, C-+F:G, D-+L, E-+H, F-+I, G-+I:J, H-+E:K, I-+K, J-+I, K-+I:R, L-+H) dtree <- dominator_tree(g, root="R") layout <- layout_as_tree(dtree$domtree, root="R") layout[,2] <- -layout[,2] plot(dtree$domtree, layout=layout, vertex.label=V(dtree$domtree)$name) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>