グラフの可視化

グラフ理論の勉強用にグラフの元データからグラフを可視化するプログラムを作成してみた。Graphクラスのコンストラクタにノード数と(点A、点B、AB間のコスト)の配列を渡せばグラフが表示される。見栄えは、微妙。

アルゴリズムは非常に単純で、グラフのノードを円形に並べ、線でつなぐだけ。線の交わりが出来るだけ少なくなるように描くプログラムが書ければかっこいいのだが。

隣接行列にもそのうち対応してみたい

#light "off"

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

//要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス
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;
		//ノード間の接続とコストを描く
        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;;

//(始点、終点、コスト)からなる配列。
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)|];;

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