[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] kou algorithm to find steiner tree

From: Juan Fernandez
Subject: [igraph] kou algorithm to find steiner tree
Date: Fri, 8 May 2015 09:06:40 +0000

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 

reply via email to

[Prev in Thread] Current Thread [Next in Thread]