スケールフリーグラフ

グラフ生成はBarabasi-Albertモデル
グラフ描画は完全にランダムレイアウト
左上は次数分布

by naraba 14 Nov 2009

Tags

graph scale-free グラフ
Embed

/**
 * Copyright naraba ( http://wonderfl.net/user/naraba )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/gUje
 */

// グラフ生成はBarabasi-Albertモデル
// グラフ描画は完全にランダムレイアウト
// 左上は次数分布
package
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.TimerEvent;
	import flash.utils.Timer;
	
	[SWF(width="465", height="465", frameRate="30")]
	public class BAModel extends Sprite
	{
		private const INIT_NODES:Number = 2;
		private const NUM_NODES:Number = 500;
		private const NUM_EDGES:Number = 4;
		private const WIDTH:Number = 465;
		private const HEIGHT:Number = 465;
		private const STAT_SCALE:Number = .25;
		private var maxfreq:Number;
		private var nodes:Array = [];
		private var edges:Array = [];
		private var degdist:Array = [];
		private var evolveTimer:Timer = new Timer(100);
		
		public function BAModel()
		{
			Wonderfl.capture_delay(30);
			
			for (var i:Number = 0; i < INIT_NODES; i++) {
				nodes.push(new Node(WIDTH/2+Math.random()*100-50,
									HEIGHT/2+Math.random()*100-50,
									INIT_NODES-1));
				degdist.push(0);
				for (var j:Number = i+1; j < INIT_NODES; j++) {
					edges.push(new Edge(i, j));
				}
			}
			degdist[INIT_NODES-1] = INIT_NODES;
			maxfreq = INIT_NODES;
			stage.addEventListener(Event.ENTER_FRAME, function(e:Event):void {
				draw();
			});
			evolveTimer.addEventListener(TimerEvent.TIMER, evolve);
			evolveTimer.start();
		}

		private function evolve(e:TimerEvent):void
		{
			var adds:Array = [];
			var n:Number = nodes.length;
			var ends:Number = 2*edges.length;
			nodes.push(new Node(Math.random()*WIDTH, Math.random()*HEIGHT, NUM_EDGES));
			for (var i:Number = 0; i < NUM_EDGES; i++) {
				degdist.push(0);
				var addend:Number = int(Math.random()*ends)+1;
				for (var j:Number = 0; j < n; j++) {
					addend -= nodes[j].deg;
					if (addend <= 0) {
						adds.push(j);
						break;
					}
				}
			}
			for each (var addn:Number in adds) {
				var d:Number = nodes[addn].deg;
				nodes[addn].deg += 1;
				edges.push(new Edge(n, addn));
				degdist[d] -= 1;
				degdist[d+1] += 1;
				maxfreq = Math.max(maxfreq, degdist[d+1]);
			}
			degdist[NUM_EDGES] += 1;
			maxfreq = Math.max(maxfreq, degdist[NUM_EDGES]);
			if (nodes.length >= NUM_NODES) { evolveTimer.stop(); }
		}
		
		private function draw():void
		{
			graphics.clear();
			drawGraph();
			drawDegdist();
		}

		private function drawGraph():void
		{
			graphics.lineStyle(1, 0x999999, .1);
			for each (var edge:Edge in edges) {
				graphics.moveTo(nodes[edge.u].x, nodes[edge.u].y);
				graphics.lineTo(nodes[edge.v].x, nodes[edge.v].y);
			}	
			graphics.beginFill(0x000000);
			for each (var node:Node in nodes) {
				graphics.drawCircle(node.x, node.y, node.deg/5+.1);
			}
			graphics.endFill();
		}
		
		private function drawDegdist():void
		{
			graphics.lineStyle(1, 0xFFFF00, 1);
			var areaW:Number = WIDTH*STAT_SCALE;
			var areaH:Number = HEIGHT*STAT_SCALE;
			graphics.beginFill(0x333333, .8);
			graphics.drawRect(0, 0, areaW+10, areaH+10);
			graphics.endFill();
			graphics.beginFill(0xFFFF00, .8);
			var maxdeg:Number = -1;
			for (var i:Number = degdist.length-1; i >= 0; i--) {
				if (degdist[i] != 0) { 
					if (maxdeg == -1) { maxdeg = i; }
					graphics.drawCircle(5+i/maxdeg*areaW,
										5+(1.-degdist[i]/maxfreq)*areaH,
										1);
				}
			}
			graphics.endFill();
		}
	}
}

class Edge
{
	public var u:Number;
	public var v:Number;
	
	public function Edge(u:Number, v:Number)
	{
		this.u = u;
		this.v = v;
	}
}

class Node
{
	public var x:Number;
	public var y:Number;
	public var deg:Number;
    
    public function Node(x:Number, y:Number, deg:Number)
    {
        this.x = x;
        this.y = y;
		this.deg = deg;
    }
}