igraph 中的最低共同祖先

Question

假设我们有一棵树igraph：

library(igraph)

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

^{由reprex 包(v0.3.0)于 2019 年 12 月 21 日创建}

我们如何找到任意节点集合的最低共同祖先（LCA）？也就是说，在上面的例子中

1. 7 和 14 的 LCA 是 2。
2. 6、9、12 和 14 的 LCA 为 1。
3. 1 和 8 的 LCA 为 1。
4. 任何节点的 LCA 都是它自己。

等等。

感觉应该有一种优雅的方式来做到这一点igraph，但我还没有找到。我尝试过调用 的交叉点all_simple_paths，但由于我没有获得每个节点级别的好方法，因此这没有帮助。

我知道许多系统发育包为其他数据结构实现了 这一点，但如果图表上有合理的解决方案，我宁愿避免相互转换。（但是，我对tidygraph解决方案非常满意。）

Answer 1

对于树，您可以获得从节点到根的路径。然后找到路径之间的交叉点的最高索引：

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)