[BioC] RBGL: bfs & dfs with directed graphs

[stephen edwards]

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