r - igraph中最低的共同祖先

Question

假设我们在 igraph 中有一棵树:

library(igraph)

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

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

我们如何找到 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 的调用交集，但由于我没有获得每个节点级别的好方法，所以这没有帮助。

我知道许多系统发育包implement this对于其他数据结构，但如果图上有合理的解决方案，我宁愿避免相互转换。 (不过，我对 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)