Lowest Common Ancestor in a Directed Graph in igraph?

user_7966156 0
Viewed 200

Does igraph have an algorithm that outputs the lowest common ancestor(s) of 2 nodes in a directed graph? This is NOT a DAG, it could have cycles.

If not, is there a way I could use igraph to determine the LCA?

Here is a sample graph:

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)

enter image description here

  • If I were to ask, what is the closest parent that nodes "E" and "C" share? The answer is "A" or "B" or "F".

  • What about the closest parent that nodes "G" and "C" share? The answer is "H".

  • Since we are looking for parents, a node cannot be its own parent, so the closest parent that nodes "H" and "C" share would be "G".

  • Finally, the closest parent that nodes "A" and "G" share would be "None."

P.S. I'm not sure if there is a rule in the case of ties. Like if nodes are a distance of (1,3 respectively) from a parent vs (2,2 respectively) from another parent.

graph-traversal igraph graph-theory directed-graph r
2 Answers

If your graph contains cycles, then you cannot infer a topologic order on its vertices.
Without an order on vertices, you cannot define "Lowest", and thus you cannot define what a "Lowest Common Ancestor" is.
So unless you come up with an alternative definition of "Lowest Common Ancestor", the problem cannot be solved, since it cannot be characterized.

user_74426730

I guess you can define a custom function like below

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)))
}

and then

> 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"
user_121587570
Related