最小木問題(Minimum Spanning Tree)

「最小木問題」
各エッジに重みのついた完全結合グラフから、全ノードを結び、
重みの総和が最小となるようなエッジの組み合わせを求める問題

です。
現在2週間おきに留学生のＡと後輩で学部生のＭ君と勉強会を
開いています。そこでこの前の内容がこの最小木問題。
学部生のＭ君にとっては難しい内容のようだが。。。
この勉強会の特徴は各自がエクササイズ問題を解いてきて
答え合わせをすること。
どんなに難しい問題を解くよりも、一度自分でプログラムを
書く方が十分勉強になる(-_-)>
ちなみに私が今回書いたプログラムは以下の通り、

#Minimum Spanning Tree Algorithms (Prim algorithm)
#submit data should be V*L matrix.
#sequence already should have been converted
#from ATGC to 1-4.
#V : the number of sequences.
#L : the length of sequences.

#coded by Tanakky
#2007/12/05 1st version

MST <- function(data){
#call library
library(graph)
library(Rgraphviz)

######## demo mode ############
#The data for demonstration are obained randomly
if(data == "demo"){
data <- sample(1:4, 60, replace=T)
data <- matrix(data, nrow=6, ncol=10)
rownames(data) <- LETTERS[1:6]
colnames(data) <- 1:10
}
print("The demo data is below.\n")
print(data)
###############################

#make complete connected graph
#edgeweights are calculated from input data
V <- LETTERS[1:nrow(data)] #named node A, B, C, ....
WT <- vector("list", length=length(V)) #edgeweight
names(WT) <- V
dif <- c()
for(i in 1:length(V)){
e <- c()
wt <- c()
for(j in 1:length(V)){
if(i != j){
e <- c(e, V[j])
dif <- data[j,] - data[i,]
wt <- c(wt, ncol(data) - length(dif[dif==0]))
}
}
WTi <- list(edges=e, weights=wt)
}
G <- new("graphNEL", node=V, edgeL = WT) #complete connected graph

#Initialization of arrays
E_star <- vector("list", length=length(V)) #edges in MST
names(E_star) <- V
for(i in 1:length(V)){

}
V_star <- c() #nodes in MST
E <- edges(G) #all edges
Es <- E #A set of edges which disconnects the given graph
min_wt <- 0 #minimum weight
min_v <- c() #nodes which have minimum weight edge
sub_wt <- c() #sub weight array

#MST algorithms
for(i in 1:(length(V)-1)){
#get edgeweights for each node
WT <- c()
sub_wt <- unlist(edgeWeights(G, names(Es)))
for(j in 1:length(Es)){
WT <- c(WT ,paste(names(Es)[j], ".", Esj, sep=""))
}
WT <- sub_wt[WT]
#print(WT)

#get nodes which have mimimum weight edge
min_wt <- min(WT)
min_v <- which(WT == min_wt)
min_v <- unlist(strsplit(names(WT)[min_v[1]], "\\."))
print(paste(min_v[1], "-", min_v[2],
" is minimum weight (=", min_wt,") edge in Es.", sep=""))

#add edge and node into MST
V_star <- unique(c(V_star, min_v))
E_starmin_v[1] <- unique(c(E_starmin_v[1], min_v[2]))
E_starmin_v[2] <- unique(c(E_starmin_v[2], min_v[1]))
#print(V_star)
#print(E_star)

#update Es
Es <- vector("list", length=length(V_star))
names(Es) <- V_star
for(j in 1:length(Es)){
Esj <- setdiff(V, V_star)
}
#print(Es)
}

#attribute of graph aplot
eAttrs <- list()
nAttrs <- list()
colE <- c()
otherE <- c()
for(i in 1:length(E_star)){
colE <- c(colE, paste(names(E_star)[i], "~", E_stari, sep=""))
}
otherE <- setdiff(edgeNames(G), colE)
eAttrs$label <- unlist(unlist(edgeWeights(G)))
toRemove <- removedEdges(G)
if(length(toRemove) > 0){
eAttrs$label <- eAttrs$label[-toRemove]
}
names(eAttrs$label) <- edgeNames(G)
eAttrs$fontcolor <- c(rep("red", times=length(colE)), rep("grey",times=length(otherE)))
names(eAttrs$fontcolor) <- c(colE, otherE)
eAttrs$color <- c(rep("red", times=length(colE)), rep("grey", times=length(otherE)))
names(eAttrs$color) <- c(colE, otherE)
nAttrs$color <- c(rep("red", times=length(V)))
names(nAttrs$color) <- V

#return data
plot(G, "neato", nodeAttrs=nAttrs, edgeAttrs=eAttrs,
main="Minimum Spanning Tree")
}

R言語で書いています。ちなみにこのプログラムを動かすには
「graph」と「Rgraphviz」ライブラリが必要です。
出力結果は。。。。

ってな感じで。
完全結合グラフから最小木を取り出したようすです。(^o^)v