查找矩阵中最大连通区域的大小
Find size of maximum connected region in matrix
所以我有一个矩阵(n 行 x m 列)并且想找到具有最多连接“1”的区域。例如,如果我有以下矩阵:
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
矩阵中有 2 个“1”区域。
第一个区域:
1 1
1 1
1
第二个地区:
1
我想创建一个算法来输出最大值 = 5。我认为这与深度优先搜索有关,但我只有基础 R 并且可以访问几个包。
您可以使用 SDMTools
。首先,我们将矩阵转换为 raster
,然后我们检测 clump
s(块)连接的单元格。每个团块都有一个唯一的 ID。 NA 和零用作背景值。最后,PatchStat
提供每个补丁的统计数据。
library(raster)
library(SDMTools)
r <- raster(mat)
rc <- clump(r)
as.matrix(rc)
[,1] [,2] [,3] [,4] [,5]
[1,] NA 1 1 1 1
[2,] 1 NA NA 1 NA
[3,] 1 1 1 NA 1
[4,] NA NA NA NA NA
[5,] 2 2 NA NA NA
p <- PatchStat(rc)
max(p$n.cell)
[1] 10
示例数据
set.seed(2)
m <- 5
n <- 5
mat <- round(matrix(runif(m * n), m, n))
mat
[,1] [,2] [,3] [,4] [,5]
[1,] 0 1 1 1 1
[2,] 1 0 0 1 0
[3,] 1 1 1 0 1
[4,] 0 0 0 0 0
[5,] 1 1 0 0 0
我最终使用了 igraph
:
library(igraph)
data<-scan("stdin")
n<-data[1]
m<-data[2]
mat<-matrix(data[3:(n*m+2)],nrow=n,ncol=m,byrow=TRUE)
labels <- as.vector(mat)
rows <- (seq(length(labels)) - 1) %% nrow(mat)
cols <- ceiling(seq(length(labels)) / nrow(mat))
g <- graph.lattice(dim(mat), nei=2)
# Remove edges between elements of different types or that aren't diagonal
edgelist <- get.edgelist(g)
retain <- labels[edgelist[,1]] == labels[edgelist[,2]] &
abs(rows[edgelist[,1]] - rows[edgelist[,2]]) <= 1 &
abs(cols[edgelist[,1]] - cols[edgelist[,2]]) <= 1
g <- delete.edges(g, E(g)[!retain])
y<-clusters(g)$membership ### clustered matrix as vector
m<-as.vector(mat) ### original matrix
z<-y[m>0] ### ignore where original matrix is 0
cat(sort(table(z),decreasing=TRUE)[[1]])
所以我有一个矩阵(n 行 x m 列)并且想找到具有最多连接“1”的区域。例如,如果我有以下矩阵:
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
矩阵中有 2 个“1”区域。
第一个区域:
1 1
1 1
1
第二个地区:
1
我想创建一个算法来输出最大值 = 5。我认为这与深度优先搜索有关,但我只有基础 R 并且可以访问几个包。
您可以使用 SDMTools
。首先,我们将矩阵转换为 raster
,然后我们检测 clump
s(块)连接的单元格。每个团块都有一个唯一的 ID。 NA 和零用作背景值。最后,PatchStat
提供每个补丁的统计数据。
library(raster)
library(SDMTools)
r <- raster(mat)
rc <- clump(r)
as.matrix(rc)
[,1] [,2] [,3] [,4] [,5] [1,] NA 1 1 1 1 [2,] 1 NA NA 1 NA [3,] 1 1 1 NA 1 [4,] NA NA NA NA NA [5,] 2 2 NA NA NA
p <- PatchStat(rc)
max(p$n.cell)
[1] 10
示例数据
set.seed(2)
m <- 5
n <- 5
mat <- round(matrix(runif(m * n), m, n))
mat
[,1] [,2] [,3] [,4] [,5] [1,] 0 1 1 1 1 [2,] 1 0 0 1 0 [3,] 1 1 1 0 1 [4,] 0 0 0 0 0 [5,] 1 1 0 0 0
我最终使用了 igraph
:
library(igraph)
data<-scan("stdin")
n<-data[1]
m<-data[2]
mat<-matrix(data[3:(n*m+2)],nrow=n,ncol=m,byrow=TRUE)
labels <- as.vector(mat)
rows <- (seq(length(labels)) - 1) %% nrow(mat)
cols <- ceiling(seq(length(labels)) / nrow(mat))
g <- graph.lattice(dim(mat), nei=2)
# Remove edges between elements of different types or that aren't diagonal
edgelist <- get.edgelist(g)
retain <- labels[edgelist[,1]] == labels[edgelist[,2]] &
abs(rows[edgelist[,1]] - rows[edgelist[,2]]) <= 1 &
abs(cols[edgelist[,1]] - cols[edgelist[,2]]) <= 1
g <- delete.edges(g, E(g)[!retain])
y<-clusters(g)$membership ### clustered matrix as vector
m<-as.vector(mat) ### original matrix
z<-y[m>0] ### ignore where original matrix is 0
cat(sort(table(z),decreasing=TRUE)[[1]])