第5回グラフ理論Ust宿題1

@see http://www.ustream.tv/recorded/7585209

by uwi 23 Jun 2010

• Related works: 2
Embed

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

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import frocessing.color.*;

	// @see http://www.ustream.tv/recorded/7585209
	public class Test extends Sprite {
		private var _tf : TextField;

		private var _edges : Array = [
			[0, 1], [1, 2], [2, 3], [3, 4], [4, 0],
			[0, 6], [1, 7], [2, 8], [3, 9], [4, 5],
			[0, 9], [1, 5], [2, 6], [3, 7], [4, 8],
			[5, 10], [6, 10], [7, 10], [8, 10], [9, 10]
		];
		
		private var _coords : Array = [
			[230 - Math.sin(0) * 200, 230 - Math.cos(0) * 200],
			[230 - Math.sin(Math.PI*2/5) * 200, 230 - Math.cos(Math.PI*2/5) * 200],
			[230 - Math.sin(Math.PI*4/5) * 200, 230 - Math.cos(Math.PI*4/5) * 200],
			[230 - Math.sin(Math.PI*6/5) * 200, 230 - Math.cos(Math.PI*6/5) * 200],
			[230 - Math.sin(Math.PI*8/5) * 200, 230 - Math.cos(Math.PI*8/5) * 200],
			[230 - Math.sin(0) * 100, 230 - Math.cos(0) * 100],
			[230 - Math.sin(Math.PI*2/5) * 100, 230 - Math.cos(Math.PI*2/5) * 100],
			[230 - Math.sin(Math.PI*4/5) * 100, 230 - Math.cos(Math.PI*4/5) * 100],
			[230 - Math.sin(Math.PI*6/5) * 100, 230 - Math.cos(Math.PI*6/5) * 100],
			[230 - Math.sin(Math.PI*8/5) * 100, 230 - Math.cos(Math.PI*8/5) * 100],
			[230, 230]
		];
		
		private var N : uint = _coords.length;
		
		public function Test() {
			_tf = new TextField();
			_tf.width = 465;
			_tf.height = 465;
//			addChild(_tf);

			solve();
		}
		
		private function solve() : void
		{
			var g : Array = new Array(N);
			var i : uint, j : uint;
			for(i = 0;i < N;i++){
				g[i] = new Array(N);
				for(j = 0;j < N;j++){
					g[i][j] = -1;
				}
			}
			
			for each(var e : Array in _edges){
				g[e[0]][e[1]] = 0;
				g[e[1]][e[0]] = 0;
			}
			
			rec(g, 5, 0);
			
			/*
			for(i = 0;i < 11;i++){
				tr(g[i]);
			}
			*/
			paint(g, _coords);
		}
		
		private function paint(g : Array, coords : Array) : void
		{
			var i : uint, j : uint;
			var max : int = 0;
			for(i = 0;i < N;i++){
				for(j = i + 1;j < N;j++){
					if(g[i][j] > max)max = g[i][j];
				}
			}
			var cs : Array = [];
			for(i = 0;i < max;i++){
				cs.push(new ColorHSV(360 * i / max).value);
			}
			
			for(i = 0;i < N;i++){
				for(j = i + 1;j < N;j++){
					if(g[i][j] > 0){
						graphics.lineStyle(3, cs[g[i][j] - 1]);
						graphics.moveTo(coords[i][0], coords[i][1]);
						graphics.lineTo(coords[j][0], coords[j][1]);
					}
				}
			}
		}
		
		private function rec(g : Array, nc : uint, pos : uint) : Boolean
		{
			if(pos == _edges.length)return true;
			
			var a : uint = _edges[pos][0];
			var b : uint = _edges[pos][1];
			
			var j : uint;
			var ca : uint = 0;
			for(j = 0;j < N;j++){
				if(g[a][j] > 0)ca |= 1 << g[a][j];
			}
			
			var cb : uint = 0;
			for(j = 0;j < N;j++){
				if(g[b][j] > 0)cb |= 1 << g[b][j];
			}
			
			for(var k : uint = 1;k <= nc;k++){
				if(ca & (1 << k))continue;
				if(cb & (1 << k))continue;
				g[a][b] = k;
				g[b][a] = k;
				if(rec(g, nc, pos + 1))return true;
				g[a][b] = 0;
				g[b][a] = 0;
			}
			return false;
		}

		private function tr(...o : Array) : void
		{
			_tf.appendText(o + "\n");
		}
	}
}