获取相邻值的连通组件

Question

获取相邻值的连通组件

12

我有一个数值为0或1的矩阵，我想获得一组相邻1的列表。定义相连的组时，每个1的水平和垂直相邻都将被考虑。

例如，矩阵如下：

mat = rbind(c(1,0,0,0,0),
            c(1,0,0,1,0),
            c(0,0,1,0,0),
            c(0,0,0,0,0),
            c(1,1,1,1,1))

> mat
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    0    0    0    0
[2,]    1    0    0    1    0
[3,]    0    0    1    0    0
[4,]    0    0    0    0    0
[5,]    1    1    1    1    1

应返回以下4个连通分量：

C1 = {(1,1);(2,1)}

C2 = {(2,4)}

C3 = {(3,3)}

C4 = {(5,1);(5,2);(5,3);(5,4);(5,5)}

有人知道如何在R中快速完成吗？我实际的矩阵确实非常大，例如2000x2000（但我希望连通分量的数量是相对较小的，即200个）。

- Instanton

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy W · Accepted Answer

你可以将二进制矩阵转换为光栅对象，并使用 raster::clumps 函数来“检测连接单元格的斑块（patches）。”每个斑块都有一个唯一的ID。然后只需要进行数据管理，以返回所需的确切格式。以下是示例：

library(igraph)
library(raster)

mat = rbind(c(1,0,0,0,0),
            c(1,0,0,1,0),
            c(0,0,1,0,0),
            c(0,0,0,0,0),
            c(1,1,1,1,1))
Rmat <- raster(mat)
Clumps <- as.matrix(clump(Rmat, directions=4))

#turn the clumps into a list
tot <- max(Clumps, na.rm=TRUE)
res <- vector("list",tot)
for (i in 1:tot){
  res[i] <- list(which(Clumps == i, arr.ind = TRUE))
}

然后 res 在控制台上打印出：

> res
[[1]]
     row col
[1,]   1   1
[2,]   2   1

[[2]]
     row col
[1,]   2   4

[[3]]
     row col
[1,]   3   3

[[4]]
     row col
[1,]   5   1
[2,]   5   2
[3,]   5   3
[4,]   5   4
[5,]   5   5

虽然我不确定从光栅对象到您的最终目标是否有更好的方法，但对于此操作来说，一个2000x2000矩阵不应该是什么大问题。

这个答案（旧的）虽然错误，但对于想要得到图形的连通组件的人应该还是有用的。

您可以使用igraph包将邻接矩阵转换为网络并返回组件。您的示例图形是一个组件，因此我删除了一条边进行说明。

library(igraph)
mat = rbind(c(1,0,0,0,0),
            c(1,0,0,1,0),
            c(0,0,1,0,0),
            c(0,0,0,0,0),
            c(1,1,1,1,1))
g  <- graph.adjacency(mat) %>% delete_edges("5|3")
plot(g)
clu <- components(g)
groups(clu)

最后一行代码将在提示符处返回：

> groups(clu)
$`1`
[1] 1 2 4 5

$`2`
[1] 3

我使用过这个算法，它非常快 - 因此我不认为 2,000 x 2,000 会是一个问题。