Я пытаюсь реализовать алгоритм Коу, чтобы идентифицировать дерево Штайнера в R, используя igraph.
Алгоритм Kou может быть описан следующим образом:
- Найти полный граф расстояний G '(G' имеет V '= S (узлы стайнеров), а для каждой пары узлов (u, v) в VxV есть ребро с весом, равным весу min- путь стоимости между этими узлами p_ (u, v) в G)
- Найти минимальное остовное дерево T 'в G'
- Построим подграф Gs группы G, подставляя каждое ребро T ', являющееся реброми G' с соответствующим кратчайшим путем G (его несколько кратчайших путей, выбираем произвольный).
- Найдите минимальное остовное дерево, Ts, of Gs (если имеется несколько минимальных остовных деревьев, выберите произвольный)
- Построим дерево Штейнера, Th, из Ts, удалив края в Ts, если это необходимо, к тому, что все листья в Th являются узлами Штейнера.
Первые 2 шага легко:
g <- erdos.renyi.game(100, 1/10) # graph
V(g)$name <- 1:100
# Some steiner nodes
steiner.points <- sample(1:100, 5)
# Complete distance graph G'
Gi <- graph.full(5)
V(Gi)$name <- steiner.points
# Find a minimum spanning tree T' in G'
mst <- minimum.spanning.tree(Gi)
Однако я не знаю, как заменить ребра в T 'для кратчайшего пути в G. Я знаю, что с get.shortest.paths
я могу получить vpath
из пары узлов, но как я заменяю и ребро в Т 'с shortest.path
в G?
Большое спасибо заранее