Erhalten von verbundenen Komponenten in R

Question

Ich habe eine Matrix mit Werten 0 oder 1, und ich möchte eine Liste der Gruppen von benachbarten 1 erhalten.

Zum Beispiel kann die Matrix

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 

sollten die folgenden 4 verbundenen Komponenten zurück:

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

C2 = { (2,4)}

C3 = {(3,3)}

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

Hat jemand eine Idee, wie man es schnell in R macht? Meine reale Matrix ist tatsächlich ziemlich groß, wie 2000x2000 (aber ich erwarte, dass die Anzahl der verbundenen Komponenten ziemlich klein ist, d. H. 200).

Answer 1

Mit dem Update können Sie Ihre binäre Matrix in ein Rasterobjekt umwandeln und die Klumpen Funktion verwenden. Dann ist es nur Datenverwaltung, um das genaue Format zurückzugeben, das Sie wünschen. Beispiel unten:

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

die dann res Drucke an der Konsole aus:

> 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 

Ich wäre nicht überrascht, wenn es eine bessere Art und Weise aus dem Raster-Objekt zu Ihrem Endziel obwohl zu gehen. Wiederum sollte eine Matrix von 2000 nach 2000 keine große Sache sein.

---

Alt (falsche Antwort), sollte aber für Leute, die wollen verbundenen Komponenten eines Graphen nützlich sein.

Mit dem Paket "igraph" können Sie Ihre Adjazenzmatrix in ein Netzwerk umwandeln und die Komponenten zurückgeben. Ihr Beispielgraph ist eine Komponente, also habe ich eine Kante zur Veranschaulichung entfernt.

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) 

Die letzte Zeile kehrt dann an der Eingabeaufforderung:

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

$`2` 
[1] 3 

Meine Erfahrung mit diesem Algorithmus ist es ziemlich schnell ist - so glaube ich nicht 2000 von 2000 wird ein Problem sein.