本文介绍了字形中最低的共同祖先的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
假设igraph
中有一棵树:
library(igraph)
g <- make_tree(14, children = 3)
plot(g, layout = layout_as_tree)
于2019-12-21创建
如何找到任意节点集合的lowest common ancestor(LCA)?即上面的示例
- 7和14的LCA为2。
- 6、9、12和14的LCA为1。
- %1和%8的LCA为%1。
- 任何节点的LCA都是其自身。
等等。
感觉在igraph
中应该有一种优雅的方法来完成这项工作,但我还没有找到它。我尝试了调用all_simple_paths
的交叉点,但由于我没有好的方法来获取每个节点的级别,所以这没有帮助。
我知道许多用于其他数据结构的系统发育包implementthis,但如果图上有合理的解决方案,我宁愿避免相互转换。(不过,我对tidygraph
解决方案非常满意。)
推荐答案
对于树,您可以获取从节点到根的路径。然后找出路径之间的交集的最高指数:
lca <- function(graph, ...) {
dots = c(...)
path = ego(graph, order=length(V(graph)), nodes=dots, mode="in")
max(Reduce(intersect, path))
}
lca(g, 7, 14)
lca(g, 10, 8)
这篇关于字形中最低的共同祖先的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!