r - 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”共享的最接近的父节点将是“无”。

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

标签： rgraph-theoryigraphdirected-graphgraph-traversal

Answer 1

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