Establezca el orden de filas de R data.table encadenando 2 columnas

Estoy tratando de descubrir cómo ordenar una tabla de datos R basada en el encadenamiento de 2 columnas.

Aquí está mi muestra data.table.

dt <- data.table(id = c('A', 'A', 'A', 'A', 'A')
         , col1 = c(7521, 0, 7915, 5222, 5703)
         , col2 = c(7907, 5703, 8004, 7521, 5222))

   id col1 col2
1:  A 7521 7907
2:  A    0 5703
3:  A 7915 8004
4:  A 5222 7521
5:  A 5703 5222

Necesito el orden de la fila para comenzar con col1 = 0. El valor de col1 en la fila 2 debe ser igual al valor de col2 en la fila anterior, y así sucesivamente.

Además, generalmente siempre debe haber un valor coincidente que encadene el orden de las filas. Pero si no, debe seleccionar el valor más cercano (ver filas 4 y 5 a continuación).

El resultado que estoy buscando se muestra a continuación:

   id col1 col2
1:  A    0 5703
2:  A 5703 5222
3:  A 5222 7521
4:  A 7521 7907
5:  A 7915 8004

Creo que puedo escribir una función loca para hacer esto ... pero me pregunto si hay una solución elegante de data.table.

EDITAR
Actualicé la tabla para incluir una ID adicional con filas duplicadas y una columna fuente única:

dt <- data.table(id = c('A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B')
               , col1 = c(7521, 0, 7915, 5222, 5703, 1644, 1625, 0, 1625, 1625)
               , col2 = c(7907, 5703, 8004, 7521, 5222, 1625, 1625, 1644, 1625, 1505)
               , source = c('c', 'b', 'a', 'e', 'd', 'y', 'z', 'x', 'w', 'v'))

    id col1 col2 source
 1:  A 7521 7907      c
 2:  A    0 5703      b
 3:  A 7915 8004      a
 4:  A 5222 7521      e
 5:  A 5703 5222      d
 6:  B 1644 1625      y
 7:  B 1625 1625      z
 8:  B    0 1644      x
 9:  B 1625 1625      w
10:  B 1625 1505      v

Puede haber valores coincidentes dentro de una ID. Ver B, filas 7 y 9 arriba. Sin embargo, hay una fuente única para cada fila de donde provienen estos datos.

El resultado deseado sería:

    id col1 col2 source
 1:  A    0 5703      b
 2:  A 5703 5222      d
 3:  A 5222 7521      e
 4:  A 7521 7907      c
 5:  A 7915 8004      a
 6:  B    0 1644      x
 7:  B 1644 1625      y
 8:  B 1625 1625      w
 9:  B 1625 1625      z
10:  B 1625 1625      v

En la salida, las filas coincidentes, 8 y 9 podrían estar en cualquier orden.

¡Gracias!

Aquí hay otro enfoque que:

1. Reordena los datos que colocarán primero el valor 0.
2. Recorre el resto de los valores para devolver el índice de dónde col2coincide col1.

setorder(dt, col1)

neworder = seq_len(nrow(dt))
init = 1L
col1 = dt[['col1']]; col2 = dt[['col2']]

for (i in seq_along(neworder)[-1L]) {
  ind = match(col2[init], col1)
  if (is.na(ind)) break
  neworder[i] = init = ind
}

dt[neworder]

##       id  col1  col2
##   <char> <num> <num>
##1:      A     0  5703
##2:      A  5703  5222
##3:      A  5222  7521
##4:      A  7521  7907
##5:      A  7915  8004

Si lo está haciendo con la agrupación, puede ajustar el ciclo dentro de a dt[, .I[{...}, by = id]$V1para devolver los índices. O para que se vea mejor, podemos hacer una función.

recursive_order = function (x, y) {
  neworder = seq_len(length(x))
  init = 1L

  for (i in neworder[-1L]) {
    ind = match(y[init], x)
    if (is.na(ind)) break

    # Multiple matches which means all the maining matches are the same number
    if (ind == init) { 
      inds = which(x %in% y[init])
      l = length(inds)
      neworder[i:(i + l - 2L)] = inds[-1L]
      break
    }
    neworder[i] = init = ind
  }
  return(neworder)
}

dt <- data.table(id = c('A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B')
                 , col1 = c(7521, 0, 7915, 5222, 5703, 1644, 1625, 0, 1625, 1625)
                 , col2 = c(7907, 5703, 8004, 7521, 5222, 1625, 1625, 1644, 1625, 1505)
                 , source = c('c', 'b', 'a', 'e', 'd', 'y', 'z', 'x', 'w', 'v'))

setorder(dt, col1)
dt[dt[, .I[recursive_order(col1, col2)], by = id]$V1]

       id  col1  col2 source
    <char> <num> <num> <char>
 1:      A     0  5703      b
 2:      A  5703  5222      d
 3:      A  5222  7521      e
 4:      A  7521  7907      c
 5:      A  7915  8004      a
 6:      B     0  1644      x
 7:      B  1644  1625      y
 8:      B  1625  1625      z
 9:      B  1625  1625      w
10:      B  1625  1505      v

Aquí hay una opción igraphcon data.table:

#add id in front of cols to distinguishes them as vertices
cols <- paste0("col", 1L:2L)
dt[, (cols) := lapply(.SD, function(x) paste0(id, x)), .SDcols=cols]

#permutations of root nodes and leaf nodes
chains <- dt[, CJ(root=setdiff(col1, col2), leaf=setdiff(col2, col1)), id]

#find all paths from root nodes to leaf nodes
#note that igraph requires vertices to be of character type
library(igraph)
g <- graph_from_data_frame(dt[, .(col1, col2)])
l <- lapply(unlist(
  apply(chains, 1L, function(x) all_simple_paths(g, x[["root"]], x[["leaf"]])), 
  recursive=FALSE), names)
links <- data.table(g=rep(seq_along(l), lengths(l)), col1=unlist(l))

#look up edges
dt[links, on=.(col1), nomatch=0L]

salida:

    id  col1  col2 source g
 1:  A    A0 A5703      b 1
 2:  A A5703 A5222      d 1
 3:  A A5222 A7521      e 1
 4:  A A7521 A7907      c 1
 5:  A A7915 A8004      a 2
 6:  B    B0 B1644      x 3
 7:  B B1644 B1625      y 3
 8:  B B1625 B1625      z 3
 9:  B B1625 B1625      w 3
10:  B B1625 B1505      v 3

datos:

library(data.table)
dt <- data.table(id = c('A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B')
  , col1 = c(7521, 0, 7915, 5222, 5703, 1644, 1625, 0, 1625, 1625)
  , col2 = c(7907, 5703, 8004, 7521, 5222, 1625, 1625, 1644, 1625, 1505)
  , source = c('c', 'b', 'a', 'e', 'd', 'y', 'z', 'x', 'w', 'v'))