代码之家  ›  专栏  ›  技术社区  ›  Tony Hellmuth

求矩阵中最大连通区域的大小

  •  3
  • Tony Hellmuth  · 技术社区  · 7 年前

    所以我有一个矩阵(n行x m列),我想找到连通度最大的“1s”区域。例如,如果我有以下矩阵:

    1 1 0 0
    0 1 1 0
    0 0 1 0
    1 0 0 0
    

    矩阵中有两个“1”区域。

    第一区域:

    1 1
      1 1
        1
    

    第二地区:

    1
    

    我想创建一个将输出最大值=5的算法。我认为这与深度优先搜索有关,但我只有base R和访问几个包的权限。

    2 回复  |  直到 7 年前
        1
  •  3
  •   DJack    7 年前

    你可以使用 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
    
        2
  •  2
  •   Tony Hellmuth    7 年前

    我最终使用 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]])