последовательность событий в соответствии с таблицей соединений из двух столбцов - PullRequest
Новая
       38

последовательность событий в соответствии с таблицей соединений из двух столбцов

0 голосов
/ 12 октября 2018

У меня есть таблица, которая показывает связи между событиями: 

library(data.table)
df = data.table(p1 = c("x0", "x0", "x1", "x2", "x3"),
                p2 = c("x1", "x2", "x3", "x3", "x4"))

Вот иллюстрация:

enter image description here

СледующееСобытие может произойти, только если все предыдущие события уже произошли.Например, событие x3 может произойти только после x1 и x2 независимо от их последовательности.

Как преобразовать таблицу df в следующую (где все события отображаются в некотором допустимом порядке) в виде data.table: 

df_required = data.table(p = c("x0", "x1", "x2", "x3", "x4", 
                               "x0", "x1", "x2", "x3", "x4"),
                         sequence = c(1, 2, 3, 4, 5, 1, 3, 2, 4, 5),
                         group = c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2))

В требуемой таблице показаны две возможные группы соединений: x0-x1-x2-x3-x4 и x0-x2-x1-x3-x4.Есть два возможных способа, потому что два значения могут следовать сразу за x0: x1 или x2.Последовательность также написана над кружками на иллюстрации.

Ответы [ 2 ]

0 голосов
/ 12 октября 2018

Вы можете присвоить ранг каждому узлу (при условии, что у вас есть график, для которого это имеет смысл ) ... 

vdf = data.table(p = sort(unique(unlist(df[, c("p1", "p2")]))))

i = 0L
vdf[, r := 0L]
while (any(vdf[r == i, p] %in% df$p1)){
  vdf[r == i, r := r + !df[.(p), on=.(p1), p %in% setdiff(p1, p2)]]
  i = i + 1L
}

    p r
1: x0 0
2: x1 1
3: x2 1
4: x3 2
5: x4 3

Если есть уникальное первое событие, x0, тогда благодаря @Roland вот более простой способ: 

library(igraph)
vdf[, r := as.vector(distances(graph_from_data_frame(df), "x0"))]

Затем для каждого ранга, имеющего более одного узла, возьмите все перестановки (здесь, заимствуя из Генерация всех различных перестановоксписок в R ) ... 

wdf = vdf[, do.call(cbind, lapply(split(.I, r), function(x) as.data.table(
  gtools::permutations(length(x), length(x), x)
)))]

   0.V1 1.V1 1.V2 2.V1 3.V1
1:    1    2    3    4    5
2:    1    3    2    4    5

Значения в wdf являются номерами строк (см. ?.I) из vdf, поэтому ... 

mdf = melt(wdf[, g := .I], id = "g", value.name = "w")[order(g, variable)]
vdf[mdf$w, .(p, g = mdf$g, r)][, seq := rowid(g)][]

     p g r seq
 1: x0 1 0   1
 2: x1 1 1   2
 3: x2 1 1   3
 4: x3 1 2   4
 5: x4 1 3   5
 6: x0 2 0   1
 7: x2 2 1   2
 8: x1 2 1   3
 9: x3 2 2   4
10: x4 2 3   5

Итак, g - это «группа», упомянутая в ОП;r - ранг;seq - это последовательность внутри группы (полезна для явной сортировки таблицы).

Комментарий. Я бы остановился после присвоения атрибута rank / глубиныкаждый узел в vdf.Вся информация о возможных последовательностях событий находится здесь, но перечисление их (как в выходных данных OP) может быть очень дорогостоящим, с точки зрения вычислительного времени и пространства, и поэтому его следует по возможности избегать.

Число перестановок для событий x с одинаковым рангом равно factorial(length(x)), поэтому, например, если x имеет длину 10, возвращаемая матрица имеет размеры dim(gtools::permutations(10, 10)) = 3628800 x 10. Мой компьютер зависает при попытке вычислить его.

0 голосов
/ 12 октября 2018

Я просто публикую это, поскольку он выдает тот же вывод, что и совет Роланда:

(я удалю его, если он не имеет смысла)

data: 

library(data.table)
df = data.table(p1 = c("x0", "x0", "x1", "x2", "x3"),
                p2 = c("x1", "x2", "x3", "x3", "x4"))

код: 

restElements <- setdiff(df$p1, df$p2)
ans <-
    t(do.call(
        expand.grid, c(restElements, unique(split(df$p2,df$p1)))
        ))

group = rep(1:ncol(ans), each = nrow(ans))

p     = c( ans )

sequence = as.numeric(factor(p))

data.table(p, sequence, group)

результат: 

#    p sequence group
#1: x0        1     1
#2: x1        2     1
#3: x3        4     1
#4: x4        5     1
#5: x0        1     2
#6: x2        3     2
#7: x3        4     2
#8: x4        5     2

обратите внимание:

  • убедитесь, что при установке коэффициента:factor(p), вы получите правильный заказ.(по умолчанию уровни факторов просто отсортированы. Работает с этим примером, может не работать с другими.)

  • Вместо моего ans, вероятно, разумнее использовать метод igraph.

Таким образом, вы можете комбинировать:

заимствовано у @ Roland 

lvls <- levels(factor(c(df$p1, df$p2)))
library(igraph);
tmp <- lapply(all_shortest_paths(graph_from_data_frame(df), lvls[1], lvls[length(lvls)])$res, as.vector)
ans <- sapply(tmp, function(x) { lvls[x] })

Вы можете использовать это ans.Убедитесь, что вы позже используете: sequence = as.numeric(factor(p, lvls))

...