graph.dfs: Depth-first search

Description

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.

Usage

graph.dfs (graph, root, neimode = 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())

Arguments

graph

The input graph.

root

The single root vertex to start the search from.

neimode

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<

unreachable

Logical scalar, whether the search should visit the vertices that are unreachable from the given root vertex (or vertices). If TRUE, then additional searches are performed until all vertices are visited.

order

Logical scalar, whether to return the DFS ordering of the vertices.

order.out

Logical scalar, whether to return the ordering based on leaving the subtree of the vertex.

father

Logical scalar, whether to return the father of the vertices.

dist

Logical scalar, whether to return the distance from the root of the search tree.

in.callback

If not NULL, then it must be callback function. This is called whenever a vertex is visited. See details below.

out.callback

If not NULL, then it must be callback function. This is called whenever the subtree of a vertex is completed by the algorithm. See details below.

extra

Additional argument to supply to the callback function.

rho

The environment in which the callback function is evaluated.

Value

A named list with the following entries:
rootNumeric scalar. The root vertex that was used as the starting point of the search.
neimodeCharacter scalar. The neimode argument of the function call. Note that for undirected graphs this is always all, irrespectively of the supplied value.
orderNumeric vector. The vertex ids, in the order in which they were visited by the search.
order.outNumeric vector, the vertex ids, in the order of the completion of their subtree.
fatherNumeric vector. The father of each vertex, i.e. the vertex it was discovered from.
distNumeric vector, for each vertex its distance from the root of the search tree.
Note that order, order.out, father, and dist might be NULL if their corresponding argument is FALSE, i.e. if their calculation is not requested.

Details

The callback functions must have the following arguments: [object Object],[object Object],[object Object] See examples below on how to use the callback functions.

Examples

Run this code

## A graph with two separate trees
graph.dfs(graph.tree(10) %du% graph.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), "")
  FALSE
}
f.out <- function(graph, data, extra) {
  cat("out:", paste(collapse=", ", data), "")
  FALSE
}
tmp <- graph.dfs(graph.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 <- graph.dfs(graph.tree(10) %du% graph.tree(10), root=1,
                 out.callback=f.out)