3

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

4

2 回答 2

5

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

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)
于 2019-12-21T19:07:39.270 回答
4

至少对于中等大小的图表，您可以从点之间的距离矩阵中做到这一点。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
于 2019-12-21T18:59:53.383 回答