我有这样的数据：
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相同，则这两个步骤是相关的。
我想找到所有相关的步骤并首先订购它们(作为第一步是源自一个数字的步骤，该步骤未记录为任何其他行的目的地，同样，步骤的顺序以目标结束这不是同时的原点(。
我可以想象我想获得的两个理想的结果：
- 列表，列表的每个元素存储相关的向量步骤。
- 每个行存储相关步骤和的数据表 数据表中的列数对应于 最长的步骤顺序。
在这种情况下，数据表看起来像：
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开始到达。
使用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)
输出：
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
可能的解决方案：
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