identificare gruppi di episodi legati a catena, che insieme

Question

prendere questa semplice cornice di dati di ID connessi:

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 

Ora voglio raggruppare tutti gli ID che collegano. Tramite "collegamento", intendo seguire la catena di collegamenti in modo che tutti gli identificativi di un gruppo siano etichettati insieme. Una specie di struttura ramificata. cioè:

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 

Ora ho più o meno conoscere la logica che vorrei, ma non so come avrei implementarlo con eleganza. Sto pensando a un uso ricorsivo di match o %in% per andare giù per ogni ramo, ma sono davvero stumped questa volta.

Il risultato finale sarei inseguendo è:

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

Il pacchetto Bioconductor RBGL (un'interfaccia R alla libreria grafico BOOST) contiene una funzione, connectedComp(), che identifica i componenti collegati in un grafico - proprio quello che stai volendo.

(Per utilizzare la funzione, è necessario prima installare il grafico e RBGL pacchetti, disponibili here e 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

Ecco una risposta alternativa che io stesso ho scoperto dopo la spingendo nella giusta direzione da parte di Josh. Questa risposta utilizza il pacchetto igraph. Per coloro che sono alla ricerca e venire attraverso questa risposta, il mio test set di dati è indicato come una "lista edge" o "lista di adiacenza" in teoria dei grafi (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

Senza usare pacchetti:

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