Dear list
I am trying to implement the Kou's algorithm to identify Steiner Tree(s) in R
using igraph.
The Kou's algorithm can be described like this:
1. Find the complete distance graph G' (G' has V' = S (steiner nodes) , and
for each pair of nodes (u,v) in VxV there is an edge with weight equal to the
weight of the min-cost path between these nodes p_(u,v) in G)
2. Find a minimum spanning tree T' in G'
3. Construct the subgraph Gs, of G by substituting every edge of T', which is
an edge of G' with the corresponding shortest path of G (it there are several
shortest paths, pick an arbitrary one).
4. Find the minimal spanning tree, Ts, of Gs (If there are several minimal
spanning trees, pick an arbitrary one)
5. Construct a Steiner tree, Th, from Ts by deleting edges in Ts, if necessary,
to that all the leaves in Th are Steiner nodes.
The first 2 steps are easy:
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)
However, I don't know how to replace the edges in T' for the shortest path in
G. I know that with `get.shortest.paths` I can get the `vpath` from a pair of
nodes, but how I replace and edge in T' with the `shortest.path` in G?
Many thanks in advance
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
