Lấy các thành phần được kết nối trong R

Question

Tôi có ma trận với các giá trị 0 hoặc 1 và tôi muốn lấy danh sách các nhóm liền kề 1.

Ví dụ, ma trận

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 

nên trả lại 4 thành phần kết nối sau:

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

C2 = { (2,4)}

C3 = {(3,3)}

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

Có ai có ý tưởng về cách thực hiện nhanh trong R? Ma trận thực sự của tôi thực sự là khá lớn, như 2000x2000 (nhưng tôi mong rằng số lượng các thành phần được kết nối là hợp lý nhỏ, tức là 200).

Answer 1

Với bản cập nhật, bạn có thể biến ma trận nhị phân thành đối tượng raster và sử dụng chức năng clumps. Sau đó, nó chỉ là quản lý dữ liệu để trả lại định dạng chính xác mà bạn muốn. Ví dụ dưới đây:

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)) 
} 

Mà sau đó res in ra tại giao diện điều khiển:

> 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 

Tôi sẽ không ngạc nhiên nếu có một cách tốt hơn để đi từ đối tượng raster đến mục tiêu cuối cùng của bạn mặc dù. Một lần nữa một ma trận 2000 năm 2000 không phải là một việc lớn cho việc này.

---

Cũ (câu trả lời sai) nhưng nên có ích cho những người muốn thành phần kết nối của một đồ thị.

Bạn có thể sử dụng gói igraph để biến ma trận kề của bạn thành mạng và trả về các thành phần. Biểu đồ ví dụ của bạn là một thành phần, vì vậy tôi đã xóa một cạnh để minh họa.

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) 

Dòng cuối cùng sau đó trả về tại dấu nhắc:

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

$`2` 
[1] 3 

Kinh nghiệm của tôi với thuật toán này nó là khá nhanh - vì vậy tôi không nghĩ rằng 2.000 2.000 sẽ là một vấn đề.