identifizieren Gruppen von verknüpften Episoden, die zusammen ketten

Question

Nehmen Sie diese einfachen Datenrahmen verknüpft ids:

test <- data.frame(id1=c(10,10,1,1,24,8),id2=c(1,36,24,45,300,11)) 

> test 
    id1 id2 
1 10 1 
2 10 36 
3 1 24 
4 1 45 
5 24 300 
6 8 11 

ich jetzt zusammenfassen möchten alle IDs, welche Verbindung. Mit 'Link', ich meine, folgen Sie durch die Kette von Links, so dass alle IDs in einer Gruppe zusammen bezeichnet werden. Eine Art Verzweigungsstruktur. d. h .:

Group 1 
10 --> 1, 1 --> (24,45) 
        24 --> 300 
          300 --> NULL 
        45 --> NULL 
10 --> 36, 36 --> NULL, 
Final group members: 10,1,24,36,45,300 

Group 2 
8 --> 11 
     11 --> NULL 
Final group members: 8,11 

Jetzt weiß ich ungefähr die Logik, die ich möchte, aber weiß nicht, wie ich es elegant implementieren würde. Ich denke an eine rekursive Verwendung von match oder %in%, um jeden Zweig zu gehen, aber bin dieses Mal wirklich ratlos.

Das Endergebnis I jagen würde, ist:

result <- data.frame(group=c(1,1,1,1,1,1,2,2),id=c(10,1,24,36,45,300,8,11)) 

> result 
    group id 
1  1 10 
2  1 1 
3  1 24 
4  1 36 
5  1 45 
6  1 300 
7  2 8 
8  2 11 

Answer 1

Das Bioconductor Paket RBGL (eine R-Schnittstelle zur BOOST Graph Bibliothek) enthält mit einer Funktion, connectedComp(), welches die verbundenen Komponenten in einem identifiziert, Grafik - genau das, was Sie wollen.

(die Funktion nutzen zu können, müssen Sie zuerst die Graph und RBGL Pakete installieren müssen, verfügbar here und here.)

library(RBGL) 
test <- data.frame(id1=c(10,10,1,1,24,8),id2=c(1,36,24,45,300,11)) 

## Convert your 'from-to' data to a 'node and edge-list' representation 
## used by the 'graph' & 'RBGL' packages 
g <- ftM2graphNEL(as.matrix(test)) 

## Extract the connected components 
cc <- connectedComp(g) 

## Massage results into the format you're after 
ld <- lapply(seq_along(cc), 
      function(i) data.frame(group = names(cc)[i], id = cc[[i]])) 
do.call(rbind, ld) 
# group id 
# 1  1 10 
# 2  1 1 
# 3  1 24 
# 4  1 36 
# 5  1 45 
# 6  1 300 
# 7  2 8 
# 8  2 11 

Answer 2

Hier ist eine alternative Antwort, dass ich mich nach dem entdeckt von Josh in die richtige Richtung schubsen. Diese Antwort verwendet das igraph-Paket. Für diejenigen, die sich über diese Antwort, mein test Datensatz wird bezeichnet als „Kantenliste“ oder „Adjazenzliste“ in der Graphentheorie (http://en.wikipedia.org/wiki/Graph_theory)

library(igraph) 
test <- data.frame(id1=c(10,10,1,1,24,8),id2=c(1,36,24,45,300,11)) 
gr.test <- graph.data.frame(test) 
links <- data.frame(id=unique(unlist(test)),group=clusters(gr.test)$membership) 
links[order(links$group),] 

# id group 
#1 10  1 
#2 1  1 
#3 24  1 
#5 36  1 
#6 45  1 
#7 300  1 
#4 8  2 
#8 11  2 

Answer 3

Ohne die Verwendung von Paketen suchen und kommen:

# 2 sets of test data 
mytest <- data.frame(id1=c(10,10,3,1,1,24,8,11,32,11,45),id2=c(1,36,50,24,45,300,11,8,32,12,49)) 
test <- data.frame(id1=c(10,10,1,1,24,8),id2=c(1,36,24,45,300,11)) 

grouppairs <- function(df){ 

    # from wide to long format; assumes df is 2 columns of related id's 
    test <- data.frame(group = 1:nrow(df),val = unlist(df)) 

    # keep moving to next pair until all same values have same group 
    i <- 0 
    while(any(duplicated(unique(test)$val))){ 
    i <- i+1 

    # get group of matching values 
    matches <- test[test$val == test$val[i],'group'] 

    # change all groups with matching values to same group 
    test[test$group %in% matches,'group'] <- test$group[i] 
    } 

    # renumber starting from 1 and show only unique values in group order 
    test$group <- match(test$group, sort(unique(test$group))) 
    unique(test)[order(unique(test)$group), ] 
} 

# test 
grouppairs(test) 
grouppairs(mytest)