|
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 |
[Prev in Thread] | Current Thread | [Next in Thread] |