r - 图中最低的共同祖先

假设我们在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）？也就是说，在上面的示例中


7和14的LCA为2。
6、9、12和14的LCA为1。
1和8的LCA为1。
任何节点的LCA本身就是。


等等。

感觉应该在igraph中应该有一种优雅的方法，但是我还没有找到它。我玩过对all_simple_paths的调用的交集，但是由于我没有很好的方法来获取每个节点的级别，因此这无济于事。

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