如何匹配由 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相同，则这两个步骤是相关的。

我想找到所有相关步骤并将它们从头到尾排序（因为第一步是起源于一个数字的数字，该数字未记录为任何其他行的目的地，类似地，步骤序列以目的地不同时也是起点）。

我可以想象我想要获得的两个理想结果：

一个列表，其中列表的每个元素存储相关的向量步骤。
一个数据 table 其中每一行存储相关的步骤和数据中的列数 table 对应于数据的长度最长的步骤序列。

本例中的数据 table 如下所示：

   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

现在我想要一种动态识别结果 table 应该有多少列的方法，但实际上我知道不会超过 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

可能的解决方案：

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

Answer 2

另一种可能性是使用igraph构建集群然后data.table::dcast得到想要的宽数据table:

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>

edit：解决 qn edit 和评论，仍然使用 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 
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)

输出：

   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

如何匹配由 data.table 的两列指示的链接步骤

How to match linked steps indicated by two columns of a data.table

r

reshape2

data.table