如何根据一组不等式约束对data.table进行排序？

Question

我有一组"x <y"不等式约束,我想基于这些排序data.table的行.

例如,

library(data.table)
set.seed(0)
ineqs <- unique(data.table(
  X = sample(letters, 10, replace = T),
  Rel = "<",
  Y = sample(letters, 10, replace = T)
))
ineqs
    X Rel Y
 1: x   < b
 2: g   < f
 3: j   < e
 4: o   < r
 5: x   < j
 6: f   < u
 7: x   < m
 8: y   < s
 9: r   < z
10: q   < j

所以,如果我从一个排序的字母表开始,

dt <- data.table(Foo = letters)
    Foo
 1:   a
 2:   b
 3:   c
---    
24:   x
25:   y
26:   z

如何调整行顺序以满足我的约束？此外,我确信我的约束是有效的(即没有任何约束相互矛盾).

Answer 1

library(igraph)
g = ineqs[, graph_from_edgelist(cbind(X,Y), directed=TRUE)]
o = names(topo_sort(g))

dt[, v := factor(Foo, levels = o, ordered=TRUE)]
dt[order(v)]


    Foo    v
 1:   x    x
 2:   g    g
 3:   o    o
 4:   y    y
 5:   q    q
 6:   b    b
 7:   m    m
 8:   f    f
 9:   r    r
10:   s    s
11:   j    j
12:   u    u
13:   z    z
14:   e    e
15:   a <NA>
16:   c <NA>
17:   d <NA>
18:   h <NA>
19:   i <NA>
20:   k <NA>
21:   l <NA>
22:   n <NA>
23:   p <NA>
24:   t <NA>
25:   v <NA>
26:   w <NA>
    Foo    v

所有未包含的术语ineqs都排序到最后.

如果您的关系图表有周期,您应该收到警告topo_sort.这告诉您某些术语的任务定义不明确ineqs.