EVOLUTION-MANAGER
Edit File: dfs.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: Depth-first search</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 dfs {igraph}"><tr><td>dfs {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Depth-first search</h2> <h3>Description</h3> <p>Depth-first search is an algorithm to traverse a graph. It starts from a root vertex and tries to go quickly as far from as possible. </p> <h3>Usage</h3> <pre> dfs( graph, root, mode = c("out", "in", "all", "total"), unreachable = TRUE, order = TRUE, order.out = FALSE, father = FALSE, dist = FALSE, in.callback = NULL, out.callback = NULL, extra = NULL, rho = parent.frame(), neimode ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph.</p> </td></tr> <tr valign="top"><td><code>root</code></td> <td> <p>The single root vertex to start the search from.</p> </td></tr> <tr valign="top"><td><code>mode</code></td> <td> <p>For directed graphs specifies the type of edges to follow. ‘out’ follows outgoing, ‘in’ incoming edges. ‘all’ ignores edge directions completely. ‘total’ is a synonym for ‘all’. This argument is ignored for undirected graphs.</p> </td></tr> <tr valign="top"><td><code>unreachable</code></td> <td> <p>Logical scalar, whether the search should visit the vertices that are unreachable from the given root vertex (or vertices). If <code>TRUE</code>, then additional searches are performed until all vertices are visited.</p> </td></tr> <tr valign="top"><td><code>order</code></td> <td> <p>Logical scalar, whether to return the DFS ordering of the vertices.</p> </td></tr> <tr valign="top"><td><code>order.out</code></td> <td> <p>Logical scalar, whether to return the ordering based on leaving the subtree of the vertex.</p> </td></tr> <tr valign="top"><td><code>father</code></td> <td> <p>Logical scalar, whether to return the father of the vertices.</p> </td></tr> <tr valign="top"><td><code>dist</code></td> <td> <p>Logical scalar, whether to return the distance from the root of the search tree.</p> </td></tr> <tr valign="top"><td><code>in.callback</code></td> <td> <p>If not <code>NULL</code>, then it must be callback function. This is called whenever a vertex is visited. See details below.</p> </td></tr> <tr valign="top"><td><code>out.callback</code></td> <td> <p>If not <code>NULL</code>, then it must be callback function. This is called whenever the subtree of a vertex is completed by the algorithm. See details below.</p> </td></tr> <tr valign="top"><td><code>extra</code></td> <td> <p>Additional argument to supply to the callback function.</p> </td></tr> <tr valign="top"><td><code>rho</code></td> <td> <p>The environment in which the callback function is evaluated.</p> </td></tr> <tr valign="top"><td><code>neimode</code></td> <td> <p>This argument is deprecated from igraph 1.3.0; use <code>mode</code> instead.</p> </td></tr> </table> <h3>Details</h3> <p>The callback functions must have the following arguments: </p> <dl> <dt>graph</dt><dd><p>The input graph is passed to the callback function here.</p> </dd> <dt>data</dt><dd><p>A named numeric vector, with the following entries: ‘vid’, the vertex that was just visited and ‘dist’, its distance from the root of the search tree.</p> </dd> <dt>extra</dt><dd><p>The extra argument.</p> </dd> </dl> <p> The callback must return FALSE to continue the search or TRUE to terminate it. See examples below on how to use the callback functions. </p> <h3>Value</h3> <p>A named list with the following entries: </p> <table summary="R valueblock"> <tr valign="top"><td><code>root</code></td> <td> <p>Numeric scalar. The root vertex that was used as the starting point of the search.</p> </td></tr> <tr valign="top"><td><code>neimode</code></td> <td> <p>Character scalar. The <code>mode</code> argument of the function call. Note that for undirected graphs this is always ‘all’, irrespectively of the supplied value.</p> </td></tr> <tr valign="top"><td><code>order</code></td> <td> <p>Numeric vector. The vertex ids, in the order in which they were visited by the search.</p> </td></tr> <tr valign="top"><td><code>order.out</code></td> <td> <p>Numeric vector, the vertex ids, in the order of the completion of their subtree.</p> </td></tr> <tr valign="top"><td><code>father</code></td> <td> <p>Numeric vector. The father of each vertex, i.e. the vertex it was discovered from.</p> </td></tr> <tr valign="top"><td><code>dist</code></td> <td> <p>Numeric vector, for each vertex its distance from the root of the search tree.</p> </td></tr> </table> <p>Note that <code>order</code>, <code>order.out</code>, <code>father</code>, and <code>dist</code> might be <code>NULL</code> if their corresponding argument is <code>FALSE</code>, i.e. if their calculation is not requested. </p> <h3>Author(s)</h3> <p>Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> </p> <h3>See Also</h3> <p><code><a href="bfs.html">bfs</a></code> for breadth-first search. </p> <h3>Examples</h3> <pre> ## A graph with two separate trees dfs(make_tree(10) %du% make_tree(10), root=1, "out", TRUE, TRUE, TRUE, TRUE) ## How to use a callback f.in <- function(graph, data, extra) { cat("in:", paste(collapse=", ", data), "\n") FALSE } f.out <- function(graph, data, extra) { cat("out:", paste(collapse=", ", data), "\n") FALSE } tmp <- dfs(make_tree(10), root=1, "out", in.callback=f.in, out.callback=f.out) ## Terminate after the first component, using a callback f.out <- function(graph, data, extra) { data['vid'] == 1 } tmp <- dfs(make_tree(10) %du% make_tree(10), root=1, out.callback=f.out) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>