Извлечь поддерево в R

Question

У меня есть дерево, представленное data.frame с двумя столбцами. Первый столбец - это идентификатор узла, а второй - идентификатор родителя, учитывая, что root является его собственным родителем.

Например,

df <- data.frame(id = 1:10, parent = c(1,1,1,2,2,2,3,3,5,5))

соответствует следующему дереву :

Я хочу написать функцию

get_subtree <- function(new_root) {
  ...
}

, которая возвращает вектор идентификаторов узлов поддерева, у которого root равно new_root , Например, get_subtree(2) вернет вектор c(2,4,5,6,9,10). Я предполагаю, что это должна быть рекурсивная функция, которая возвращает new_root, если new_root является листом. Я могу легко получить дочерние элементы данного узла, используя df %>% filter(parent == new_root) %>% pull(id), но он останавливается на первом поколении. Так как написать мою функцию?

NB : я знаю о пакете data.tree. Я мог бы преобразовать свой data.frame в data.tree объект, используя mytree <- data.tree::FromDataFrameNetwork(df[-1,]) (здесь мне нужно удалить root), и тогда я думаю, что я мог бы легко использовать встроенные функции для получения поддеревьев. Проблема в том, что в моем дереве более двух миллионов узлов, а data.tree::FromDataFrameNetwork занимает слишком много времени. Мне просто нужно относительно небольшое поддерево (несколько тысяч узлов), поэтому я думаю, что лучше работать на data.frame напрямую.

Answer 1

Возможно, мы можем использовать igraph

library(igraph)
g1 <- graph.data.frame(df[2:1])
as.numeric(subcomponent(g1, 2, mode = 'out'))
#[1]  2  4  5  6  9 10