Kous Algorithmus zum Finden von Steiner-Bäumen mit Hilfe von ifigraph

Question

Ich versuche den Kous Algorithmus zu implementieren, um Steinerbäume in R mit Hilfe von igraph zu identifizieren.

Der Algorithmus des Kou kann wie folgt beschrieben werden:

1. finden die vollständige Entfernung Graph G '(G' ist V‘= S (Steiner-Knoten), und für jedes Paar von Knoten (u, v) in VxV gibt es eine Kante mit Gewicht gleich dem Gewicht des Min-Cost-Pfads zwischen diesen Knoten p_ (u, v) in G)
2. Suchen Sie einen minimalen Spannbaum T 'in G'
3. Konstruieren Sie den Teilgraphen Gs , von G, indem jede Kante von T ', die eine Kante von G' ist, durch den entsprechenden kürzesten Weg von G ersetzt wird (es gibt mehrere kürzeste Wege, wählen Sie einen beliebigen aus).
4. Finden Sie den minimalen Spannbaum, Ts, von Gs (Wenn es mehrere minimale Spannbäume gibt, wählen Sie einen beliebigen)
5. Konstruieren Sie einen Steinerbaum, Th, von Ts durch Löschen von Kanten in Ts, falls erforderlich, um das alle Blätter in Th sind Steinerknoten.

Die ersten 2 Schritte sind einfach:

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) 

Aber ich weiß nicht, wie die Kanten in T‘in G. für den kürzesten Weg zu ersetzen, ich weiß, dass mit get.shortest.paths kann ich die vpath von einem Paar von Knoten, aber wie ich ersetzen und Rand in T 'mit der shortest.path in G?

Vielen Dank im Voraus

Answer 1

Wenn ich den Algorithmus bin zu verstehen, wie Sie es geschrieben haben, ich denke, das Sie durch die 3-Schritt bekommt, aber bitte klären, ob dies nicht der Fall ist:

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) 

Plot von minimalen Spannbaum auf der linken Seite, mit kürzesten Wege auf der rechten Seite ersetzt: