no diag element returned by "as_adjacency_matrix" when sparse = F

gauzens commented 4 months ago

What happens, and what did you expect instead?

When using the as_adjacency_matrix with sparse = F no diagonal elements (self-loops of the graph) are present in the matrix returned. Works fine when sparse = TRUE

Maybe because the loops = FALSE argument used in get.adjacency.dense is not accessible from as_adjacency_matrix?

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
a.mat = (matrix(sample(rep(c(0,1),8)), nrow = 4, ncol = 4))
diag(a.mat) = c(0,1,0,1) # make sure diag is not empty

ig = graph_from_adjacency_matrix(a.mat, mode = "directed")
b.mat = as_adjacency_matrix(ig, sparse = F)
diag(b.mat) # only 0 elements
#> [1] 0 0 0 0

^{Created on 2024-07-15 with reprex v2.1.1}

System information

R version 4.4.1 (2024-06-14) Platform: x86_64-pc-linux-gnu Running under: Ubuntu 24.04 LTS

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

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

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

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

other attached packages: [1] igraph_2.0.3

loaded via a namespace (and not attached): [1] utf8_1.2.4 R6_2.5.1 tidyselect_1.2.1 mgcv_1.9-1 Matrix_1.7-0
[6] lattice_0.22-5 magrittr_2.0.3 splines_4.4.1 glue_1.7.0 tibble_3.2.1
[11] pkgconfig_2.0.3 generics_0.1.3 dplyr_1.1.4 lifecycle_1.0.4 cli_3.6.3
[16] fansi_1.0.6 grid_4.4.1 vctrs_0.6.5 compiler_4.4.1 rstudioapi_0.16.0 [21] tools_4.4.1 nlme_3.1-165 pillar_1.9.0 rlang_1.1.4

maelle commented 4 months ago

Thank you @gauzens!

maelle commented 4 months ago

With igraph 2.0.3 (thanks git worktree) I actually get the same result.

devtools::load_all()
#> installing to /tmp/RtmpueKbZb/devtools_install_836c351b98ee/00LOCK-rigraphv2.0.3/00new/igraph/libs
#> ** checking absolute paths in shared objects and dynamic libraries
#> * DONE (igraph)
a.mat = (matrix(sample(rep(c(0,1),8)), nrow = 4, ncol = 4))
diag(a.mat) = c(0,1,0,1) # make sure diag is not empty

ig = graph_from_adjacency_matrix(a.mat, mode = "directed")
b.mat = as_adjacency_matrix(ig, sparse = F)
diag(b.mat) # only 0 elements
#> [1] 0 0 0 0

^{Created on 2024-07-17 with reprex v2.1.0}

krlmlr commented 4 months ago

Is this the consequence of a known change listed in https://github.com/igraph/igraph/blob/master/CHANGELOG.md ? What's the last version of the igraph package where this worked?

szhorvat commented 4 months ago

I can't be on github much, but I can't bear to see things stalling, so responding very briefly:

This is a bug that must be fixed. I consider it to be a serious issue that should be fixed for 2.0.4. Minimal example: as_adjacency_matrix(make_graph(c(1,1)), sparse=F).
This functionality does not dispatch to the C core. It is implemented in pure R. Quickfix must be in R, long-term fix is to dispatch to C core.
Conversions to and from adjacency matrices are implemented in the C core for all cases since 0.10. This includes sparse/dense, and weighted/non-weights. This was one of the things I insisted should have been done before 2.0.0, to make sure that there is no discrepancy between the R and C implementations. It also requires a breaking change, as the non-standard attr should be changed to a standard weights in as_adjacency_matrix() (#906), a blocker for several more fixes (like #903 and similar). Furthermore, the loops setting from the C core should be exposed, so we don't just control whether to ignore the diagonal, but whether to count self-loops once, twice, or not at all. I strongly suggest loops="twice" as default for conversion both to and from adjacency matrices, as this is the only mathematically well-founded choice.
Several of the R_igraph_sparsemat... functions in rinterface_extra.c are completely buggy and must be rewritten properly before a dispatch to the C core can be implemented.

To understand loop counting, see https://igraph.org/c/html/latest/igraph-Structural.html#igraph_get_adjacency and and https://igraph.org/c/html/latest/igraph-Generators.html#igraph_adjacency

I did some work on initial loop support, but my PR was closed. I suggest you re-use the work there: https://github.com/igraph/rigraph/pull/1063

See also:

krlmlr commented 4 months ago

@Antonov548: I propose we start by exposing the conversion to and from adjacency matrices to be used from R, without switching any exported code to use it. This allows us to compare the behavior and progress step by step without too many blockers. Can you take this on, please?

emilio-berti commented 4 months ago

Here with @gauzens. We added the argument loops = TRUE to R/conversion.R:

diff --git a/R/conversion.R b/R/conversion.R
index 6c9fdf9f0..f18b5b580 100644
--- a/R/conversion.R
+++ b/R/conversion.R
@@ -348,7 +348,7 @@ as_adjacency_matrix <- function(graph, type = c("both", "upper", "lower"),
   if (sparse) {
     get.adjacency.sparse(graph, type = type, attr = attr, names = names)
   } else {
-    get.adjacency.dense(graph, type = type, attr = attr, weights = NULL, names = names)
+    get.adjacency.dense(graph, type = type, attr = attr, weights = NULL, names = names, loops = TRUE)
   }
 }

This seems to solve the issue:

as_adjacency_matrix(make_graph(c(1,1)), sparse=F)
     [,1]
[1,]    1

szhorvat commented 4 months ago

There's a bit more needed than that to be consistent with the sparse version. #1437 could be a starting point. I hope this helps @Antonov548, please feel free to take over.

The dense and sparse versions must be consistent in whether they put 1s or 2s on the diagonal with undirected graphs. Example:

as_adjacency_matrix(make_graph(c(1,1, 1,2), directed=F), sparse=F)

krlmlr commented 2 months ago

IIUC we want to get rid of these differences. The PR by Szabolcs is a good starting point.

options(conflicts.policy = list(warn = FALSE))
library(igraph)
as_adjacency_matrix(make_graph(c(1, 1, 1, 2), directed = F), sparse = F)
#>      [,1] [,2]
#> [1,]    0    1
#> [2,]    1    0
as_adjacency_matrix(make_graph(c(1, 1, 1, 2), directed = F), sparse = T)
#> 2 x 2 sparse Matrix of class "dgCMatrix"
#>         
#> [1,] 1 1
#> [2,] 1 .

^{Created on 2024-08-28 with reprex v2.1.0}

igraph / rigraph