Skip to content

Breadth-first search documentation and output. #1639

Open
@llrs

Description

@llrs

What happens, and what did you expect instead?

There are several surprising elements with the documentation of bfs output.
The root for example does not return all the indices used. father, pred and succ elements of the output are not a "Numeric vector." (related to #522)


In addition, I have found that if multiple roots are provided they might not be used or are not reported to be of dist == 0 (see last lines of the example). I think this comes from the C library.

To reproduce

library("igraph")
#> 
#> Attaching package: 'igraph'
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union
packageVersion("igraph")
#> [1] '2.1.2'
g <- make_ring(10) %du% make_ring(10)
roots <- c(1, 5, 15)
out <- bfs(g, root = roots, father = TRUE, succ = TRUE, pred = TRUE, 
           rank = TRUE, unreachable = FALSE, dist = TRUE)
out$root
#> [1] 1
is(out$father)
#> [1] "igraph.vs"
is(out$pred)
#> [1] "igraph.vs"
is(out$succ)
#> [1] "igraph.vs"
out$dist[roots]
#> [1] 0 4 0
stopifnot("Roots doesn't match those provided" = sum(out$dist == 0L) == length(roots))
#> Error: Roots doesn't match those provided

Created on 2024-12-25 with reprex v2.1.1

System information

Ubuntu 24.04, R from rig add R-4.4.2 (+ igraph compiled locally), session:

R version 4.4.2 (2024-10-31)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 24.04.1 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/openblas-pthread/libblas.so.3 
LAPACK: /usr/lib/x86_64-linux-gnu/openblas-pthread/libopenblasp-r0.3.26.so;  LAPACK version 3.12.0

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C               LC_TIME=ca_ES.UTF-8       
 [4] LC_COLLATE=en_US.UTF-8     LC_MONETARY=ca_ES.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=ca_ES.UTF-8       LC_NAME=C                  LC_ADDRESS=C              
[10] LC_TELEPHONE=C             LC_MEASUREMENT=ca_ES.UTF-8 LC_IDENTIFICATION=C       

time zone: Europe/Madrid
tzcode source: system (glibc)

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] igraph_2.1.2        BiocManager_1.30.25 cyclocomp_1.1.1     testthat_3.2.1.1    devtools_2.4.5     
[6] usethis_3.0.0      

loaded via a namespace (and not attached):
 [1] utf8_1.2.4             digest_0.6.37          magrittr_2.0.3         evaluate_1.0.1        
 [5] pkgload_1.4.0          fastmap_1.2.0          processx_3.8.4         pkgbuild_1.4.5        
 [9] sessioninfo_1.2.2.9000 brio_1.1.5             urlchecker_1.0.1       ps_1.8.1              
[13] promises_1.3.0         purrr_1.0.2            fansi_1.0.6            cli_3.6.3             
[17] shiny_1.9.1            rlang_1.1.4            crayon_1.5.3           ellipsis_0.3.2        
[21] reprex_2.1.1           remotes_2.5.0          withr_3.0.2            cachem_1.1.0          
[25] yaml_2.3.10            tools_4.4.2            memoise_2.0.1          httpuv_1.6.15         
[29] vctrs_0.6.5            R6_2.5.1               mime_0.12              lifecycle_1.0.4       
[33] fs_1.6.5               htmlwidgets_1.6.4      miniUI_0.1.1.1         clipr_0.8.0           
[37] pkgconfig_2.0.3        desc_1.4.3             callr_3.7.6            pillar_1.9.0          
[41] later_1.3.2            glue_1.8.0             profvis_0.4.0          Rcpp_1.0.13-1         
[45] xfun_0.49              tibble_3.2.1           rstudioapi_0.17.1      knitr_1.49            
[49] xtable_1.8-4           htmltools_0.5.8.1      rmarkdown_2.29         compiler_4.4.2  

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions