Prim法

特にテーマもなくBlogを初めたので、しばらくはグラフ理論のアルゴリズムに関するプログラムをF#を使って書いていくことにしてみようと思う。今回はPrim法で、入力データは前回と同じもの。グラフが与えられた時に、全ての点を通り、コストの総和が最小になるよう辺を選び取るアルゴリズムになります。

ところで、自分は、プログラムを作る際には、効率よりも「解けるプログラムを作ること」と、(自分にとって)理解しやすいこと、のほうを重視している。PerlやRubyなんかのLightweightな言語がはやってるように、とりあえず「出来る」だけで有用な場面のほうが多い気がするし、効率を気にして時間をかけてプログラムに四苦八苦するよりも、とりあえず出来たほうがなんか楽しい、というのが大きい。

という(いい)わけで、Prim法の実装にあたってResizeArray使った「手抜きPriority Queue」を実装してみた。本来ならヒープを使ってPriority Queueを実装するほうが効率もよいし本格的だが、そこは後で置き換えれば良いので、Prim法を解くことから入ってみる。

#light "off"

open Microsoft.FSharp.Collections;;
//プリム法
let pe x = print_any x;print_endline "";;
let m = Int32.max_int;;
let nodenum = 6;;
//辺リスト
let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];;
//簡易プライオリティキュー
type easy_pq<'T> = class
    val private array : ResizeArray<'T>
    val private sorter : 'T -> 'T -> int
    new (sortfunc,(ar : 'T array)) = {array = new ResizeArray<'T>(ar);sorter=sortfunc}
    new (sortfunc) = {array = new ResizeArray<'T>();sorter=sortfunc}
    member x.push v = x.array.Add(v);ResizeArray.sort x.sorter x.array
    member x.pop _ = let r = x.array.[0] in x.array.Remove(r)|>ignore;r
    member x.show f = Seq.iter f x.array
    end;;

let mst = new ResizeArray<int>();;
let edges = new ResizeArray<int*int*int>();;
//MSTの初期値としてノード0を指定
mst.Add(0);;

//MSTへ一つノードを追加し、edgesへ追加した辺を格納する
let update mst edges adj=
    let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in
        if l>r then 1 else if l<r then -1 else 0 in
    let pq = new easy_pq<int*int*int>(sorter) in
    //次の辺を見つけるためキューにデータを入れる
    for i in mst do
        Array.map (fun x ->
            let (f,t,c)=x in if f=i || t=i then pq.push x
            ) adj |> ignore
    done;
    //mstにないノードが見つかるまでキューからPOP
    let rec update_aux mst (edges:ResizeArray<int*int*int>) adj (pq:easy_pq<int*int*int>)=
        let nextedge = pq.pop() in
        let (f,t,c) = nextedge in
        if not (ResizeArray.exists ((=)t) mst) then begin mst.Add(t);edges.Add(nextedge) end
        else if not(ResizeArray.exists ((=)f) mst) then begin mst.Add(f);edges.Add(nextedge) end
        else update_aux mst edges adj pq in
    update_aux mst edges adj pq;;

//最初に1個入れているのでノード数-1回MSTのアップデートを繰り返す
for i=0 to nodenum-2 do update mst edges adj done;;
ResizeArray.iter pe edges;;

出力結果は、辺のリスト。これは、前に作ったグラフを可視化するプログラムにそのまま入力出来るので、次のプログラムで最小全域木がどうなってるか確認出来る。なお、今回のupdate関数は副作用ありな関数になっている。

#light "off"

open Microsoft.FSharp.Collections;;
open Microsoft.FSharp.Core;;
open System;;
open System.Windows.Forms;;
open System.Drawing;;

//プリム法
let pe x = print_any x;print_endline "";;
let m = Int32.max_int;;
let nodenum = 6;;
//辺リスト
let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];;
//簡易プライオリティキュー
type easy_pq<'T> = class
    val private array : ResizeArray<'T>
    val private sorter : 'T -> 'T -> int
    new (sortfunc,(ar : 'T array)) = {array = new ResizeArray<'T>(ar);sorter=sortfunc}
    new (sortfunc) = {array = new ResizeArray<'T>();sorter=sortfunc}
    member x.push v = x.array.Add(v);ResizeArray.sort x.sorter x.array
    member x.pop _ = let r = x.array.[0] in x.array.Remove(r)|>ignore;r
    member x.show f = Seq.iter f x.array
    end;;

let mst = new ResizeArray<int>();;
let edges = new ResizeArray<int*int*int>();;
//MSTの初期値としてノード0を指定
mst.Add(0);;

//MSTへ一つノードを追加し、edgesへ追加した辺を格納する
let update mst edges adj=
    let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in
        if l>r then 1 else if l<r then -1 else 0 in
    let pq = new easy_pq<int*int*int>(sorter) in
    //次の辺を見つけるためキューにデータを入れる
    for i in mst do
        Array.map (fun x ->
            let (f,t,c)=x in if f=i || t=i then pq.push x
            ) adj |> ignore
    done;
    //mstにないノードが見つかるまでキューからPOP
    let rec update_aux mst (edges:ResizeArray<int*int*int>) adj (pq:easy_pq<int*int*int>)=
        let nextedge = pq.pop() in
        let (f,t,c) = nextedge in
        if not (ResizeArray.exists ((=)t) mst) then begin mst.Add(t);edges.Add(nextedge) end
        else if not(ResizeArray.exists ((=)f) mst) then begin mst.Add(f);edges.Add(nextedge) end
        else update_aux mst edges adj pq in
    update_aux mst edges adj pq;;

//最初に1個入れているのでノード数-1回MSTのアップデートを繰り返す
for i=0 to nodenum-2 do update mst edges adj done;;
ResizeArray.iter pe edges;;


//要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス
type Graph = class inherit Form
	val pbox : PictureBox
	val pos : (float32*float32) array   //各ノードのx,y座標
	val circle_width : float32          //1つのノードの幅
	val circle_height : float32         //1つのノードの高さ
	new (pnum:int,adj) as this =
	    {pbox = new PictureBox();
	     pos=Array.init pnum (fun x -> (0.f,0.f));
	     circle_width = 50.f;
	     circle_height = 50.f;}
		then
		let (whole_width,whole_height)=(800,600) in
		this.Width <- whole_width;
		this.Height <- whole_height;
		let (screen_width,screen_height)=(this.ClientRectangle.Width,this.ClientRectangle.Height) in
		this.pbox.Dock <- DockStyle.Fill;
		this.Controls.Add(this.pbox);
		this.pbox.Image <- new Bitmap(screen_width,screen_height);
		//画面中央の計算
		let (cx,cy)=((Float32.of_int screen_width)/2.f,(Float32.of_int screen_height)/2.f) in
		//各ノードの座標計算
		for i=0 to pnum-1 do
		    let dist = 200.f in
		    let (dx,dy)=
		    (cx+dist*Float32.of_float(Math.Cos(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i))),
		     cy+dist*Float32.of_float(Math.Sin(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i)))) in
		     this.pos.[i]<-(dx,dy);
		done;
		//ノードを描く
		Array.mapi (fun i x -> this.circle (fst x) (snd x) (i.ToString())) this.pos |> ignore;
		//ノード間の接続とコストを描く
        for i in adj do
            let (s,e,c) = i in
            this.line (fst this.pos.[s]) (snd this.pos.[s]) (fst this.pos.[e]) (snd this.pos.[e]) (Float32.of_int c)
            done
		
    //円とラベルを指定座標に描く
    member this.circle (x:float32) (y:float32) label =
		use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in
		let w,h = (this.circle_width,this.circle_height) in
		g.DrawEllipse(Drawing.Pens.Black,x,y,w,h);
		let font = new Font("MS UI Gothic",18.f) in
		let size = g.MeasureString(label,font,768,new StringFormat()) in
		g.DrawString(label,font,Brushes.Black,x+w/2.f-size.Width/2.f,y+h/2.f-size.Height/2.f);

    //線を指定座標から指定座標へ描き、間にコストを描く
    member this.line (sx:float32) (sy:float32) (ex:float32) (ey:float32) c=
        use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in
        let (dx,dy) = (this.circle_width/2.f,this.circle_height/2.f) in
		let font = new Font("MS UI Gothic",12.f) in
		let (nsx,nsy,nex,ney) = (sx+dx,sy+dy,ex+dx,ey+dy) in
        g.DrawLine(Pens.Black,nsx,nsy,nex,ney);
        //線を1:2に内分する点にコストを描く
		g.DrawString(c.ToString(),font,Brushes.Black,(nsx+2.f*nex)/3.f,(nsy+2.f*ney)/3.f);
end;;


[<STAThread>]
do System.Windows.Forms.Application.Run(new Graph(6,edges));;