如何为图的随机连通子图分割函数添加节点占比约束？

问题背景 #

此前基于Stack Overflow回答实现了网格图的随机连通子图分割，现需添加约束：将图分割为7个随机连通子图，每个子图的节点数占总节点数的比例需在5%到25%之间。已实现符合比例要求的随机数值生成函数，需将该约束整合到原分割逻辑中。

修改后的完整代码 #

library(igraph)
library(data.table)

# 生成符合比例要求的子图节点数列表
generate_subgraph_sizes <- function(n_subgraphs = 7, total_nodes, min_pct = 5, max_pct = 25) {
  repeat {
    # 生成随机分割点并计算比例
    points <- sort(c(0, runif(n_subgraphs - 1), 1))
    pcts <- diff(points) * 100
    # 检查比例是否符合要求
    if (min(pcts) >= min_pct && max(pcts) <= max_pct) {
      # 转换为节点数并取整
      sizes <- round(pcts * total_nodes / 100)
      # 调整总和，确保等于总节点数（处理取整误差）
      size_diff <- total_nodes - sum(sizes)
      if (size_diff != 0) {
        # 随机选择子图调整节点数
        adjust_idx <- sample(1:n_subgraphs, abs(size_diff))
        sizes[adjust_idx] <- sizes[adjust_idx] + sign(size_diff)
      }
      return(sizes)
    }
  }
}

# 修改后的分割函数：按指定子图大小分割为连通子图
split_graph_by_sizes <- function(g, target_sizes) {
  n_subgraphs <- length(target_sizes)
  total_nodes <- vcount(g)
  used <- logical(total_nodes)
  groups <- integer(total_nodes)
  
  # 初始化每个子图的起始节点
  start_nodes <- sample(which(!used), n_subgraphs)
  used[start_nodes] <- TRUE
  groups[start_nodes] <- 1:n_subgraphs
  
  # 转换为无向边的数据表
  dt <- setDT(as_data_frame(g))
  dt <- rbindlist(list(dt, dt[, .(from = to, to = from)]))
  
  # 逐个生长每个子图到目标大小
  for (grp in 1:n_subgraphs) {
    current_size <- 1
    target_size <- target_sizes[grp]
    
    while (current_size < target_size) {
      # 找到当前子图节点的未使用邻居
      neighbors <- unique(dt[from %in% which(groups == grp) & !used[to], to])
      if (length(neighbors) == 0) {
        # 极端情况：无法继续生长，重新生成起始节点（避免死循环）
        used <- logical(total_nodes)
        start_nodes <- sample(which(!used), n_subgraphs)
        used[start_nodes] <- TRUE
        groups <- integer(total_nodes)
        groups[start_nodes] <- 1:n_subgraphs
        grp <- 0  # 重置循环，重新开始
        break
      }
      # 随机选择一个邻居加入子图
      new_node <- sample(neighbors, 1)
      used[new_node] <- TRUE
      groups[new_node] <- grp
      current_size <- current_size + 1
    }
  }
  
  # 整理结果为子图-节点列表
  result <- data.table(group = 1:n_subgraphs)
  result[, vertices := lapply(group, function(x) which(groups == x))]
  return(result)
}

# 批量绘制分割结果的函数
plot_multiple_subgraphs <- function(n_plots = 25, n_rows = 10, n_cols = 5, n_subgraphs = 7) {
  g <- make_lattice(dimvector = c(n_cols, n_rows))
  layout <- layout_on_grid(g, width = n_cols)
  total_nodes <- vcount(g)
  
  color_palette <- c("red", "blue", "green", "yellow", "purple", "orange", "cyan")
  
  par(mfrow = c(5, 5), mar = c(0.5, 0.5, 2, 0.5))
  
  for (i in 1:n_plots) {
    # 生成符合约束的子图大小
    subgraph_sizes <- generate_subgraph_sizes(n_subgraphs, total_nodes)
    # 分割图
    subgraphs <- split_graph_by_sizes(g, subgraph_sizes)
    
    node_colors <- rep("white", total_nodes)
    
    for (j in 1:nrow(subgraphs)) {
      nodes <- unlist(subgraphs$vertices[j])
      node_colors[nodes] <- color_palette[j]
    }
    
    plot(g, 
         layout = layout, 
         vertex.color = node_colors,
         vertex.label = NA,  
         vertex.size = 15,   
         edge.color = "gray",
         edge.width = 0.5,  
         main = paste("Partition", i, "\nSizes:", paste(subgraph_sizes, collapse = ", ")),  
         cex.main = 0.7)     
  }
}

# 运行批量绘图
set.seed(123)
plot_multiple_subgraphs()

关键改动说明 #

• 生成子图大小函数优化：generate_subgraph_sizes直接基于总节点数生成符合比例的整数节点数，同时调整取整误差，确保总和等于总节点数。
• 分割函数重写：split_graph_by_sizes不再按子图数量初始化后自由生长，而是逐个将每个子图从起始节点生长到指定目标大小，保证每个子图的节点数符合约束且连通。
• 异常处理：添加了极端情况下的重置逻辑，避免因局部无法生长导致的死循环。
• 批量绘图函数适配：调用新的大小生成函数和分割函数，在标题中显示每个子图的实际大小，方便验证约束是否生效。

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