igraph 中的最低共同祖先

Question

假设我们在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 解决方案非常满意。）

Answer 1

至少对于中等大小的图表，您可以根据点之间的距离矩阵执行此操作。当且仅当存在从 x 到 y 的路径时，x 是 y 的祖先。此外，如果 x 的索引 > y 的索引，则 x 在树中不高于 y。

DM = distances(g, V(g), mode="out")
LCA = function(NodeList) {
    max(which(rowSums(is.infinite(DM[,NodeList])) == 0)) 
}
LCA(c(7,14))
2
LCA(c(6,9,12,14))
1

Answer 2

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

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)

igraph 中的最低共同祖先

Lowest common ancestor in igraph

r

igraph

graph-theory

tidygraph