字形中最低的共同祖先 [英] Lowest common ancestor in igraph

问题描述

假设igraph中有一棵树：

library(igraph)

g <- make_tree(14, children = 3)
plot(g, layout = layout_as_tree)

^{由reprex package(v0.3.0)}于2019-12-21创建

如何找到任意节点集合的lowest common ancestor(LCA)？即上面的示例

1. 7和14的LCA为2。
2. 6、9、12和14的LCA为1。
3. %1和%8的LCA为%1。
4. 任何节点的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)

这篇关于字形中最低的共同祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！