Вычислить ВСЕ связующие деревья ориентированного ациклического графа с помощью igraph, сети или другого пакета R - PullRequest
Новая
       9

Вычислить ВСЕ связующие деревья ориентированного ациклического графа с помощью igraph, сети или другого пакета R

1 голос
/ 17 апреля 2019

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

Я вижу функциональность для вычисления связующего дерева минимум с igraph: 

library(igraph)
g <- sample_gnp(100, 3/100)
g_mst <- mst(g)

и я вижу предыдущую запись StackOverflow , в которой описано, как вычислить остовное дерево с использованием поиска в ширину .Код ниже адаптирован из принятого ответа: 

r <- graph.bfs(g, root=1, neimode='all', order = TRUE, father = TRUE)
h <- graph(rbind(r$order, r$father[r$order, na_ok = TRUE])[,-1], directed = FALSE)

Однако я не знаю, как адаптировать это для вычисления нескольких остовных деревьев.Как можно адаптировать этот код для вычисления всех остовных деревьев?Я думаю, что одна часть этого будет проходить через каждый узел, чтобы использовать в качестве «корня» каждого дерева, но я не думаю, что это займет у меня весь путь (так как все еще могут быть связаны несколько связующих деревьевс заданным корневым узлом).

РЕДАКТИРОВАТЬ

Конечной целью является вычисление искажения графика, который определяется следующим образом( ссылка, см. Стр. 5 ):

Рассмотрим любое связующее дерево T на графике G и вычислите среднее расстояние t = E [H T ] на T между любыми двумя узлами, которые совместно используют ссылку в G .Искажение показывает, как T искажает ссылки в G , т. Е. Измеряет, сколько дополнительных прыжков требуется для перехода с одной стороны ссылки в G на другую., если мы ограничены использованием T .Искажение определяется [13] как наименьшее среднее значение за все возможные значения T с.Интуитивно искажение измеряет, насколько древовиден граф*

1 Ответ

3 голосов
/ 18 апреля 2019

Я не думаю, что вы найдете функцию для этого в пакете R.

На графе имеется n ^ {n-2} остовных деревьев (согласно формуле Кэли ).Даже на вашем графе с 10 узлами может существовать 1 000 000 000 различных охватывающих деревьев, что является большим числом.

Кроме того, проблема подсчета или перечисления всех охватывающих деревьев данного графа составляет # P-Завершите , что сложнее, чем задачи NP-Complete.

Если вы действительно хотите это сделать, я рекомендую сбросить R и начать использовать C или C ++, что может вычислить вашу проблему гораздо быстрее, чем любая другая.Код R может сделать.
Взгляните на в этой статье для обзора алгоритмов вычисления всех связующих деревьев связного графа (который, я думаю, ваш случай).

...