Otimizando Funções para Gráficos de Rede

Nesta questão aqui ( Somando nós em uma rede ), aprendi como encontrar o quadrado dentro da rede original com a maior soma de nós.

Aqui estão os dados para esta pergunta:

library(igraph)

width <- 30
height <- 20
num_nodes <- width * height

# Create a grid
x <- rep(1:width, each = height)
y <- rep(1:height, times = width)

g <- make_empty_graph(n = num_nodes, directed = FALSE)

# Function to get node index
get_node_index <- function(i, j) (i - 1) * height + j

# Add edges
edges <- c()
for(i in 1:width) {
   for(j in 1:height) {
      current_node <- get_node_index(i, j)
    
      # Connect to right neighbor
      if(i < width) edges <- c(edges, current_node, get_node_index(i + 1, j))
    
      # Connect to bottom neighbor
      if(j < height) edges <- c(edges, current_node, get_node_index(i, j + 1))
   }
}

g <- add_edges(g, edges)

V(g)$x <- x
V(g)$y <- y

par(mfrow=c(1,2))

V(g)$name <- 1:num_nodes
plot(g, vertex.size = 7, vertex.label = V(g)$name, vertex.label.cex = 0.6, main = "Map with         Node Indices")

V(g)$value <- sample(1:100, num_nodes, replace = TRUE)
plot(g, vertex.size = 7, vertex.label = V(g)$value, vertex.label.cex = 0.6, main = "Map with     Population Values")

E aqui está a função:

sg <- subgraph_isomorphisms(make_ring(4), g)
lst <- unique(lapply(sg, \(x) sort(names(x))))
out <- do.call(
  rbind,
  lapply(
    lst,
    \(v) data.frame(
      node_id = toString(v),
      value = sum(V(induced_subgraph(g, v))$value)
    )
  )
)

Esta abordagem está atualmente usando uma abordagem de força bruta em que cada nó é verificado individualmente. Existe alguma maneira em R de reestruturar essa função para que ela seja executada em paralelo ou um tipo diferente de algoritmo de busca que possa varrer a rede com mais eficiência?

Eu tive duas ideias sobre isso:

1. Ideia 1:

   Reescrevendo a função para observar grades quadradas e tesselá-las na rede:

    efficient_sum_squares <- function(g, width, height) {
      results <- data.frame(node_id = character(), value = numeric())
   
      for (i in 1:(width - 1)) {
        for (j in 1:(height - 1)) {
          nodes <- c(
            get_node_index(i, j),
            get_node_index(i + 1, j),
            get_node_index(i, j + 1),
            get_node_index(i + 1, j + 1)
          )
   
          sum_value <- sum(V(g)$value[nodes])
   
          results <- rbind(results, data.frame(node_id = toString(nodes), value = sum_value))
        }
      }
   
      results
    }
   
    out_efficient <- efficient_sum_squares(g, width, height)
   

2. Ideia 2:

   Achei que as comparações poderiam ser feitas de forma vetorizada:

    vectorized_sum_squares <- function(g, width, height) {
      x_mat <- matrix(V(g)$x, nrow = height, ncol = width, byrow = FALSE)
      y_mat <- matrix(V(g)$y, nrow = height, ncol = width, byrow = FALSE)
      value_mat <- matrix(V(g)$value, nrow = height, ncol = width, byrow = FALSE)
   
      sums <- value_mat[1:(height-1), 1:(width-1)] + 
              value_mat[2:height, 1:(width-1)] + 
              value_mat[1:(height-1), 2:width] + 
              value_mat[2:height, 2:width]
   
      node_ids <- apply(which(sums == sums, arr.ind = TRUE), 1, function(idx) {
        i <- idx[1]
        j <- idx[2]
        toString(c(
          get_node_index(j, i),
          get_node_index(j + 1, i),
          get_node_index(j, i + 1),
          get_node_index(j + 1, i + 1)
        ))
      })
   
      data.frame(node_id = node_ids, value = as.vector(sums))
    }
   
    out_vectorized <- vectorized_sum_squares(g, width, height)
   

Existe alguma maneira melhor de trabalhar nesse problema?