I have a matrix like this:
1 0 1 0 1 1
1 1 1 0 0 1
1 0 1 1 1 1
0 0 0 1 0 0
0 1 1 1 0 1
1 1 0 1 1 1
where the 1 represents a node and the 0 represents that there's no node, so for example from (1, 1) we can go to (2, 1) and from (2, 1) we can go to (3, 1) or (2, 2) and so on.
The graph is undirected and all the edges has the same cost (just say cost of 1)
So in total we have 23 nodes, so the adjency matrix should be a 23 x 23 matrix that has 1 telling us that two nodes are connected.
Is there any way to transform this matrix into the adjency matrix of the graph using R?
CodePudding user response：
Create a data frame with one row per entry of the matrix and the corresponding row and column number and then subset that data frame down to the entries that are 1. (@Andrew Gustar deleted his post but that post shows that the row and col columns of d could also have been expressed as d <- as.data.frame(which(m == 1, arr.ind = TRUE)) ). Now use outer to determine whether two rows of that data frame represent adjacent nodes or not. Change the ==1 to <=1 in the line that sets adj if nodes can be adjacent to themselves.
d <- data.frame(value = c(m), row = c(row(m)), col = c(col(m))) |>
subset(value == 1)
adj <- with(d, abs(outer(row, row, `-`)) abs(outer(col, col, `-`)) == 1)
We can view the adjacency matrix easily by converting it to a sparse matrix.
Matrix::Matrix(adj)
giving:
23 x 23 sparse Matrix of class "dsCMatrix"
[1,] . 1 . . . . . . . . . . . . . . . . . . . . .
[2,] 1 . 1 . 1 . . . . . . . . . . . . . . . . . .
[3,] . 1 . . . . . . . . . . . . . . . . . . . . .
[4,] . . . . . . 1 . . . . . . . . . . . . . . . .
[5,] . 1 . . . . . . 1 . . . . . . . . . . . . . .
[6,] . . . . . . 1 . . . 1 . . . . . . . . . . . .
[7,] . . . 1 . 1 . . . . . . . . . . . . . . . . .
[8,] . . . . . . . . 1 . . . . . . . . . . . . . .
[9,] . . . . 1 . . 1 . 1 . . . . . . . . . . . . .
[10,] . . . . . . . . 1 . . 1 . . . . . . . . . . .
[11,] . . . . . 1 . . . . . . . 1 . . . . . . . . .
[12,] . . . . . . . . . 1 . . 1 . . . 1 . . . . . .
[13,] . . . . . . . . . . . 1 . 1 . . . . . . . . .
[14,] . . . . . . . . . . 1 . 1 . 1 . . . . . . . .
[15,] . . . . . . . . . . . . . 1 . . . 1 . . . . .
[16,] . . . . . . . . . . . . . . . . . . 1 . . . .
[17,] . . . . . . . . . . . 1 . . . . . . . . 1 . .
[18,] . . . . . . . . . . . . . . 1 . . . . . . . 1
[19,] . . . . . . . . . . . . . . . 1 . . . 1 . . .
[20,] . . . . . . . . . . . . . . . . . . 1 . 1 . .
[21,] . . . . . . . . . . . . . . . . 1 . . 1 . . .
[22,] . . . . . . . . . . . . . . . . . . . . . . 1
[23,] . . . . . . . . . . . . . . . . . 1 . . . 1 .
Note
m <- structure(c(1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1,
0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1), .Dim = c(6L,
6L), .Dimnames = list(NULL, NULL))
CodePudding user response：
We can try this
v <- c(row(m) * m 1i * col(m) * m)[m > 0]
d <- (abs(outer(v, v, `-`)) == 1)
which gives
> d
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
[1,] 0 1 0 0 0 0 0 0 0 0 0 0 0
[2,] 1 0 1 0 1 0 0 0 0 0 0 0 0
[3,] 0 1 0 0 0 0 0 0 0 0 0 0 0
[4,] 0 0 0 0 0 0 1 0 0 0 0 0 0
[5,] 0 1 0 0 0 0 0 0 1 0 0 0 0
[6,] 0 0 0 0 0 0 1 0 0 0 1 0 0
[7,] 0 0 0 1 0 1 0 0 0 0 0 0 0
[8,] 0 0 0 0 0 0 0 0 1 0 0 0 0
[9,] 0 0 0 0 1 0 0 1 0 1 0 0 0
[10,] 0 0 0 0 0 0 0 0 1 0 0 1 0
[11,] 0 0 0 0 0 1 0 0 0 0 0 0 0
[12,] 0 0 0 0 0 0 0 0 0 1 0 0 1
[13,] 0 0 0 0 0 0 0 0 0 0 0 1 0
[14,] 0 0 0 0 0 0 0 0 0 0 1 0 1
[15,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[16,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[17,] 0 0 0 0 0 0 0 0 0 0 0 1 0
[18,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[19,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[20,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[21,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[22,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[23,] 0 0 0 0 0 0 0 0 0 0 0 0 0
[,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23]
[1,] 0 0 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 0 0 0 0 0 0
[3,] 0 0 0 0 0 0 0 0 0 0
[4,] 0 0 0 0 0 0 0 0 0 0
[5,] 0 0 0 0 0 0 0 0 0 0
[6,] 0 0 0 0 0 0 0 0 0 0
[7,] 0 0 0 0 0 0 0 0 0 0
[8,] 0 0 0 0 0 0 0 0 0 0
[9,] 0 0 0 0 0 0 0 0 0 0
[10,] 0 0 0 0 0 0 0 0 0 0
[11,] 1 0 0 0 0 0 0 0 0 0
[12,] 0 0 0 1 0 0 0 0 0 0
[13,] 1 0 0 0 0 0 0 0 0 0
[14,] 0 1 0 0 0 0 0 0 0 0
[15,] 1 0 0 0 1 0 0 0 0 0
[16,] 0 0 0 0 0 1 0 0 0 0
[17,] 0 0 0 0 0 0 0 1 0 0
[18,] 0 1 0 0 0 0 0 0 0 1
[19,] 0 0 1 0 0 0 1 0 0 0
[20,] 0 0 0 0 0 1 0 1 0 0
[21,] 0 0 0 1 0 0 1 0 0 0
[22,] 0 0 0 0 0 0 0 0 0 1
[23,] 0 0 0 0 1 0 0 0 1 0