Условно создать фрейм данных, свернуть столбец, урезать реальный фрейм данных.

Question

У меня есть такой кадр данных:

+------+----+----------+----------+
| from | to | priority | distance |
+------+----+----------+----------+
|    1 |  3 |        1 |       10 |
|    1 |  5 |        1 |       10 |
|    2 |  7 |        1 |       10 |
|    3 |  9 |        1 |       15 |
|    4 |  8 |        2 |       20 |
|    5 |  6 |        2 |       20 |
|    5 |  1 |        2 |       30 |
|    6 |  2 |        2 |       30 |
|    6 |  4 |        3 |       40 |
|    7 |  2 |        3 |       40 |
|    8 |  3 |        3 |       50 |
|    9 |  5 |        3 |       60 |
|   10 |    |        3 |          |
|   12 | 11 |        7 |        9 |
+------+----+----------+----------+

Он отсортирован по приоритету и расстоянию

Я хочу свернуть столбец to на основе следующих критериев:

1. Каждое уникальное значение в to будет сгруппировано с соответствующим from (пример строки 1 в таблице ниже)

   +--------------+----------+
   | from_parent  | to_child |
   +--------------+----------+
   |            1 |      3,5 |
   +--------------+----------+
   

   Если значение уже сгруппировано в to_child (в нашем случае число 3), и если оно также появляется в from основной таблицы и если его соответствующее to является новым значением, значение, которое никогда не появлялось в from_parent или to_child, тогда это значение должно появиться независимо в from_parent. Например, из нашей таблицы,

   +------+----+----------+----------+
   | from | to | priority | distance |
   +------+----+----------+----------+
   |    3 |  9 |        1 |       15 |
   +------+----+----------+----------+
   

   значение 9 должно появиться независимо в новой таблице, как показано ниже:

   +--------------+----------+
   | from_parent  | to_child |
   +--------------+----------+
   |            9 |          |
   +--------------+----------+
   

, но если значение 9 позднее появится в столбце to, его следует добавить в кластер to_child, а предыдущее значение следует удалить, поэтому я имею в виду, что если 9 появился как to для from из 1 позже, соответствующее значение to_child, равное 1, должно быть 3,5,9

, поэтому итоговая таблица должна быть такой же, как в

+--------------+----------+
| from_parent  | to_child |
+--------------+----------+
|            1 |      3,5 |
|            2 |        7 |
|            4 |        8 |
|            6 |          |
|            9 |          |
|           10 |          |
|           12 |       11 |
+--------------+----------+

Answer 1

Я буду использовать пакет igraph для решения рассматриваемой проблемы, поскольку это проблема теории графов.

Сначала создайте график из первых двух столбцов входного фрейма data.frame.

library(igraph)

g <- graph_from_data_frame(df1[1:2], directed = TRUE)
plot(g, edge.curved = TRUE, edge.arrow.size = 0.5)

Теперь получите пути из каждой вершины в df1$from. Пути получаются с помощью поиска в ширину, функция bfs.

paths_list <- vector("list", length = length(V(g)))
i <- 0L
for(v in V(g)){
  i <- i + 1L
  ord <- bfs(g, root = v, neimode = "out",
             unreachable = FALSE, dist = TRUE)$dist
  ord <- ord[is.finite(ord)]
  paths_list[[i]] <- ord
}

from <- lapply(paths_list, function(x) names(x)[1])
to <- lapply(paths_list, function(x) paste(names(x)[x != 0], collapse = ","))
res <- data.frame(from = unlist(from), to = unlist(to), stringsAsFactors = FALSE)
res <- res[nchar(res$from) != 0, ]

res
#   from              to
#1     1 3,5,6,9,2,4,7,8
#2     2               7
#3     3 9,5,1,6,2,4,7,8
#4     4 8,3,9,5,1,6,2,7
#5     5 1,6,2,3,4,7,8,9
#6     6 2,4,7,8,3,9,5,1
#7     7               2
#8     8 3,9,5,1,6,2,4,7
#9     9 5,1,6,2,3,4,7,8
#10   10                
#11   12              11