第5回グラフ理論Ust宿題2
@see http://www.ustream.tv/recorded/7585209
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/fKEt
*/
// 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/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, 5], [1, 6], [2, 7], [3, 8], [4, 9],
[5, 10], [6, 11], [7, 12], [8, 13], [9, 14],
[5, 14], [6, 10], [7, 11], [8, 12], [9, 13],
[10, 15], [11, 16], [12, 17], [13, 18], [14, 19],
[15, 16], [16, 17], [17, 18], [18, 19], [19, 15],
];
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) * 150, 230 - Math.cos(0) * 150],
[230 - Math.sin(Math.PI*2/5) * 150, 230 - Math.cos(Math.PI*2/5) * 150],
[230 - Math.sin(Math.PI*4/5) * 150, 230 - Math.cos(Math.PI*4/5) * 150],
[230 - Math.sin(Math.PI*6/5) * 150, 230 - Math.cos(Math.PI*6/5) * 150],
[230 - Math.sin(Math.PI*8/5) * 150, 230 - Math.cos(Math.PI*8/5) * 150],
[230 - Math.sin(Math.PI*1/5) * 100, 230 - Math.cos(Math.PI*1/5) * 100],
[230 - Math.sin(Math.PI*3/5) * 100, 230 - Math.cos(Math.PI*3/5) * 100],
[230 - Math.sin(Math.PI*5/5) * 100, 230 - Math.cos(Math.PI*5/5) * 100],
[230 - Math.sin(Math.PI*7/5) * 100, 230 - Math.cos(Math.PI*7/5) * 100],
[230 - Math.sin(Math.PI*9/5) * 100, 230 - Math.cos(Math.PI*9/5) * 100],
[230 - Math.sin(Math.PI*1/5) * 50, 230 - Math.cos(Math.PI*1/5) * 50],
[230 - Math.sin(Math.PI*3/5) * 50, 230 - Math.cos(Math.PI*3/5) * 50],
[230 - Math.sin(Math.PI*5/5) * 50, 230 - Math.cos(Math.PI*5/5) * 50],
[230 - Math.sin(Math.PI*7/5) * 50, 230 - Math.cos(Math.PI*7/5) * 50],
[230 - Math.sin(Math.PI*9/5) * 50, 230 - Math.cos(Math.PI*9/5) * 50],
];
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, 3, 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");
}
}
}