优化网络图函数：高效寻找网格中节点和最大的正方形

基于R的igraph包构建的网格网络如下：

library(igraph)

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

# 创建网格
x <- rep(1:width, each = height)
y <- rep(1:height, times = width)

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

# 获取节点索引的函数
get_node_index <- function(i, j) (i - 1) * height + j

# 添加边
edges <- c()
for(i in 1:width) {
   for(j in 1:height) {
      current_node <- get_node_index(i, j)
    
      # 连接右侧邻居
      if(i < width) edges <- c(edges, current_node, get_node_index(i + 1, j))
    
      # 连接下方邻居
      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 = "带节点索引的网格图")

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 = "带节点值的网格图")

最初采用暴力遍历方式逐个检查节点，实现代码如下：

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)
    )
  )
)

该方法效率较低，现探讨在R中是否可重构函数实现并行运行，或采用更高效的搜索算法扫描网络。

思路一：遍历网格划分正方形 #

通过直接遍历网格中所有可能的2x2正方形区域，计算对应节点的和：

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)

思路二：向量化计算 #

将节点值转换为矩阵，通过矩阵切片的向量化操作直接计算所有2x2区域的和：

vectorized_sum_squares <- function(g, width, height) {
   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)

是否存在更优的解决方案？

内容的提问来源于stack exchange，提问作者farrow90