给定是一棵树:
library(igraph)
# setup graph
g= graph.formula(A -+ B,
A -+ C,
B -+ C,
B -+ D,
B -+ E
)
plot(g, layout = layout.reingold.tilford(g, root="A"))
顶点
"A"
是树的根,而顶点 "C", "D", "E"
被视为终端叶。问题:
任务是找到根和叶之间的所有路径。我失败了以下代码,因为它只提供最短路径:
# find root and leaves
leaves= which(degree(g, v = V(g), mode = "out")==0, useNames = T)
root= which(degree(g, v = V(g), mode = "in")==0, useNames = T)
# find all paths
paths= lapply(root, function(x) get.all.shortest.paths(g, from = x, to = leaves, mode = "out")$res)
named_paths= lapply(unlist(paths, recursive=FALSE), function(x) V(g)[x])
named_paths
输出:
$A1
Vertex sequence:
[1] "A" "C"
$A2
Vertex sequence:
[1] "A" "B" "D"
$A3
Vertex sequence:
[1] "A" "B" "E"
问题:
如何找到包括顶点序列在内的所有路径:
"A" "B" "C"
?我的理解是,缺失的序列
"A" "B" "C"
不是由 get.all.shortest.paths()
提供的作为来自 "A"
的路径至 "C"
通过顶点序列:"A" "C"
(在列表元素 $A1
中找到)较短。所以igraph
工作正常。尽管如此,我正在寻找一种代码解决方案,以
R list
的形式获取从根到所有叶子的所有路径. 评论:
我知道对于大树,覆盖所有组合的算法可能会变得昂贵,但我的实际应用程序相对较小。
最佳答案
根据 Gabor 的评论:
all_simple_paths(g, from = root, to = leaves)
产量:
[[1]]
+ 3/5 vertices, named:
[1] A B C
[[2]]
+ 3/5 vertices, named:
[1] A B D
[[3]]
+ 3/5 vertices, named:
[1] A B E
[[4]]
+ 2/5 vertices, named:
[1] A C
关于r - igraph R中从根到叶的有向 TreeMap 中的所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31406328/