3

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

MSR
  • 2,731
  • 1
  • 14
  • 24

2 Answers2

5

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)
user20650
  • 24,654
  • 5
  • 56
  • 91
4

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
G5W
  • 36,531
  • 10
  • 47
  • 80