辺彩色
返彩色
簡単に書くと、
各○に同じ色の辺は高々1本しか入ってこない条件下で、
すべての辺を最小色数で色付けしたときの状態
@see http://www.prefield.com/algorithm/graph/bipartite_coloring.html
/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/bj26
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
import flash.events.*;
import frocessing.color.*;
// 返彩色
// 簡単に書くと、
// 各○に同じ色の辺は高々1本しか入ってこない条件下で、
// すべての辺を最小色数で色付けしたときの状態
// @see http://www.prefield.com/algorithm/graph/bipartite_coloring.html
public class Test extends Sprite {
private var _tf : TextField;
public function Test() {
/*
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
*/
stage.addEventListener(MouseEvent.CLICK, onClick);
_mode = 0;
onClick(null);
}
private var _mode : uint = 0;
private var _xys : Vector.<Number>;
private var M : uint = 6;
private var N : uint = 6;
private var P : Number = 0.5;
private function onClick(e : MouseEvent) : void
{
var i : uint, j : uint;
_mode = (_mode + 1) % 2;
if(_mode == 1){
// 問題の描画
_xys = new Vector.<Number>(2 * (M + N));
for(i = 0;i < M;i++){
_xys[2*i] = Math.random() * 150 + 50;
_xys[2*i+1] = Math.random() * 400 + 30;
}
for(i = M;i < M+N;i++){
_xys[2*i] = 465 - 50 - Math.random() * 150;
_xys[2*i+1] = Math.random() * 400 + 30;
}
graphics.clear();
graphics.lineStyle(2, 0xcfcfcf);
_r = createRelation(M, N, P);
for(i = 0;i < M;i++){
for(j = 0;j < N;j++){
if(_r[i][j] == 1){
graphics.moveTo(_xys[2*i], _xys[2*i+1]);
graphics.lineTo(_xys[2*(M+j)], _xys[2*(M+j)+1]);
}
}
}
// 頂点の上塗り
graphics.lineStyle(0, 0x7f7f7f);
for(i = 0;i < M;i++){
graphics.beginFill(0x7f7fff);
graphics.drawCircle(_xys[2*i], _xys[2*i+1], 10);
graphics.endFill();
}
for(i = M;i < M+N;i++){
graphics.beginFill(0xff7f7f);
graphics.drawCircle(_xys[2*i], _xys[2*i+1], 10);
graphics.endFill();
}
}else if(_mode == 0){
// 解答の描画
var ec : Vector.<Vector.<uint>> = edgeColoring(_r);
var hsv : ColorHSV = new ColorHSV();
var base : Number = Math.random();
for each(var v : Vector.<uint> in ec){
hsv.hsv(base, 1, 1);
graphics.lineStyle(2, hsv.value);
for(i = 0;i < v.length;i+=2){
graphics.moveTo(_xys[2*v[i]], _xys[2*v[i]+1]);
graphics.lineTo(_xys[2*(M+v[i+1])], _xys[2*(M+v[i+1])+1]);
}
base += 360 / ec.length;
}
// 頂点の上塗り
graphics.lineStyle(0, 0x7f7f7f);
for(i = 0;i < M;i++){
graphics.beginFill(0x7f7fff);
graphics.drawCircle(_xys[2*i], _xys[2*i+1], 10);
graphics.endFill();
}
for(i = M;i < M+N;i++){
graphics.beginFill(0xff7f7f);
graphics.drawCircle(_xys[2*i], _xys[2*i+1], 10);
graphics.endFill();
}
}
}
private var _r : Vector.<Vector.<uint>>;
private function createRelation(M : uint, N: uint, p : Number) : Vector.<Vector.<uint>>
{
var r : Vector.<Vector.<uint>> = new Vector.<Vector.<uint>>(M);
for(var i : uint = 0;i < M;i++){
var row : Vector.<uint> = new Vector.<uint>(j);
for(var j : uint = 0;j < N;j++){
row[j] = Math.random() < p ? 1 : 0;
}
r[i] = row;
}
return r;
}
// rについて破壊的
private function edgeColoring(r : Vector.<Vector.<uint>>) : Vector.<Vector.<uint>>
{
var m : uint = r.length;
var n : uint = r[0].length;
var ret : Vector.<Vector.<uint>> = new Vector.<Vector.<uint>>();
while(true){
var partner : Vector.<int> = bipartiteMatching(r, m, n);
var mat : Vector.<uint> = new Vector.<uint>();
for(var i : uint = 0;i < partner.length;i++){
if(partner[i] != -1){
mat.push(partner[i], i);
r[partner[i]][i] = 0;
}
}
if(mat.length == 0)break;
ret.push(mat);
}
return ret;
}
// m個とn個をマッチングする。
private function bipartiteMatching(r : Vector.<Vector.<uint>>, m : uint, n : uint) : Vector.<int>
{
// sink側から見たsource側の相手。いなければ-1
var partner : Vector.<int> = new Vector.<int>(n);
var i : uint;
for(i = 0;i < n;i++)partner[i] = -1;
for(i = 0;i < m;i++){
// source側のすでに探索したかどうかの配列
var visited : Vector.<Boolean> = new Vector.<Boolean>(m);
augment(r, i, partner, visited, n);
}
return partner;
}
private function augment(r : Vector.<Vector.<uint>>, s : uint, partner : Vector.<int>, visited : Vector.<Boolean>, n : uint) : Boolean
{
if(visited[s])return false;
visited[s] = true;
for(var i : uint = 0;i < n;i++){
if(
r[s][i] == 1 &&
(
partner[i] == -1 ||
(
partner[i] != s &&
augment(r, partner[i], partner, visited, n)
))){
// パートナーがいない場合はつないで終わり
partner[i] = s;
return true;
}
}
return false;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
}
}