[igraph] kou algorithm to find steiner tree

[Juan Fernandez]

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