igraph R中从根到叶的有向树图中的所有路径 [英] All paths in directed tree graph from root to leaves in igraph R
问题描述
给出的是一棵树:
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"
被视为终叶.
Vertex "A"
is the root of the tree, while vertices "C", "D", "E"
are considered as terminal leaves.
问题:
任务是查找根与叶之间的所有路径.使用以下代码失败,因为它仅提供最短的路径:
The task is to find all paths between root and leaves. I fail with following code, as it only provides the shortest paths:
# 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"
?
How can I find all paths including the vertex sequence: "A" "B" "C"
?
我的理解是,get.all.shortest.paths()
没有提供缺失的序列"A" "B" "C"
作为通过顶点序列从"A"
到"C"
的路径:"A" "C"
(可在列表元素$A1
中找到) )较短.因此igraph
可以正常工作.
尽管如此,我仍在寻找一种代码解决方案,以R list
的形式获取从根到所有叶子的所有路径.
My understanding is, that the missing sequence "A" "B" "C"
is not provided by get.all.shortest.paths()
as the path from "A"
to "C"
via the vertex sequence: "A" "C"
(which is found in list element $A1
) is shorter. So igraph
works properly.
Nevertheless I am looking for a code solution to get all paths from the root to all leaves in form of a R list
.
评论:
我知道对于大树,覆盖所有组合的算法可能会变得昂贵,但是我的实际应用相对较小.
I am aware that for large trees the algorithm covering all combinations might become expensive, but my real application is relatively small.
推荐答案
基于Gabor的评论:
Based on Gabor's comment:
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
这篇关于igraph R中从根到叶的有向树图中的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!