igraph 有向图中的最低公共祖先？

Question

igraph 是否有一种算法可以输出有向图中 2 个节点的最低公共祖先？这不是 DAG，它可以有循环。

如果没有，有没有办法使用 igraph 来确定 LCA？

这是一个示例图：

m <- read.table(row.names=1, header=TRUE, text=
                  " A B C D E F G H
                A 0  1  1  0  0 0 0 0
                B 0  0 0  1  1 0 0 0
                C 0 0  0  1 0 0 0 0
                D 0  0  0  0 0 1 0 0
                E 0  0 1 0  0 0 0 0
                F 0  0  0  0  1 0 0 0
                G 0  0  0  1  0 0 0 1
                H 0  0  0  0  0 1 1 0")
m <- as.matrix(m)
ig <- graph.adjacency(m, mode="directed")
plot(ig)

如果我要问，节点“E”和“C”共享的最近父节点是什么？答案是“A”或“B”或“F”。
节点“G”和“C”共享的最近的父节点呢？答案是“H”。
由于我们正在寻找父节点，因此节点不能是它自己的父节点，因此节点“H”和“C”共享的最近父节点将是“G”。
最后，节点“A”和“G”共享的最近父级将是“None”。

P.S。我不确定在平局的情况下是否有规则。就像节点与父节点的距离（分别为 1,3）和与另一个父节点的距离（分别为 2,2）一样。

Answer 1

如果您的图形包含循环，则您无法推断其顶点的拓扑顺序。
没有顶点顺序，你不能定义“最低”，因此你不能定义“最低公共祖先”是什么。
所以除非你想出“最低共同祖先”的替代定义，否则这个问题无法解决，因为它无法被表征。

Answer 2

我想你可以像下面这样定义一个自定义函数

f <- function(g, vs) {
  da <- subset(colSums(distances(g, mode = "in")[vs, ]), !names(V(g)) %in% vs)
  if (all(is.infinite(da))) {
    return("None")
  }
  names(which(da == min(da)))
}

然后

> f(ig, c("E", "C"))
[1] "A" "B" "F"

> f(ig, c("G", "C"))
[1] "H"

> f(ig, c("H", "C"))
[1] "G"

> f(ig, c("A", "G"))
[1] "None"

igraph 有向图中的最低公共祖先？

Lowest Common Ancestor in a Directed Graph in igraph?

r

graph-theory

directed-graph

igraph

graph-traversal