identificar grupos de episodios enlazadas que encadenar

Question

Tome esta trama de datos sencilla de identificadores vinculados:

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 

ahora quiero agrupar todos los identificadores que unen. Por 'enlace', me refiero a seguir a través de la cadena de enlaces para que todos los identificadores en un grupo estén etiquetados juntos. Una especie de estructura de ramificación. es decir:

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 

Ahora más o menos conocer la lógica que me gustaría, pero no saben cómo iba a ponerlo en práctica con elegancia. Estoy pensando en un uso recursivo de match o %in% para bajar cada rama, pero estoy realmente perplejo esta vez.

El resultado final estaría persiguiendo es:

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

El paquete Bioconductor RBGL (una interfaz R a la biblioteca gráfica BOOST) contiene una función, connectedComp(), que identifica los componentes conectados en una gráfico - justo lo que está buscando.

(Para utilizar la función, primero tendrá que instalar el gráfico y RBGL paquetes, disponibles here y 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

Aquí está una respuesta alternativa que he descubierto a mí mismo después de la empujando en la dirección correcta por Josh. Esta respuesta usa el paquete igraph. Para aquellos que están buscando y nos hemos encontrado esta respuesta, mi test conjunto de datos se conoce como una "lista de aristas" o "lista de adyacencia" en la teoría de grafos (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

Sin el uso de paquetes:

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