Наименьший общий предок в igraph

Предположим, у нас есть дерево в igraph:

library(igraph)

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

Создана 21 декабря 2019 г. с помощью пакета reprex (v0.3.0)

Как найти наименьшего общего предка (LCA) произвольного набора узлов ? То есть в приведенном выше примере

  1. LCA 7 и 14 равен 2.
  2. LCA 6, 9, 12 и 14 равен 1.
  3. LCA 1 и 8 равен 1.
  4. LCA любого узла — это он сам.

И так далее.

Кажется, что в igraph должен быть элегантный способ сделать это, но мне не удалось его найти. Я поигрался с пересечениями вызовов all_simple_paths, но так как у меня нет хорошего способа получить уровни каждого узла, это не помогло.

Я знаю, что многие пакеты филогенетики реализуют это для других структур данных, но я бы предпочел избегать взаимное преобразование, если на графе есть разумное решение. (Однако я вполне доволен решением tidygraph.)


r igraph graph-theory tidygraph
person MSR    schedule 21.12.2019    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Для дерева можно получить пути от узла к корню. Затем найдите наибольший индекс пересечения путей:

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)
person user20650    schedule 21.12.2019

arrow_upward
4
arrow_downward

По крайней мере, для графиков скромных размеров это можно сделать из матрицы расстояний между точками. x является предком y тогда и только тогда, когда существует путь от x к y. Кроме того, если индекс x > индекса y, x не выше, чем y в дереве.

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
person G5W    schedule 21.12.2019