Kou的算法使用igraph找到Steiner樹

Question

我正在試圖用igraph實現Kou的算法來識別R中的Steiner樹（s）。

的寇氏算法可以這樣描述：

1. 找到完整的距離圖G '（G' 具有V」 = S（斯坦納的節點），並且對於每對節點的（U，V）在VxV中存在一個邊，其權重等於G中這些節點之間的最小成本路徑p_（u，v）的權重
2. 在G'中找到最小生成樹T'
3. 構造子圖Gs ，G'的每條邊代替G'的相應最短路徑G（它有幾條最短路徑，選擇一條任意一條）。
4. 找到Gs的最小生成樹Ts（如果有幾個最小生成樹，則選取任意一個）
5. 通過刪除Ts中的邊來構造一個Steiner樹Th，如有必要， Th中的所有葉子都是Steiner節點。

第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，但我如何在T中用shortest.path代替T'中的邊緣？

提前感謝

Answer 1

如果我理解算法你寫它，我覺得這可以讓你通過第3步，但請澄清，如果這是不是這樣：

library(igraph) 

set.seed(2002) 

g <- erdos.renyi.game(100, 1/10) # graph 
V(g)$name <- as.character(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) 

## For each edge in mst, replace with shortest path: 
edge_list <- get.edgelist(mst) 

Gs <- mst 
for (n in 1:nrow(edge_list)) { 
    i <- edge_list[n,2] 
    j <- edge_list[n,1] 
    ## If the edge of T' mst is shared by Gi, then remove the edge from T' 
    ## and replace with the shortest path between the nodes of g: 
    if (length(E(Gi)[which(V(mst)$name==i) %--% which(V(mst)$name==j)]) == 1) { 
     ## If edge is present then remove existing edge from the 
     ## minimum spanning tree: 
     Gs <- Gs - E(Gs)[which(V(mst)$name==i) %--% which(V(mst)$name==j)] 

     ## Next extract the sub-graph from g corresponding to the 
     ## shortest path and union it with the mst graph: 
     g_sub <- induced.subgraph(g, (get.shortest.paths(g, from=V(g)[i], to=V(g)[j])$vpath[[1]])) 
     Gs <- graph.union(Gs, g_sub, byname=T) 
    } 
} 

par(mfrow=c(1,2)) 
plot(mst) 
plot(Gs) 

情節左側最小生成樹，用最短路徑上權代替：