如何检查图与矩阵中同值元素的无阻碍完全连通性？

我们需要对结构一致的矩阵m和igraph图g完成三类连通性检查：

• 所有值为1的元素，不经过值为2、3的元素实现互相连通；
• 所有值为2的元素，不经过值为1、3的元素实现互相连通；
• 所有值为3的元素，不经过值为1、2的元素实现互相连通。

初始版连通性检查代码 #

该版本仅返回指定值的节点是否连通：

library(igraph)

check_connectivity_igraph <- function(g, value) {
    value_vertices <- which(V(g)$value == value)
    if (length(value_vertices) < 2) {
        return(TRUE)
    }
    subgraph <- induced_subgraph(g, value_vertices)
    is_connected <- components(subgraph)$no == 1
    return(is_connected)
}

result_1 <- check_connectivity_igraph(g, 1)
result_2 <- check_connectivity_igraph(g, 2)
result_3 <- check_connectivity_igraph(g, 3)

更新版连通性检查代码 #

该版本返回更详细的结果，包括是否连通、违规节点数量及具体节点：

check_all_connectivity <- function(g) {
  values_to_check <- c(1, 2, 3)
  results <- list()
  
  for (value in values_to_check) {
    same_value_vertices <- which(V(g)$value == value)
    result_for_value <- list()
    
    if (length(same_value_vertices) < 2) {
      result_for_value$connected <- TRUE
      result_for_value$violation_count <- 0
      result_for_value$violating_nodes <- integer(0)
      results[[paste0("value_", value)]] <- result_for_value
      next
    }
    
    other_value_vertices <- which(V(g)$value != value)
    
    if (length(other_value_vertices) > 0) {
      subgraph <- delete_vertices(g, other_value_vertices)
    } else {
      subgraph <- g
    }
    
    comp <- components(subgraph)
    is_connected <- comp$no == 1
    
    result_for_value$connected <- is_connected
    
    if (!is_connected) {
      component_sizes <- table(comp$membership)
      largest_component <- as.numeric(names(component_sizes)[which.max(component_sizes)])
      isolated_nodes <- which(comp$membership != largest_component)
      
      violating_nodes <- same_value_vertices[isolated_nodes]
      
      result_for_value$violation_count <- length(violating_nodes)
      result_for_value$violating_nodes <- violating_nodes
    } else {
      result_for_value$violation_count <- 0
      result_for_value$violating_nodes <- integer(0)
    }
    
    results[[paste0("value_", value)]] <- result_for_value
  }
  
  return(results)
}

check_all_connectivity(upgrade_graph(g))

需验证以下矩阵检查代码是否符合上述连通性逻辑：

check_connectivity_matrix <- function(m, value) {
  mask <- m == value
  if (sum(mask) < 2) {
    return(0)
  }
  
  visited <- matrix(FALSE, nrow = nrow(m), ncol = ncol(m))
  coords <- which(mask, arr.ind = TRUE)
  start_cell <- coords[1, ]
  
  flood_fill <- function(i, j) {
    if (i < 1 || i > nrow(m) || j < 1 || j > ncol(m) || 
        visited[i, j] || m[i, j] != value) {
      return()
    }
    
    visited[i, j] <<- TRUE
    
    flood_fill(i-1, j)
    flood_fill(i, j+1)
    flood_fill(i+1, j)
    flood_fill(i, j-1)
  }
  
  flood_fill(start_cell[1], start_cell[2])
  
  violations <- sum(mask & !visited)
  return(violations)
}

count_total_violations <- function(m) {
  unique_values <- unique(as.vector(m))
  total_violations <- 0
  
  for (val in unique_values) {
    violations <- check_connectivity_matrix(m, val)
    total_violations <- total_violations + violations
  }
  
  return(total_violations)
}

total_violations <- count_total_violations(m)
print(total_violations)

矩阵m的结构 #

[,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    1    1    1    1    2
[2,]    1    1    1    1    2    2
[3,]    1    1    1    2    2    2
[4,]    1    1    1    2    3    2
[5,]    1    1    1    1    3    3
[6,]    1    1    1    1    3    3

定义代码 #

library(igraph)

m = structure(c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 2, 2, 3, 3), dim = c(6L, 
6L))

g = structure(list(36, FALSE, c(1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 
14, 15, 16, 17, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 
33, 34, 35, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35
), c(0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 
20, 21, 22, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 0, 1, 2, 
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
20, 21, 22, 23, 24, 25, 26, 27, 28, 29), NULL, NULL, NULL, NULL, 
    list(c(1, 0, 1), structure(list(), names = character(0)), 
        list(name = c("1", "2", "3", "4", "5", "6", "7", "8", 
        "9", "10", "11", "12", "13", "14", "15", "16", "17", 
        "18", "19", "20", "21", "22", "23", "24", "25", "26", 
        "27", "28", "29", "30", "31", "32", "33", "34", "35", 
        "36"), value = c(1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 
        1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3, 
        1, 1, 1, 1, 3, 3), color = structure(c(1L, 1L, 1L, 1L, 
        1L, 2L, 1L, 1L, 1L, 1L, 2L, 2L, 1L, 1L, 1L, 2L, 2L, 2L, 
        1L, 1L, 1L, 2L, 3L, 2L, 1L, 1L, 1L, 1L, 3L, 3L, 1L, 1L, 
        1L, 1L, 3L, 3L), levels = c("1", "2", "3"), class = "factor"), 
            label = c(1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 
            1, 1, 2, 2, 2, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 3, 3, 
            1, 1, 1, 1, 3, 3)), structure(list(), names = character(0)))), class = "igraph")
g = upgrade_graph(g)
plot(g)
edgelist = dput(as_edgelist(g))
adj_matrix = get.adjacency(g)

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