Как сопоставить связанные шаги, указанные двумя столбцами таблицы data.table

Question

У меня есть такие данные:

structure(list(step_origin = c(4897L, 3105L, 129L, 2689L, 2945L, 
161L), step_destination = c(3105L, 1057L, 2689L, 2945L, 3201L, 
673L)), row.names = c(NA, -6L), class = c("data.table", "data.frame"
), .internal.selfref = <pointer: 0x000001a52ad81ef0>)

в удобной для человека форме это выглядит так:

   step_origin step_destination
1:        4897             3105
2:        3105             1057
3:         129             2689
4:        2689             2945
5:        2945             3201
6:         161              673

каждая строка представляет шаг в каком-то процессе, первый столбец указывает источникшага, а второй столбец указывает, где заканчивается шаг.

Если step_destination в одной строке совпадает с step_origin другой строки, то эти два шага связаны.

Я хочу найти все связанные шаги и упорядочить их от первого до последнего (поскольку первый шаг - это тот, который начинается с номера, который не записан как пункт назначения в любой другой строке, аналогично последовательность шагов заканчивается пунктом назначения, которыйне одновременно и источник).

Я могу представить два желаемых результата, которые я хотел бы получить:

1. список, где каждый элемент списка хранит вектор соответствующегошаги.
2. таблица данных, где каждая строка хранит связанные шаги, а количество столбцов в таблице данных соответствует длине самой длинной последовательности шагов.

Данныетаблица в этом случае будет выглядеть следующим образом:

   sequence_id step_1 step_2 step_3 step_4
1:           1    129   2689   2945   3201
2:           2    161    673     NA     NA
3:           3   4897   3105   1057     NA

Теперь я хотел бы, чтобы метод динамически определял, сколько столбцов должна иметь результирующая таблица, но на практике я знаю, что будет не более 12 последовательных шагов..

РЕДАКТИРОВАТЬ:

первоначальный вопрос уже был дан ответ, однако мой реальный сценарий оказывается немного сложнее, чем я первоначально ожидал.

Процесс, описанный выше, может фактически перемещаться из одного источника в два разных пункта назначения.

Пример данных:

structure(list(step_origin = c(3105, 2689, 2689, 1610), step_destination = c(2689, 
2945, 3201, 6730), time = c("2019-03-27 13:24:07", "2019-03-27 20:46:58", 
"2019-03-28 16:02:57", "2019-03-28 16:12:44")), row.names = c(NA, 
-4L), class = c("data.table", "data.frame"), .internal.selfref = <pointer: 0x000001a52ad81ef0>)

, который выглядит как:

   step_origin step_destination                time
1:        3105             2689 2019-03-27 13:24:07
2:        2689             2945 2019-03-27 20:46:58
3:        2689             3201 2019-03-28 16:02:57
4:        1610             6730 2019-03-28 16:12:44

Что в основном означает, что с 2689 процесс разделяется на 2945 и 3201.Обратите внимание, что один пункт назначения всегда достигается только от одного источника, но один источник может иметь несколько пунктов назначения.

Я могу добраться до:

   sequence_id step_1 step_2 step_3
1:           1   3105   2689   2945
2:           2   2689   3201     NA
3:           3   1610   6730     NA

Используя уже предложенные подходы, однако в этомВ этом случае я хотел бы иметь

   sequence_id step_1 step_2 step_3
1:           1   3105   2689   2945
2:           2   3105   2689   3201
3:           3   1610   6730     NA

, что указывало бы на то, что пункты назначения 2945 и 3201 были достигнуты с начала в 3105.

Answer 1

Еще одна возможность использования igraph для построения кластеров, а затем data.table::dcast для получения желаемой таблицы широких данных:

library(igraph)
g <- graph_from_data_frame(DF)
seqid <- clusters(g)$membership
dcast(as.data.table(seqid, keep.rownames=TRUE),
    seqid ~ rowid(seqid), 
    value.var="rn")

вывод:

   seqid    1    2    3    4
1:     1 4897 3105 1057 <NA>
2:     2  129 2689 2945 3201
3:     3  161  673 <NA> <NA>

---

редактировать: вадрес qn отредактируйте и прокомментируйте, все еще используя igraph, но находя все возможные пути вместо кластеризации сейчас.

library(igraph)
library(data.table)
DF2 <- structure(list(step_origin = c(3105, 2689, 2689, 1610), step_destination = c(2689,
    2945, 3201, 6730), time = c("2019-03-27 13:24:07", "2019-03-27 20:46:58",
        "2019-03-28 16:02:57", "2019-03-28 16:12:44")), row.names = c(NA,
            -4L), class = c("data.table", "data.frame"))
DF2 <- rbindlist(list(DF2, DF2), idcol="ID")

gDT <- DF2[, .(graph=.(graph_from_data_frame(.SD))), by=.(ID), 
    .SDcols=c("step_origin", "step_destination")]

#create all combinations of roots and leaf nodes
rootleaf <- DF2[, CJ(setdiff(step_origin, step_destination),
        setdiff(step_destination, step_origin)), 
    by=.(ID)][, 
        c("V1", "V2") := lapply(.SD, as.character), .SDcols=c("V1", "V2")]

#get all paths from roots to leaf nodes
#see https://stackoverflow.com/a/25758769/1989480
paths <- rootleaf[, {
        id <- .BY$ID
        g <- gDT[ID==id, graph][[1L]]

        .(.SD[, .(lapply(all_shortest_paths(g, from=V1, to=V2)$res,
                function(sp) transpose(as.data.table(c(id, V(g)[sp]$name))))),
            by=seq_len(.SD[,.N])]$V1)
    },
    by=.(ID)]

#get desired wide output
rbindlist(paths$V1, use.names=TRUE, fill=TRUE)

output:

   V1   V2   V3   V4
1:  1 1610 6730 <NA>
2:  1 3105 2689 2945
3:  1 3105 2689 3201
4:  2 1610 6730 <NA>
5:  2 3105 2689 2945
6:  2 3105 2689 3201

Answer 2

Возможное решение:

DT[, .(step = c(step_origin, step_destination[.N]))
   , by = .(sequence_id = DT[, cumsum(c(TRUE, step_origin[-1] != step_destination[-.N]))])
   ][, dcast(.SD, sequence_id ~ rowid(sequence_id, prefix = "step_"), value.var = "step")
     ][order(step_1)][, sequence_id := .I][]

, что дает:

   sequence_id step_1 step_2 step_3 step_4
1:           1    129   2689   2945   3201
2:           2    161    673     NA     NA
3:           3   4897   3105   1057     NA