bfs: Breadth and Depth-first search

Description Usage Arguments Details Value Author(s) References Examples

Description

These functions return information on graph traversal by breadth and depth first search using routines from the BOOST library.

Usage

1
2
bfs(object, node, checkConn=TRUE)
dfs(object, node, checkConn=TRUE)

Arguments

object

instance of class graph from Bioconductor graph class

node

node name where search starts; defaults to the node in first position in the node vector.

checkConn

logical for backwards compatibility; this parameter has no effect as of RBGL 1.7.9 and will be removed in future versions.

Details

These two functions are interfaces to the BOOST graph library functions for breadth first and depth first search. Both methods handle unconnected graphs by applying the algorithms over the connected components.

Cormen et al note (p 542) that 'results of depth-first search may depend upon the order in which the vertices are examined ... These different visitation orders tend not to cause problems in practice, as any DFS result can usually be used effectively, with essentially equivalent results'.

Value

For bfs a vector of node indices in order of BFS visit.

For dfs a list of two vectors of nodes, with elements discover (order of DFS discovery), and finish (order of DFS completion).

Author(s)

VJ Carey <[email protected]>

References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
con1 <- file(system.file("XML/bfsex.gxl",package="RBGL"), open="r")
dd <- fromGXL(con1)
close(con1)

bfs(dd, "r")
bfs(dd, "s")

con2 <- file(system.file("XML/dfsex.gxl",package="RBGL"), open="r")
dd2 <- fromGXL(con2)
close(con2)

dfs(dd2, "u")

Example output

Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, cbind, colnames, do.call, duplicated, eval, evalq,
    get, grep, grepl, intersect, is.unsorted, lapply, lengths, mapply,
    match, mget, order, paste, pmax, pmax.int, pmin, pmin.int, rank,
    rbind, rownames, sapply, setdiff, sort, table, tapply, union,
    unique, unsplit, which, which.max, which.min

[1] "r" "s" "v" "w" "t" "x" "u" "y"
[1] "s" "w" "r" "t" "x" "v" "u" "y"
$discovered
[1] "u" "v" "y" "x" "w" "z"

$finish
[1] "x" "y" "v" "u" "z" "w"

RBGL documentation built on May 31, 2017, 8:23 p.m.