親と一緒にRで木を作る

Question

私はRで木を作り、2つのノード間の距離を計算しようとしています。

データフレームツリーが似ているようにする：

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の間の距離は、2-1-3-8まで3である。

ツリーは、例えば、ノード10のためのPathStringが1/4/10として与えられるべきで、各ノードのパスとdata.treeパッケージを使用して構築することができるが、レベルの数が増加するとき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