R：深度最小生成树

Question

问题R: tree with overlapping strings我问做一棵树，看起来像：

V621 --> V62123 --> V6212355 
    --> V621335 --> V62133526 
    --> V6216 --> V62162 
    --> V621213452 
    --> V62126324 

它的工作原理与minimum spanning tree从包装igraph，但现在我想确定的深度该树的每个元素。我怎么这么做？

Answer 1

如果我们借用了previous answer所有相关代码...

df <- read.table(text='verkoop   V621 
verkoopcode  V62123 
verkoopcodenaam V6212355 
verkoopdatum  V621335 
verkoopdatumchar V62133526 
verkooppr  V6216 
verkoopprijs  V62162 
verkoopsafdeling V621213452 
verkoopsartikel V62126324') 
# use igraph package 
require(igraph) 
# create adjacency matrix 
adj <- nchar(sapply(df$V1, gsub, x=df$V1, replacement='')) 
adj[!sapply(df$V1, grepl, x=df$V1)] <- 0 
# name adjecency matrix 
colnames(adj) <- df$V2 
# original graph 
gr <- graph.adjacency(adj, mode='directed', weighted=TRUE) 
layout(matrix(1:2, ncol=2)) 
plot(gr) 
# minimum spanning tree 
mst <- minimum.spanning.tree(gr) 

你可以得到

shortest.paths(mst, to="V621", weights=rep(1, ecount(mst))) 
#   V621 
# V621   0 
# V62123  1 
# V6212355  2 
# V621335  1 
# V62133526  2 
# V6216   1 
# V62162  2 
# V621213452 1 
# V62126324  1 

注意的深度，我们有因为使用默认graph.adjacency来调整权重adj中的值作为边的权重，实际上我们只想将每个边计为一个。你可能也做

gr <- graph.adjacency(adj>0, mode='directed', weighted=TRUE) 
mst <- minimum.spanning.tree(gr) 
shortest.paths(mst, to="V621") 

所有默认的权重设置为1。

这是假设你知道taht“V621”为根节点。如果你不知道哪个是根节点，你可以用

dx <-degree(mst, mode="out") 
root <- names(dx)[dx==0] 
shortest.paths(mst, to=root, weights=rep(1, ecount(mst)))