is_chordal crashes R when called on simple graph

[thomasp85]

I came across this bug while testing tidygraph. The following code consistently crashes R on my Mac:

library(igraph)
gr <- graph_from_adj_list(list(4, 3, 2, 1))
is_chordal(gr)

Session info ------------------------------------------------------------------------------------------
 setting  value                       
 version  R version 3.3.2 (2016-10-31)
 system   x86_64, darwin13.4.0        
 ui       RStudio (1.0.136)           
 language (EN)                        
 collate  en_US.UTF-8                 
 tz       Europe/Copenhagen           
 date     2017-03-16                  

Packages ----------------------------------------------------------------------------------------------
 package  * version date       source        
 devtools   1.12.0  2016-06-24 CRAN (R 3.3.0)
 digest     0.6.12  2017-01-27 cran (@0.6.12)
 igraph   * 1.0.1   2015-06-26 CRAN (R 3.3.0)
 magrittr   1.5     2014-11-22 CRAN (R 3.3.0)
 memoise    1.0.0   2016-01-29 CRAN (R 3.3.0)
 withr      1.0.2   2016-06-20 CRAN (R 3.3.0)

[mlindsk]

I have a similar problem for a simple undirected graph with 55 nodes. I get the following:

 *** caught segfault ***
address (nil), cause 'unknown'

Traceback:
 1: is.chordal(h)

Possible actions:
1: abort (with core dump, if enabled)
2: normal R exit
3: exit R without saving workspace
4: exit R saving workspace
Selection: 

@thomasp85 it seems that in your case, the problem can be solved by calling as.undirected(gr) before as_chordal - but there should be some kind of dispatch on the class of the graph then.

> sessionInfo()
R version 3.6.3 (2020-02-29)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 18.04.4 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.7.1
LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.7.1

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

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

other attached packages:
[1] dplyr_0.8.5  igraph_1.2.5

loaded via a namespace (and not attached):
 [1] Rcpp_1.0.4.6     crayon_1.3.4     assertthat_0.2.1 R6_2.4.1        
 [5] lifecycle_0.2.0  magrittr_1.5     pillar_1.4.4     rlang_0.4.6     
 [9] vctrs_0.3.0      ellipsis_0.3.0   glue_1.4.1       purrr_0.3.4     
[13] compiler_3.6.3   pkgconfig_2.0.3  tidyselect_1.0.0 tibble_3.0.1    
> 

[szhorvat]

The issue with not checking for directed graphs is solved in the latest C core.

@mlindsk Can you please share the graph? Without that, we cannot debug the problem.

[mlindsk]

Ok, however the graph is undirected. @szhorvat Sure, the graph is now attached.

[szhorvat]

Ok, however the graph is undirected.

Yes, I understood that. That is why I was asking for it.

I have a similar problem for a simple undirected graph

However, this graph is not simple. It has parallel edges. This is what causes the problem. A check for simple graphs was also added in the latest C core, so I guess this is addressed (and should propagate to the R interface eventually).

You can use simplify to remove multi-edges.

[mlindsk]

@szhorvat Thanks! This clarifies things.

[szhorvat]

This now works in the dev branch version, closing.

> library(igraph)
> gr <- graph_from_adj_list(list(4, 3, 2, 1))
> is_chordal(gr)
Error in is_chordal(gr) : 
  At decomposition.c:74 : Maximum cardinality search works on undirected graphs only, Invalid value