使用 igraph 查找 Steiner 树的 Kou 算法
Kou's algorithm to find Steiner Tree using igraph
我正在尝试使用 igraph 实现 Kou 的算法来识别 R 中的 Steiner 树。
寇氏算法可以这样描述:
- 找到完整的距离图G'(G'有V' = S(steiner节点),并且对于VxV中的每对节点(u,v)都有一条边,其权重等于这些节点之间的最小成本路径 p_(u,v) in G)
- 在G'中找到最小生成树T'
- 构造G的子图Gs,将T'的每条边,也就是G'的一条边,代入G的对应的最短路径(如果有几条最短路径,随便选一条)。
- 求Gs的最小生成树Ts(如果有几棵最小生成树,随便挑一棵)
- 从Ts构造一棵Steiner树Th,必要时删除Ts中的边,使Th中的所有叶子都是Steiner节点。
前两步很简单:
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
,但我如何用 G 中的 shortest.path
替换 T' 中的边缘?
非常感谢
如果我理解您编写的算法,我认为这可以帮助您完成第 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)
左侧最小生成树图,右侧替换为最短路径:
我正在尝试使用 igraph 实现 Kou 的算法来识别 R 中的 Steiner 树。
寇氏算法可以这样描述:
- 找到完整的距离图G'(G'有V' = S(steiner节点),并且对于VxV中的每对节点(u,v)都有一条边,其权重等于这些节点之间的最小成本路径 p_(u,v) in G)
- 在G'中找到最小生成树T'
- 构造G的子图Gs,将T'的每条边,也就是G'的一条边,代入G的对应的最短路径(如果有几条最短路径,随便选一条)。
- 求Gs的最小生成树Ts(如果有几棵最小生成树,随便挑一棵)
- 从Ts构造一棵Steiner树Th,必要时删除Ts中的边,使Th中的所有叶子都是Steiner节点。
前两步很简单:
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
,但我如何用 G 中的 shortest.path
替换 T' 中的边缘?
非常感谢
如果我理解您编写的算法,我认为这可以帮助您完成第 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)
左侧最小生成树图,右侧替换为最短路径: