L'algoritmo di Kou per trovare l'albero di Steiner usando l'igraph

Question

Sto cercando di implementare l'algoritmo di Kou per identificare gli alberi di Steiner in R usando igraph.

algoritmo del Kou può essere descritto come segue:

1. Trova grafo completo distanza G '(G' ha = S (nodi Steiner V'), e per ogni coppia di nodi (u, v) in VxV c'è un fronte con peso uguale al peso del percorso minimo tra questi nodi p_ (u, v) in G)
2. Trova un albero di spaziatura minimo T 'in G'
3. Costruisci il sottografo Gs , di G sostituendo ogni spigolo di T ', che è un bordo di G' con il corrispondente percorso più breve di G (ci sono diversi percorsi più corti, ne scegli uno arbitrario).
4. Trova lo spanning tree minimo, Ts, di Gs (se ci sono diversi spanning tree minimi, ne scegli uno arbitrario)
5. Costruisci un albero di Steiner, Th, da Ts eliminando i bordi in Ts, se necessario, a quello tutte le foglie di Th sono nodi di Steiner.

I primi 2 passi sono facili:

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) 

Tuttavia, non so come sostituire i bordi in T' per il percorso più breve in G. So che con get.shortest.paths posso ottenere il vpath da una coppia di nodi, ma come sostituisco e bordo in T 'con il shortest.path in G?

Molte grazie in anticipo

Answer 1

Se ho la comprensione l'algoritmo come hai scritto, credo che questo si ottiene attraverso il passaggio 3, ma vi prego di chiarire se questo non è il caso:

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) 

Terreno di spanning tree minimo a sinistra, sostituito con percorsi più brevi a destra: