I get unexpected results when doing a breadth or depth first search using a directed graph. If I convert the graph to an undirected graph it works fine. The example below shows the results with bfs. #numGenes <- 98; keyNode <- "G27" numGenes <- 13; keyNode <- "G11" set.seed(123) dvec <- sample(c(1,2,2,2,3,3,3,3,3,3),numGenes, replace=TRUE) names(dvec) <- sapply(1:numGenes, function(i) sprintf("G%02d",i)) set.seed(123) g <- randomNodeGraph(dvec) edges(g)[[keyNode]] [1] "G09" "G13" bfs(g, node=keyNode) [1] "G01" "G03" "G04" "G05" "G06" "G07" "G10" "G11" "G12" "G09" "G13" "G08" [13] "G02" g2 <- ugraph(g) edges(g2)[[keyNode]] [1] "G10" "G09" "G13" bfs(g2, node=keyNode) [1] "G11" "G10" "G09" "G13" "G01" "G07" "G02" "G08" "G03" "G12" "G04" "G05" [13] "G06" sessionInfo() R version 2.4.0 Patched (2006-11-03 r39792) i386-pc-mingw32 locale: LC_COLLATE=English_United States.1252;LC_CTYPE=English_United States.1252;LC_MONETARY=English_United States.1252;LC_NUMERIC=C;LC_TIME=English_United States.1252 attached base packages: [1] "stats" "graphics" "grDevices" "datasets" "utils" "tools" [7] "methods" "base" other attached packages: XML Rgraphviz geneplotter annotate RBGL graph "1.6-0" "1.12.3" "1.12.0" "1.12.1" "1.10.0" "1.12.1" annaffy Biobase cMAP GO KEGG "1.6.2" "1.12.2" "1.14.1" "1.14.1" "1.14.1" I get the same results in Linux and Windows R2.5 (not shown): sessionInfo() R version 2.4.0 (2006-10-03) x86_64-unknown-linux-gnu locale: LC_CTYPE=en_US.UTF-8;LC_NUMERIC=C;LC_TIME=en_US.UTF-8;LC_COLLATE=en_US .UTF- 8;LC_MONETARY=en_US.UTF-8;LC_MESSAGES=en_US.UTF-8;LC_PAPER=en_US.UTF- 8;LC_NAME=C;LC_ADDRESS=C;LC_TELEPHONE=C;LC_MEASUREMENT=en_US.UTF- 8;LC_IDENTIFICATION=C attached base packages: [1] "tools" "methods" "stats" "graphics" "grDevices" "utils" [7] "datasets" "base" other attached packages: geneplotter annotate Biobase RBGL graph "1.12.0" "1.12.1" "1.12.2" "1.10.0" "1.12.0" Steve Edwards USEPA