Create adjacency matrix from a path given as a vector of nodes in base R-CodePudding

Is there a compact and elegant way to create an adjacency matrix given a vector of the form shown (see code excerpt) in base R?

I give my best attempt below. Ideally, I would like to create the already-populated adjacency matrix in a single step as opposed to having to create the matrix data structure then fill it.

p <- 25 # Cardinality of vertex set; Number of nodes
  
hypothesis_path <- c(17, 7, 6, 1) # path in this form

path_to_D <- function(hypothesis_path, p) {
  path_len <- length(hypothesis_path) - 1
  idx_path <- t(sapply(1:path_len, function(i) hypothesis_path[i:(i 1)]))
  D <- matrix(0, p, p); D[idx_path] <- 1
  D
}

D <- path_to_D(hypothesis_path, p)

which(D == 1, arr.ind = TRUE)

# Desired indices of adjacency matrix are populated (with ones)
#      row col
# [1,]   6   1
# [2,]   7   6
# [3,]  17   7

Acceptable answers will avoid use of igraph or similar and will use the path vector in the form given. That said, advice and alternatives are of course always welcomed and appreciated.

CodePudding user response：

You can use the powerful but little-known trick of matrix-based indexing:

index_mat <- rbind(
               c(1, 2),
               c(2, 3), 
               c(3, 1)
             )

mat <- matrix(FALSE, 3, 3)
mat[index_mat] <- TRUE
mat
      [,1]  [,2]  [,3]
[1,] FALSE  TRUE FALSE
[2,] FALSE FALSE  TRUE
[3,]  TRUE FALSE FALSE

So do this:

path_to_D <- function (path, p) {
  indices <- cbind(path[-length(path)], path[-1])
  D <- matrix(0, p, p)
  D[indices] <- 1
  D
}

D <- path_to_D(hypothesis_path, 25)
which(D == 1, arr.ind=TRUE)

     row col
[1,]   6   1
[2,]   7   6
[3,]  17   7

CodePudding user response：

You can use a sparse matrix from the Matrix package. It is not base R but a very common package.

library(Matrix)

hypothesis_path <- c(17, 7, 6, 1)

D <- sparseMatrix(i = hypothesis_path[-length(hypothesis_path)],
                  j = hypothesis_path[-1])

which(D == 1, arr.ind = TRUE)
     row col
[1,]   6   1
[2,]   7   6
[3,]  17   7