Получение подключенных компонентов в R

Question

У меня есть матрица со значениями 0 или 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 подключенные компоненты:

С1 = {(1,1), (2,1)}

C2 = { (2,4)}

С3 = {(3,3)}

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

Есть ли у кого-нибудь идеи, как быстро это сделать в R? Моя реальная матрица действительно довольно большая, например 2000x2000 (но я ожидаю, что количество подключенных компонентов будет достаточно небольшим, т. Е. 200).

Answer 1

С обновлением вы можете превратить вашу двоичную матрицу в растровый объект и использовать функцию clumps. Тогда просто управление данными вернет точный формат, который вы хотите. Пример ниже:

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:max(Clumps, na.rm=TRUE)){ 
    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 

Я не удивлюсь, если есть лучший способ, чтобы перейти от растрового объекта к вашей конечной цели, хотя. Снова матрица 2000 по 2000 год не должна быть большой проблемой для этого.

---

Старых (неправильный ответ), но должно быть полезны для людей, которые хотят компонентов связности графа.

Вы можете использовать пакет 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 

Мой опыт работы с этим алгоритмом он довольно быстро - так что я не думаю, что 2000 на 2000 будет проблемой.