Lowest common ancestor in igraph

Question

Suppose we have a tree in igraph:

library(igraph)

g <- make_tree(14, children = 3)
plot(g, layout = layout_as_tree)

^{Created on 2019-12-21 by the reprex package (v0.3.0)}

How do we find the lowest common ancestor (LCA) of an arbitrary collection of nodes? That is, in the above example

1. The LCA of 7 and 14 is 2.
2. The LCA of 6, 9, 12, and 14 is 1.
3. The LCA of 1 and 8 is 1.
4. The LCA of any node is itself.

And so on.

It feels like there ought to be an elegant way of doing this in igraph, but I haven't managed to find it. I played around with intersections of calls to all_simple_paths, but since I don't have a good way to get the levels of each node, this didn't help.

I am aware that many of the phylogenetics packages implement this for other data structures, but I would rather avoid the interconversion if there is a reasonable solution on the graph. (I'm perfectly happy with a tidygraph solution, however.)

Answer 1

For a tree, you can get the paths from a node to the root. Then find the highest index for the intersection beteen the paths:

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)

Answer 2

At least for modest size graphs, you can do this from the distance matrix between points. x is an ancestor of y if and only if there is a path from x to y. Also, if the index of x > index of y, x is no higher than y in the tree.

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