find neighbouring elements of a matrix in R

by

Here’s a nice example. I did 4×4 so we can see it easily, but it’s all adjustable by n. It’s also fully vectorized so should have good speed.

n = 4
mat = matrix(1:n^2, nrow = n)
mat.pad = rbind(NA, cbind(NA, mat, NA), NA)

With the padded matrix, the neighbors are just n by n submatrices, shifting around. Using compass directions as labels:

ind = 2:(n + 1) # row/column indices of the "middle"
neigh = rbind(N  = as.vector(mat.pad[ind - 1, ind    ]),
              NE = as.vector(mat.pad[ind - 1, ind + 1]),
              E  = as.vector(mat.pad[ind    , ind + 1]),
              SE = as.vector(mat.pad[ind + 1, ind + 1]),
              S  = as.vector(mat.pad[ind + 1, ind    ]),
              SW = as.vector(mat.pad[ind + 1, ind - 1]),
              W  = as.vector(mat.pad[ind    , ind - 1]),
              NW = as.vector(mat.pad[ind - 1, ind - 1]))

mat
#      [,1] [,2] [,3] [,4]
# [1,]    1    5    9   13
# [2,]    2    6   10   14
# [3,]    3    7   11   15
# [4,]    4    8   12   16

  neigh[, 1:6]
#    [,1] [,2] [,3] [,4] [,5] [,6]
# N    NA    1    2    3   NA    5
# NE   NA    5    6    7   NA    9
# E     5    6    7    8    9   10
# SE    6    7    8   NA   10   11
# S     2    3    4   NA    6    7
# SW   NA   NA   NA   NA    2    3
# W    NA   NA   NA   NA    1    2
# NW   NA   NA   NA   NA   NA    1

So you can see for the first element mat[1,1], starting at North and going clockwise the neighbors are the first column of neigh. The next element is mat[2,1], and so on down the columns of mat. (You can also compare to @mrip’s answer and see that our columns have the same elements, just in a different order.)

Benchmarking

Small matrix

mat = matrix(1:16, nrow = 4)
mbm(gregor(mat), mrip(mat), marat(mat), u20650(mat), times = 100)
# Unit: microseconds
#         expr     min       lq      mean   median       uq      max neval  cld
#  gregor(mat)  25.054  30.0345  34.04585  31.9960  34.7130   61.879   100 a   
#    mrip(mat) 420.167 443.7120 482.44136 466.1995 483.4045 1820.121   100   c 
#   marat(mat) 746.462 784.0410 812.10347 808.1880 832.4870  911.570   100    d
#  u20650(mat) 186.843 206.4620 220.07242 217.3285 230.7605  269.850   100  b

On a larger matrix I had to take out user20650’s function because it tried to allocate a 232.8 Gb vector, and I also took out Marat’s answer after waiting for about 10 minutes. 

mat = matrix(1:500^2, nrow = 500)

mbm(gregor(mat), mrip(mat), times = 100)
# Unit: milliseconds
#         expr       min        lq      mean    median        uq      max neval cld
#  gregor(mat) 19.583951 21.127883 30.674130 21.656866 22.433661 127.2279   100   b
#    mrip(mat)  2.213725  2.368421  8.957648  2.758102  2.958677 104.9983   100  a

So it looks like in any case where time matters, @mrip’s solutions is by far the fastest.

Functions used:

gregor = function(mat) {
    n = nrow(mat)
    mat.pad = rbind(NA, cbind(NA, mat, NA), NA)
    ind = 2:(n + 1) # row/column indices of the "middle"
    neigh = rbind(N  = as.vector(mat.pad[ind - 1, ind    ]),
                  NE = as.vector(mat.pad[ind - 1, ind + 1]),
                  E  = as.vector(mat.pad[ind    , ind + 1]),
                  SE = as.vector(mat.pad[ind + 1, ind + 1]),
                  S  = as.vector(mat.pad[ind + 1, ind    ]),
                  SW = as.vector(mat.pad[ind + 1, ind - 1]),
                  W  = as.vector(mat.pad[ind    , ind - 1]),
                  NW = as.vector(mat.pad[ind - 1, ind - 1]))
    return(neigh)
}

mrip = function(mat) {
    m2<-cbind(NA,rbind(NA,mat,NA),NA)
    addresses <- expand.grid(x = 1:4, y = 1:4)
    ret <- c()
    for(i in 1:-1)
        for(j in 1:-1)
            if(i!=0 || j !=0)
                ret <- rbind(ret,m2[addresses$x+i+1+nrow(m2)*(addresses$y+j)]) 
    return(ret)
}

get.neighbors <- function(rw, z, mat) {
    # Convert to absolute addresses 
    z2 <- t(z + unlist(rw))
    # Choose those with indices within mat 
    b.good <- rowSums(z2 > 0)==2  &  z2[,1] <= nrow(mat)  &  z2[,2] <= ncol(mat)
    mat[z2[b.good,]]
}

marat = function(mat) {
    n.row = n.col = nrow(mat)
    addresses <- expand.grid(x = 1:n.row, y = 1:n.col)
    # Relative addresses
    z <- rbind(c(-1,0,1,-1,1,-1,0,1), c(-1,-1,-1,0,0,1,1,1))
    apply(addresses, 1,
          get.neighbors, z = z, mat = mat) # Returns a list with neighbors
}

u20650 = function(mat) {
    w <-  which(mat==mat, arr.ind=TRUE)
    d <- as.matrix(dist(w, "maximum", diag=TRUE, upper=TRUE))
    # extract neighbouring values for each element
    # extract where max distance is one
    a <- apply(d, 1, function(i) mat[i == 1] )
    names(a)  <- mat
    return(a)
}

More Related Contents:

  1. Matrix operation in R: I have a square matrix whose determinant is zero, i need to find its inverse in R programing. Is it possible ,if yes how? [closed]
  2. Loop through a R matrix row-wise and print elements [duplicate]
  3. Convert an upper to lower triangle matrix in r [duplicate]
  4. R memory management / cannot allocate vector of size n Mb
  5. Reshape three column data frame to matrix (“long” to “wide” format) [duplicate]
  6. Split a large dataframe into a list of data frames based on common value in column
  7. How to subset matrix to one column, maintain matrix data type, maintain row/column names?
  8. Multiply rows of matrix by vector?
  9. How to divide each row of a matrix by elements of a vector in R
  10. Subscript out of bounds – general definition and solution?
  11. How can I create a correlation matrix in R?
  12. Subset a matrix according to a columns vector
  13. Extract matrix column values by matrix column name
  14. Apply a function to every row of a matrix or a data frame
  15. Create dataframe from a matrix
  16. Get row and column indices of matches using `which()`
  17. Finding row index containing maximum value using R
  18. Function to split a matrix into sub-matrices in R
  19. R: Plotting a 3D surface from x, y, z
  20. Last Observation Carried Forward In a data frame? [duplicate]
  21. Directly creating dummy variable set in a sparse matrix in R
  22. Should I use a data.frame or a matrix?
  23. Find K nearest neighbors, starting from a distance matrix
  24. Select rows of a matrix that meet a condition
  25. R: How to rescale my matrix by column
  26. Calculate Euclidean distance matrix using a big.matrix object
  27. R reshape a vector into multiple columns
  28. fast large matrix multiplication in R
  29. How to calculate adjacency matrices in R
  30. What does the error “arguments imply differing number of rows: x, y” mean?

Leave a Comment