Find size of maximum connected region in matrix

Question

So I have a matrix (n row by m column) and want to find the region with the most connected "1s". For example if I have the following matrix:

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

There are 2 regions of "1s" in the matrix.

1st region:

1 1
  1 1
    1

2nd region:

1

I would like to create an algorithm that will output the maximum = 5. I think this has something to do with Depth First Search but I only have base R and access to a few packages.

Answer 1

You could use SDMTools. First, we convert the matrix into raster, then we detect clumps (patches) of connected cells. Each clump gets a unique ID. NA and zero are used as background values. Finally, PatchStat provides statistics for each patch.

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

Sample data

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