Кратчайший путь, соединяющий несколько узлов в iGraph R

У меня есть сеть iGraph в R, и я хотел бы найти кратчайший путь, соединяющий несколько узлов в моей сети (скажем, узлы 1,3,4,7). Есть ли функция, которая может это сделать? Что-то вроде all_simple_paths, но для одного глобального решения?

Решение должно выглядеть примерно так, как путь, выделенный желтым. Обратите внимание, что 1-> 2-> 4 не выбран, хотя он такой же короткий, как 1-> 3-> 4.

library(igraph)
tree <- graph.tree(n = 8, children = 2, mode = "out")
tree <- add_edges(tree, c(3,4, 3,5))
plot(tree)

введите здесь описание изображения


r igraph shortest-path
person Daniel Freeman    schedule 17.04.2020    source источник
comment
@MrFlick нет, я просто добавил пример, чтобы показать вам. shortest_paths дает отдельное решение для каждого пункта назначения, а не одно глобальное решение.   -  person Daniel Freeman    schedule 18.04.2020

Ответы (1)


arrow_upward
3
arrow_downward

Покопавшись, я думаю, что нашел ответ на свой вопрос. То, что я описал, является разновидностью проблемы минимального остовного дерева, называемой проблемой дерева Штейнера.

Для взвешенного графа G = (V, E), подмножества S ⊆ V вершин и корня r ∈ V мы хотим найти дерево минимального веса, которое соединяет все вершины в S с r. [ref]

Оказывается, существует пакет R под названием SteinerNet, созданный специально для этих типов проблем. У меня возникли проблемы с установкой их пакета напрямую, но я смог скопировать соответствующий исходный код из их Репозиторий GitHub.

out <- steinertree(type = "KB", terminals = c(1,3,4,7), graph = tree)

Пакет делает именно то, что я хотел, и даже создал красивую диаграмму!

>out[[2]]
IGRAPH fbb52e5 UN-- 4 3 -- Tree
+ attr: name (g/c), children (g/n), mode (g/c), name (v/c), color (v/c)
+ edges from fbb52e5 (vertex names):
[3] 1--3 3--4 3--7
>plot(out[[1]])

Вывод из функции SteinerNet

person Daniel Freeman    schedule 18.04.2020