Сделайте дерево в R с родителями

Question

Я пытаюсь сделать дерево в R и рассчитать расстояние между двумя узлами.

Фрейм данных, чтобы сделать дерево, как:

tree.source <- data.frame(ID = 1:10, parentID = c(NA,1,1,1,2,2,2,3,4,4)) 
#ID parentID 
#1 NA 
#2  1 
#3  1 
#4  1 
#5  2 
#6  2 
#7  2 
#8  3 
#9  4 
#10 4 

И надеемся создать древовидную структуру, подобную этой

Кроме того, я также хочу, чтобы получить расстояние между 2 узла. Например, расстояние между узлом 5 и 10 здесь составляет 4, через 5-2-1-4-10. Есть 4 края, чтобы связать их. Расстояние между узлами 2 и 8 равно 3, через 2-1-3-8.

Дерева можно строить, используя data.tree пакет с дорожками для каждого узла, например, PathString для узла 10 должно быть задано как 1/4/10, но PathString может быть очень длинным, когда число уровней увеличения , Есть ли лучший способ построить дерево?

Answer 1

Дерево может быть сгенерирован с помощью:

tree <- as.Node(tree.source[-1,],mode = "network") 

функцию as.Node может генерировать дерево с сетью, которая имеет первый столбец как «с», а второй, как «до» и следующий в качестве атрибутов.

И distance(g, 2, 8) может дать расстояние между узлом 2 и 8.

Answer 2

Попробуйте это (с данной tree.source):

library(igraph) 
g <- graph.data.frame(tree.source[-1,2:1], directed = FALSE) 
plot(g) 

# do a bfs with root as source, you will get distance of each vertex from root 
bfs(g, root=1, "out", dist=TRUE)$dist 
# 1 2 3 4 5 6 7 8 9 10 
# 0 1 1 1 2 2 2 2 2 2 

# shortest path from 5 to 10 
sp <- unlist(shortest_paths(g, 5, 10, mode="out")$vpath) 
sp 
# 5 2 1 4 10 
# 5 2 1 4 10 

# distance from 5 to 10 = # vertices on the path - 1 
length(sp)-1 
# [1] 4 

# shortest paths from source node 5 to all 
sp_from_5 <- shortest_paths(g, 5, mode="out")$vpath 
names(sp_from_5) <- names(V(g)) 
sp_from_5 

# output 
$`1` 
+ 3/10 vertices, named: 
[1] 5 2 1 

$`2` 
+ 2/10 vertices, named: 
[1] 5 2 

$`3` 
+ 4/10 vertices, named: 
[1] 5 2 1 3 

$`4` 
+ 4/10 vertices, named: 
[1] 5 2 1 4 

$`5` 
+ 1/10 vertex, named: 
[1] 5 

$`6` 
+ 3/10 vertices, named: 
[1] 5 2 6 

$`7` 
+ 3/10 vertices, named: 
[1] 5 2 7 

$`8` 
+ 5/10 vertices, named: 
[1] 5 2 1 3 8 

$`9` 
+ 5/10 vertices, named: 
[1] 5 2 1 4 9 

$`10` 
+ 5/10 vertices, named: 
[1] 5 2 1 4 10