第6回グラフ理論Ust [Tutte Graph]

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

by uwi 23 Jun 2010

• Forked from uwi's 第5回グラフ理論Ust宿題2
• Diff: 70
• 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/ljb2
 */

// forked from uwi's 第5回グラフ理論Ust宿題2
// forked from uwi's 第5回グラフ理論Ust宿題1
package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import frocessing.color.*;

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

		private var _edges : Array = [
			[1, 2], [3, 4], [5, 0],
			[0, 6], [1, 6], [2, 7], [3, 7], [4, 8], [5, 8],
			[0, 9], [1, 10], [2, 11], [3, 12], [4, 13], [5, 14],
			[6, 15], [7, 16], [8, 17],
			[9, 18], [15, 18], [11, 19], [16, 19], [13, 20], [17, 20],
			[15, 21], [10, 21], [16, 22], [12, 22], [17, 23], [14, 23],
			[9, 24], [10, 25], [11, 26], [12, 27], [13, 28], [14, 29],
			[18, 30], [24, 30], [19, 31], [26, 31], [20, 32], [28, 32],
			[30, 33], [21, 33], [31, 34], [22, 34], [32, 35], [23, 35],
			[33, 36], [25, 36], [34, 37], [27, 37], [35, 38], [29, 38],
			[24, 39], [36, 39], [26, 40], [37, 40], [28, 41], [38, 41],
			[39, 42], [25, 42], [40, 43], [27, 43], [41, 44], [29, 44],
			[42, 45], [43, 45], [44, 45]
		];
		
		private var _coords : Array = [];
		
		private var N : uint;
		
		public function Test() {
			_tf = new TextField();
			_tf.width = 465;
			_tf.height = 465;
//			addChild(_tf);

			pushCoords(200, 6, 30);
			pushCoords(200 / 2 * Math.sqrt(3), 3, 0);
			pushCoords(160, 6, 30);
			pushCoords(160, 3, 0);
			pushCoords(145, 3, 15);
			pushCoords(145, 3, -15);
			pushCoords(120, 6, 30);
			pushCoords(120, 3, 15);
			pushCoords(120, 3, 0);
			pushCoords(120 / 2 * Math.sqrt(3), 3, 0);
			pushCoords(80, 3, 30);
			pushCoords(40, 3, 0);
			pushCoords(0, 1, 0);
			N = _coords.length;
			
			solve(); 
		}
		
		private function pushCoords(r : Number, n : uint, o : Number) : void
		{
			for(var i : uint = 0;i < n;i++){
				_coords.push([
					230 - r * Math.sin((-i / n + o / 360) * 2 * Math.PI),
					230 - r * Math.cos((-i / n + o / 360) * 2 * Math.PI)
				]);
			}
		}
		
		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, 3, 0);
			
			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");
		}
	}
}