在R中获取连接的组件 [英] Obtaining connected components in R

问题描述

我有一个值为0或1的矩阵，我想获得一个相邻的1的组的列表.

I have a matrix with values 0 or 1 and I would like to obtain a list of groups of adjacent 1's.

例如矩阵

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个连接的组件:

should return the following 4 connected components:

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

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

C2 = {(2,4)}

C2 = {(2,4)}

C3 = {(3,3)}

C3 = {(3,3)}

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

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

有人知道如何在R中快速实现吗?我的真实矩阵确实相当大，例如2000x2000(但我希望连接的组件数量相当少，即200).

Does anybody has an idea of how to do it fast in R? My real matrix is indeed rather large, like 2000x2000 (but I expect that the number of connected components to be reasonably small, i.e. 200).

推荐答案

通过更新，您可以将二进制矩阵转换为栅格对象，并使用 clumps 函数.然后，仅是数据管理即可返回所需的确切格式.下面的示例:

With the update, you can turn your binary matrix into a raster object and use the clumps function. Then it is just data management to return the exact format you want. Example below:

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:

Which then res prints out at the console:

> 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

但是，如果有更好的方法从栅格对象到最终目标，我也不会感到惊讶.再次，2000年到2000年的矩阵对此并不重要.

I wouldn't be surprised if there is a better way to go from the raster object to your end goal though. Again a 2000 by 2000 matrix should not be a big deal for this.

旧的(错误的答案)，但对于想要图的连接组件的人应该有用.

Old (wrong answer) but should be useful for people who want connected components of a graph.

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

You can use the igraph package to turn your adjacency matrix into a network and return the components. Your example graph is one component, so I removed one edge for illustration.

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)

然后在提示处返回最后一行:

The final line then returns at the prompt:

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

$`2`
[1] 3

我使用这种算法的经验非常快-因此我认为2,000 x 2,000不会有问题.

My experience with this algorithm it is pretty fast - so I don't think 2,000 by 2,000 will be a problem.

这篇关于在R中获取连接的组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！