检查是否在图中完全连接了两个点

Question

i有一个矩阵和图（相同的结构）：

libary(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")

plot(g)
edgelist = dput(as_edgelist(g))
adj_matrix = get.adjacency(g)

对于此矩阵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

我想检查所有1是否可以到达所有其他1的情况下，而无需踏上2或3
• 我想检查所有2是否可以到达所有其他2
我想检查所有3是否可以到达所有其他3的情况下，而无需踩到1,2
• 我认为我知道如何使用igraph对图G进行此操作 - 我选择具有值1并制作子图的所有节点，然后检查此子图是否完全连接，并包含具有值2或3的节点。

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)

我如何对矩阵m进行相同的操作？

它不是有向图。因此，曾经与“ 1” S或“ 2” S等连接的任何数字始终与池中所有其他数字连接。这使检查非常容易。

m <- matrix(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
), nrow = 6, byrow = TRUE)

# the column and row names are the names or the nodes
# in this case, index and names are the same
colnames(m) <- 1:ncol(m)
rownames(m) <- 1:nrow(m)

Answer 1

is_connected <- function(mat, allowed_values=c(1)) {
  df <- as.data.frame(mat)
  matches <- lapply(allowed_values, function(val) df == val)
  if (length(matches) > 1) {
    any_matches <- Reduce(`|`, matches)
  } else {
    any_matches <- matches[[1]]
  }
  sort(union(colnames(df)[sapply(as.data.frame(any_matches), any)],
             rownames(df)[sapply(as.data.frame(t(any_matches)), any)]))
}

因此，所有通过边缘连接的值与值1连接的值是：

> is_connected(m, allowed_values=1) 
[1] "1" "2" "3" "4" "5" "6"

> is_connected(m, 2)
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, 3)
[1] "4" "5" "6"
> is_connected(m, c(2,3))
[1] "1" "3" "4" "5" "6"
> is_connected(m, c(1,2))
[1] "1" "2" "3" "4" "5" "6"
> is_connected(m, c(1,2,3))
[1] "1" "2" "3" "4" "5" "6"

因此，您可以看到所有6个节点均通过“ 1”或“ 2”连接。 但是“ 3”仅连接节点4、5、6.