Lowest Common Ancestor in a Directed Graph in igraph?

Question

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)

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.

It's easier to help you if you include a simple [reproducible example](https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) with sample input and desired output that can be used to test and verify possible solutions. — MrFlick, Aug 18 '21 at 23:36
do either of [these](https://stackoverflow.com/questions/59438409/lowest-common-ancestor-in-igraph) work with cycles? — user20650, Aug 18 '21 at 23:44
@user20650 yes, exactly. one of those graphs but with cycles so they aren't trees. I need to try to make a directed graph with cycles from scratch to provide a reproducible example. I wonder if there are any default ones in igraph — Nova, Aug 19 '21 at 02:50
If it is with cycles, what is the expected result then? Could you show an example with data as well as desired output? — ThomasIsCoding, Aug 19 '21 at 06:12
Why `B` is the LCA of `E` and `C`? If `B` is counted, then `F` should be a fine as well. — ThomasIsCoding, Aug 19 '21 at 20:06
Good call! Yes, F as well. I made a note about that as well in the question. — Nova, Aug 19 '21 at 20:16
Also, for nodes `G` and `C`, it seems the LCA could be `G` or `H`, since their sum distance to two nodes are both 4, i.e., a tie. — ThomasIsCoding, Aug 19 '21 at 20:54
Hi, I'd argue that it can't be G because a node cant be its own parent? Otherwise the closest parent for "E" and "C" would be "E" — Nova, Aug 19 '21 at 21:03
I’m voting to close this question because it does not clearly define the problem to be solved. What is a "lowest common ancestor"? What is a "parent"? — Szabolcs, Sep 03 '21 at 16:45

score 2 · Answer 1 · answered Aug 19 '21 at 09:27

2

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.

answered Aug 19 '21 at 09:27

m.raynal

2,983
2
21
34

Hi, thank you for the clarification. I hope I added more detail to the question so that the problem can be characterized. – Nova Aug 19 '21 at 18:42
I'm afraid you need to come up with a more strict definition. For example, you can try to minimize the sum (or product, or ...) of the distances from the ancestor to the target nodes. In any case, there may be ties the same way there may be ties in a DAG. So you'll be looking for *a* LCA, not *the* LCA. – m.raynal Aug 20 '21 at 10:24

ThomasIsCoding · Accepted Answer · 2021-08-19T21:08:50.443

1

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"

edited Aug 19 '21 at 21:08

answered Aug 19 '21 at 20:49

ThomasIsCoding

96,636
9
24
81

Lowest Common Ancestor in a Directed Graph in igraph?

2 Answers2