/**
* Copyright WinField95 ( http://wonderfl.net/user/WinField95 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/zzdf
*/
// forked from WinField95's A panel for exercises on graphs ver2
// forked from WinField95's A panel for exercises on graphs
// forked from WinField95's flash on 2011-8-16
package {
import adobe.utils.CustomActions;
import flash.display.Scene;
import flash.display.AVM1Movie;
import flash.display.Sprite;
import flash.text.*;
import flash.events.MouseEvent;
import flash.geom.*;
import flash.filters.GlowFilter;
//[SWF(backgroundColor = 0xED1A3D, frameRate = 40, width = 465, height = 465)]
public class Main extends Sprite {
public var textArea:Sprite;
public function Main() {
var back:Sprite = new Sprite(); // back_bround
back.graphics.beginFill(0x000000);
// var matrix:Matrix = new Matrix();
// back.graphics.beginGradientFill("linear", [0xFFFFFF, 0x0], [1.0, 1.0], [0, 127], matrix);
back.graphics.drawRect(-500,-500,2000,1000);
back.graphics.endFill();
addChild(back);
textArea=new Sprite();
textArea.y=50;
textArea.filters = [new GlowFilter(0x00ffff,.3)];
addChild(textArea);
var format:TextFormat=new TextFormat();
var guide:TextField=setTextField(format,150,0,0,0);
guide.text="Please input matrix";
var g_res1:TextField=setTextField(format,380,0,0,0);
g_res1.text = "Connectivity";
var g_res2:TextField=setTextField(format,470,70,0,0);
g_res2.text = "Existence of 2 or more edges for each node";
var g_res3:TextField=setTextField(format,450,120,0,0);
g_res3.text = "absence of cutting edges and nodes";
var g_res4:TextField=setTextField(format,440,175,0,0);
g_res4.text = "Calculation of all shortest paths";
var g_res5:TextField=setTextField(format,440,235,0,0);
g_res5.text = "summation of all shortest paths";
var g_res6:TextField=setTextField(format,380,290,0,0);
g_res6.text = "diameter";
var g_res7:TextField=setTextField(format,450,350,0,0);
g_res7.text = "The summation of the shortest \n paths related to each single source";
var a1:TextField=setTextField(format,20,50,300,320,300);//(format,5,30,300,300,300)
a1.visible = true;
a1.multiline = true;
a1.backgroundColor=0xFFFFFF;
a1.text="";
var bf:Boolean = true;
var bt:Button = new Button('START',130)
bt.x = 20;
bt.y = 440;
bt.addEventListener(MouseEvent.CLICK, start);
addChild(bt);
//------------------------------- main process ----------------------------------------
var n:int;
const INF:int = 1000000000;
const MAX:int = 100;
var g:Array = new Array(MAX);
for(var i:int = 0 ; i < MAX ; i++){
g[i] = new Array(MAX);
}
//------------------------------------ func1 --------------------------------------------------------------------
function func1():void{
var flag1:Array = new Array(n);
for(var i:int = 0 ; i < n ; i++){
flag1[i] = false;
}
var Q:Queue = new Queue();
for(var i:int = 0 ; i < n ;i++){
if(g[0][i] != INF){
Q.enqueue(i);
flag1[i] = true;
}
}
while(!Q.empty()){
var ind:int = Q.dequeue();
for(var i:int = 0 ; i < n ; i++){
if(g[ind][i]!= INF && !flag1[i]){
Q.enqueue(i);
flag1[i] = true;
}
}
}
var f1:Boolean = true;
for(var i:int = 0 ; i < n ; i++){
if(!flag1[i])f1 = false;
}
if(f1) r1str = "TRUE";
else r1str = "FALSE";
}
// -------------------------------------------- func2 ----------------------------------------------------
function func2():void{
var flag:Boolean = true;
for(var i:int = 0 ; i < n ; i++){
var cnt:int = 0 ;
for(var j:int = 0 ; j < n ; j++){
//if(i == j)continue;
if(g[i][j] != INF)cnt++;
}
if(cnt < 2)flag = false;
}
if(flag)r2str = "TRUE";
else r2str = "FALSE";
}
var bridge:Array = new Array(MAX);
for(var i:int = 0 ; i < MAX ; i++){
bridge[i] = new Array(MAX);
}
var low:Array = new Array(MAX);
var d:Array = new Array(MAX);
var color:Array = new Array(MAX);
var bcnt:int = 0 ;
// -------------------------------------------- func3 -----------------------------------------------------
// -------------------------------------------- dfs -------------------------------------------------------
function dfs(u:int,parent:int,deep:int):void{
color[u] = 1;
d[u] = low[u] = deep;
for(var i:int = 0 ; i < n ; i++){
if(g[u][i] == INF)continue;
var v:int = i;
if(color[v] == 1 && v != parent) low[u] = low[u] < d[v] ? low[u] : d[v];
if(color[v] == 0){
dfs(v,u,deep + 1);
low[u] = low[u] < low[v] ? low[u] : low[v];
if(low[v] > d[u]){
bcnt++;
bridge[u][v] = bridge[v][u] = 1;
}
}
}
color[u] = 2;
}
//--------------------------------------------- dfs end ------------------------------------------------------
function func3():void{
bcnt = 0;
for(var i:int = 0 ; i < n ; i++)d[i] = 0 ;
for(var i:int = 0 ; i < n ; i++)color[i] = 0 ;
for(var i:int = 0 ; i < n ; i++)low[i] = 0;
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
bridge[i][j] = 0;
}
}
for(var i:int = 0 ; i < n ; i++){
if(!color[i])dfs(i,0,0);
}
r3str = "bridge \n";
for(var i:int = 0 ; i < n ; i++){
for(var j:int = i+1 ; j < n ; j++){
if(bridge[i][j])r3str += i + " - " + j + "\n";
}
}
var degree:Array = new Array(n);
for(var i:int = 0 ; i < n ; i++)degree[i] = 0 ;
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(i == j)continue;
if(g[i][j] != INF)degree[i]++;
}
}
r3str += "articulation points \n";
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(bridge[i][j]){
if(degree[i] > 1)r3str += i + "\n";
if(degree[j] > 1)r3str += j + "\n";
degree[i] = 0;
degree[j] = 0;
}
}
}
}
// ----------------------------------------------- func4 ---------------------------------------------------
var d_sum:Array = new Array(n);
function func4():void{
for(var k:int = 0 ; k < n ; k++){
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j];
}
}
}
for(var i:int = 0 ; i < n ; i++) d_sum[i] = 0;
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(g[i][j] != INF)d_sum[i] += g[i][j];
}
}
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(g[i][j] == INF) r4str += 'x';
else{
r4str += g[i][j];
}
r4str += ' ';
}
r4str += '\n';
}
}
// ---------------------------------------------------- func5 --------------------------------------------------
function func5():void{
var sum:int = 0;
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(g[i][j] != INF)sum += g[i][j];
}
}
sum /= 2;
r5str = sum.toString();
}
//--------------------------------------------------- func6 ----------------------------------------------------
function func6():void{
var maxi:int = 0;
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(g[i][j] != INF){
// maxi = max(maxi,g[i][j]);
if(maxi <= g[i][j])maxi = g[i][j];
}
}
}
r6str = maxi.toString();
}
// ------------------------------------------------dijkstra ---------------------------------------------------
function dijkstra(s:int, g:int, n:int, G:Array):Array {
//r8str += " n = ";
//r8str += n;
//r8str += '\n';
var path:Array = new Array();
for (var i:int = 0 ; i < n ; i++) path[i] = new Array();
var q:Array = new Array(); // priority_queue
q.push(new P(0, s));
var d:Array = new Array(); // distance;
for (var i:int = 0 ; i < n ; i++) d[i] = INF-1;
d[s] = 0;
while (true) {
q.sortOn("first", Array.NUMERIC);
var p:P = q.shift();
if (p == null) break;
var v:int = p.second;
if (d[v] < p.first) continue;
for (var to:int = 0 ; to < n ; to++) {
//r8str += G[from][to];
//r8str += ' ';
var cost:int = G[v][to];
/*
r8str += 'from = ';//
r8str += v;//
r8str += ' to = ' ;//
r8str += to;//
r8str += ' cost = ';
r8str += cost;
r8str += '\n';//
*/
if (cost == INF) continue;
if (d[to] >= d[v] + cost) {
if (d[to] > d[v] + cost) {
d[to] = d[v] + cost;
q.push(new P(d[to], to));
path[to] = new Array();
}
/*
r8str += 'from = ';//
r8str += v;//
r8str += ' to = ' ;//
r8str += to;//
r8str += ' cost = ';
r8str += cost;
r8str += '\n';//
*/
path[to].push(v);
}
}
//r8str += '\n';
}
return path;
}
//----------------------------------------- count_edge ----------------------------------------------------------
var edge_count = new Array();
for (var i:int = 0 ; i < MAX ; i++) {
for (var j:int = 0 ; j < MAX ; j++) {
edge_count[i] = new Array();
}
}
function count_e (now:int,path:Array):void { // ダイクストラで最短距離を求めるときに使用したエッジの使用された回数を求める。
//r8str += now;//
//r8str += '\n';
for (var i:int = 0 ; i < path[now].length ; i++) {
var next:int = path[now][i];
/*
r8str += "now = ";
r8str += now;
r8str += " next = ";
r8str += next;
r8str += '\n';
*/
edge_count[now][next]++;
edge_count[next][now]++;
count_e(next,path); // edgeのコストに０を使うとここでバグが発生する。
}
}
//----------------------------------------- func8 -----------------------------------------------------------------
function func8(n:int,G:Array):void {
for (var i = 0 ; i < n ; i++) {
for (var j = 0 ; j < n ; j++) {
edge_count[i][j] = 0;
}
}
for (var i:int = 0 ; i < n ; i++) {
for (var j:int = 0 ; j < n ; j++) {
if (i == j) continue;
var path:Array = dijkstra(i, j, n, G); // スタート地点、ゴール地点、ノードの数,隣接行列
count_e(j,path);
}
}
/*
for (var i:int = 0 ; i < n ; i++) {
for (var j:int = 0 ; j < n ; j++) {
r8str += G[i][j];
r8str += ' ';
}
r8str += '\n';
}
var path:Array = dijkstra(0, n-1,n,G);
for (var i:int = 0 ; i < n ; i++) {
for (var j:int = 0 ; j < path[i].length ; j++) {
r8str += path[i][j];
r8str += ' ';
}
r8str += '\n';
}
*/
for (var i:int = 0 ; i < n ; i++) {
for (var j:int = i + 1; j < n ; j++) {
if (G[i][j] == INF) continue;
if (i == j) continue;
r8str += "from = ";
r8str += i;
r8str += " to = ";
r8str += j;
r8str += " count = ";
r8str += edge_count[i][j];
r8str += "\n";
}
}
}
//-------------------------------------------------------------------------------------------------------------------------
var testStr:String = new String();// test
var r1str:String = new String();
var r2str:String = new String();
var r3str:String = new String();
var r4str:String = new String();
var r5str:String = new String();
var r6str:String = new String();
var r7str:String = new String();
var r8str:String = new String();
//------------------------------------------------- perse ---------------------------------------------------------------
// String型の入力データをint型の適切な配列に変換させる
function parsing(str:String): Array{
var res:Array = new Array();
var tmp:int = 0;
a1.text = "";
//var c:String = str.charAt(0);
// a1.text += c;
var blank:Boolean = false;
for(var i:int = 0 ; i < str.length; i++){
// cout << str[i];//
//var c:char = str.charAt(i);
var c:String = str.charAt(i);
if('0' <= c.charAt(0) && c.charAt(0) <= '9'){
tmp *= 10;
tmp += parseInt(c.charAt(0));
blank = true;
}
else if(c == "x"){
tmp = INF;
blank = true;
}
else if(blank){
blank = false;
res.push(tmp);
tmp = 0;
}
if(i == str.length -1)res.push(tmp);
}
// cout << endl;//
//a1.text = "fhfh";
return res;
}
//------------------------------------------------ check --------------------------------------------------------------
/*
function check(str:String):Boolean{
for(var i:int = 0 ; i < str.length ; i++){
var c:String = str.charAt(i);
if(!( ('0' <= c.charAt(0) && c.charAt(0) <= '9') || c == "x"|| c == ",")){
guide.text = c;
return true;
}
}
return false;
}
*/
//---------------------------------------------- new_input ----------------------------------------------------
function new_input(input:Array ):Array{
//var cnt:int = 0;
var n_input:Array = new Array();
// a1.text = "Q";
for(var i:int = 0 ; i < input.length ; i++){
for(var j:int = 0 ; j < input[i].length ; j++){
if(( '0' <= input[i].charAt(j) && input[i].charAt(j) <= '9' ) || input[i].charAt(j) == 'x' ){
n_input.push(input[i]);
// a1.text += input[i];
break;
}
}
// a1.text += '\n';
}
return n_input;
}
// ------------------------------------------ start ------------------------------------------------------
function start():void{
// a1.text = "!!!!!!!!!"; // test
var btr:Button = new Button('RESET',130)
btr.x = 190;
btr.y = 440;
btr.addEventListener(MouseEvent.CLICK, reset);
addChild(btr);
var dt:Dummy = new Dummy('START',130)
dt.x = 20;
dt.y = 440;
addChild(dt);
if(a1.text == ""){
guide.text = " is not correct data! Please input the data !"
return;
}
r7str = a1.text;
//ActionScript入門Wiki http://www40.atwiki.jp/spellbound/pages/390.html
//RegExpは正規表現を利用する際に用いるクラス http://livedocs.adobe.com/flash/9.0_jp/ActionScriptLangRefV3/RegExp.html
//sgmは正規表現に対して設定できるプロパティのs(dotall)とg(global)とm(multiline)のこと。 http://help.adobe.com/ja_JP/ActionScript/3.0_ProgrammingAS3/WS5b3ccc516d4fbf351e63e3d118a9b90204-7ea7.html
//s dotall このフラグを設定した場合、.（ドット）は改行文字（¥n）にも一致します。
//g global 複数箇所に一致します。
//m multiline このフラグを設定した場合、$ および ^ はそれぞれ行末と行頭にも一致します。
// /と/の中に書かれているのが正規表現 $(ドル記号)は行の末尾を表し、.は任意の一文字を指している。
// 以上より/$./sgm は各行の改行文字を表すことになる。
var myPattern:RegExp = /$./sgm;
var input:Array = a1.text.split(myPattern); //正規表現にマッチする部分で分割を行う。
//n = input[0].length/2 + 1; // change from input[0].length/2 + 1;
input = new_input(input);
n = input.length;
// a1.text = "!!!!!!!"
var temp:Array = new Array(n);
for(var i:int = 0 ; i < n ; i++){
temp[i] = parsing(input[i]);
}
/*
for(var i:int = 0 ; i < n ; i++){
if(check(temp[i])){
guide.text = "Please input the correct format data!"
return ;
}
}
*/
a1.text = "";
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
if(temp[i][j] == INF) a1.text += "x";
else a1.text += temp[i][j];
a1.text += " ";
}
a1.text += '\n';
}
var input:Array = new Array();
var point:Array
input.push(n);
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
g[i][j] = temp[i][j];
input.push(temp[i][j]);
}
}
// var r:ReadPoint = new ReadPoint(input);
/*
// debug
var r:ReadPoint = new ReadPoint(input);
a1.text = "";
for (var i:int = 0 ; i < r.arr.length ; i++) {
a1.text += r.arr[i].toString();
a1.text += '\n';
}
// debug_end
*/
var arr1:Array = new Array();
var mat:Array = new Array();
/*
arr1.push(0);
arr1.push(0);
arr1.push(0);
arr1.push(200);
arr1.push(300);
arr1.push(50);
arr1.push(100);
arr1.push(0);
*/
for (var i:int = 0 ; i < n ; i++) {
for (var j:int = 0 ; j < n ; j++) {
mat.push(temp[i][j]);
}
}
/*
myPattern = / /;
var temp:Array = new Array(n);
for(var i:int = 0 ; i < n ; i++){
temp[i] = new Array(n);
}
for(var i:int = 0 ; i < n ; i++){
var sp:Array = input[i].split(myPattern);
for(var j:int = 0 ; j < n ; j++){
temp[i][j] = sp[j];
}
}
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ;j++){
if(temp[i][j] == 'x' || temp[i][j] == 'X')g[i][j] = INF;
else if('0' <= temp[i][j] && temp[i][j] <= '9')g[i][j] = parseInt(temp[i][j]);
else {
guide.text = "Please input the correct format data!"
return ;
}
}
}
*/
bf = false;
func8(n,temp);
func1();
func2();
func3();
func4();
func5();
func6();
var bt3:Button = new Button('button1',50)
bt3.x = 350;
bt3.y = 80;
bt3.addEventListener(MouseEvent.CLICK, b_func1);
addChild(bt3);
var bt4:Button = new Button('button2',50)
bt4.x = 350;
bt4.y = 140;
bt4.addEventListener(MouseEvent.CLICK, b_func2);
addChild(bt4);
var bt5:Button = new Button('button3',50)
bt5.x = 350;
bt5.y = 190;
bt5.addEventListener(MouseEvent.CLICK, b_func3);
addChild(bt5);
var bt6:Button = new Button('button4',50)
bt6.x = 350;
bt6.y = 250;
bt6.addEventListener(MouseEvent.CLICK, b_func4);
addChild(bt6);
var bt7:Button = new Button('button5',50)
bt7.x = 350;
bt7.y = 310;
bt7.addEventListener(MouseEvent.CLICK, b_func5);
addChild(bt7);
var bt8:Button = new Button('button6',50)
bt8.x = 350;
bt8.y = 365;
bt8.addEventListener(MouseEvent.CLICK, b_func6);
addChild(bt8);
var bt9:Button = new Button('button7',50)
bt9.x = 350;
bt9.y = 440;
bt9.addEventListener(MouseEvent.CLICK, b_func7);
addChild(bt9);
var bt10:Button = new Button('edge',50)
bt10.x = 450;
bt10.y = 80;
bt10.addEventListener(MouseEvent.CLICK, b_func8);
addChild(bt10);
guide.text = " Please push the button "
/*
var viewer:Viewer = new Viewer();
viewer.makeView(r.getArray(),mat,n);
arr1 = r.getArray();
for(var i:int = 0 ; i < arr1.length ; i++){
a1.text += arr1[i];
}
a1.text += "!!";
a1.text += arr1.length;
addChild(viewer);
*/
//var r:ReadPoint = new ReadPoint(input,mat,n);
//addChild(r);
//------------------ Viewer is under construction!! ------------------------------------------------
/*
var viewer:Viewer = new Viewer(); // TEST
viewer.makeView(input,mat,n); // TEST
addChild(viewer);
*/
//-------------------------------------------------------------------------------------------------
}
//---------------------------------------- reset ------------------------------------------
function reset():void{
//a1.text = "";
r1str = "";
r2str = "";
r3str = "";
r4str = "";
r5str = "";
r6str = "";
r7str = "";
r8str = "";
a1.text = "";
a1.multiline = true;
bf = true;
guide.text = "Please input matrix";
makeDummy();
var bt:Button = new Button('START',130)
bt.x = 20;
bt.y = 440;
bt.addEventListener(MouseEvent.CLICK, start);
addChild(bt);
}
//--------------------------------------- button function ----------------------------------------------------
function b_func1():void{
if(bf)return;
guide.text = " Connectivity "
a1.text = r1str;
}
function b_func2():void{
if(bf)return;
guide.text = " Existence of 2 or more edges for each node "
a1.text = r2str;
}
function b_func3():void{
if(bf)return;
guide.text = " absence of cutting edges and nodes "
a1.text = r3str;
}
function b_func4():void{
if(bf)return;
guide.text = " Calculation of all shortest paths "
a1.text = r4str;
}
function b_func5():void{
if(bf)return;
guide.text = " summation of all shortest paths "
a1.text = r5str;
}
function b_func6():void{
if(bf)return;
guide.text = " diameter "
a1.text = r6str;
}
function b_func7():void{
if(bf)return;
guide.text = " The summation of the shortest \n paths related to each single source "
a1.text = "";
for(var i:int = 0 ; i < n ; i++){
a1.text += "node " + i + " : " ;
a1.text += d_sum[i];
a1.text += "\n";
}
}
function b_func8():void {
if (bf) return;
guide.text = "How many times are edges used \n for calculating shortest pass by dijkstra"
a1.text = "";
a1.text = r8str;
}
makeDummy();
}
private function makeDummy():void{
var d3:Dummy= new Dummy('button1',50)
d3.x = 350;
d3.y = 80;
addChild(d3);
var d4:Dummy = new Dummy('button2',50)
d4.x = 350;
d4.y = 140;
addChild(d4);
var d5:Dummy= new Dummy('button3',50)
d5.x = 350;
d5.y = 190;
addChild(d5);
var d6:Dummy = new Dummy('button4',50)
d6.x = 350;
d6.y = 250;
addChild(d6);
var d7:Dummy = new Dummy('button5',50)
d7.x = 350;
d7.y = 310;
addChild(d7);
var d8:Dummy = new Dummy('button6',50)
d8.x = 350;
d8.y = 365;
addChild(d8);
var d9:Dummy = new Dummy('button7',50)
d9.x = 350;
d9.y = 440;
addChild(d9);
var bt10:Dummy = new Dummy('edge',50)
bt10.x = 450;
bt10.y = 80;
addChild(bt10);
var dtr:Dummy = new Dummy('RESET',130)
dtr.x = 190;
dtr.y = 440;
addChild(dtr);
// var dummy:Dummy= new Dummy('view',50)
// dummy.x = 350;
// dummy.y = 20;
// addChild(dummy);
}
private function setTextField(_format:TextFormat,_x:uint=0,_y:uint=0,_w:uint=100,_h:uint=40,_type:uint=0):TextField {
_format.color=0x000000
_format.size=15;
_format.leading = 1;
_format.align = "left"
var tbox:TextField=new TextField()
tbox.x=_x;
tbox.y=_y;
tbox.width=_w;
tbox.height=_h;
if (_type) {
tbox.type=TextFieldType.INPUT
tbox.background=true;
tbox.backgroundColor=0xFFFFFF
tbox.selectable=true;
tbox.mouseEnabled=true;
_format.color=0x000000
} else {
tbox.autoSize=TextFieldAutoSize.CENTER
tbox.selectable=false;
tbox.mouseEnabled=false;
_format.color=0xFFFFFF
}
tbox.defaultTextFormat=_format
textArea.addChild(tbox);
return tbox;
}
}
}
// ---------------------------------------------- dummy ---------------------------------------------------------------
class Dummy extends SimpleButton
{
public function Dummy(label:String, width:int = 0):void
{
var up:Sprite = _buildImage(label, 0xCC9999, width);
var over:Sprite = _buildImage(label, 0xCC9999, width);
var down:Sprite = _buildImage(label, 0xCC9999, width);
down.y = 1;
super(up, over, down, up);
}
public function _buildImage(label:String, color:int, width:int = 0):Sprite
{
var text:TextField = new TextField();
text.defaultTextFormat = new TextFormat('Verdana', 10, 0x000000, true, null, null, null, null, TextFormatAlign.CENTER);
text.autoSize = TextFieldAutoSize.CENTER;
text.selectable = false;
text.text = label;
text.x = (width - text.width) >> 1;
text.y = 5;
var base:Shape = new Shape();
var g:Graphics = base.graphics;
g.beginFill(color);
g.drawRect(0, 0, width, text.height + 3);
g.endFill();
var sp:Sprite = new Sprite();
sp.addChild(base);
sp.addChild(text);
return sp;
}
}
// ----------------------------------------------- queue ----------------------------------------------------------------------
class Queue
{
private var data:Array = [];
public function Queue()
{
data = new Array();
}
public function enqueue(obj:*):void
{
data[data.length] = obj;
}
public function dequeue():*
{
return data.splice(0, 1);
}
public function peek():*
{
return data[0];
}
public function empty():Boolean
{
return data.length == 0;
}
public function print():void
{
trace(data);
}
}
//--------------------------------------------------- pair<int,int> ---------------------------------------------------------------------
class P
{
public var first:int;
public var second:int;
public function P(a:int,b:int) {
first = a;
second = b;
}
}
import adobe.utils.CustomActions;
import flash.display.Sprite
import flash.text.*;
import flash.display.SimpleButton;
import flash.events.MouseEvent;
class Viewer extends Sprite // グラフ描画に関するクラス
{
var display:Display; // 描画処理をまとめて行うクラス
var button1:SimpleButton; // グラフ描画を開始するボタン
var button2:SimpleButton; // グラフ表示を終了するボタン
const INF:int = 1000000000;
var inputs:Array; // ReadPointで使う隣接行列 : n , mat[0][0], mat[0][1] … mat[n-1][n-1] という形で格納する
var mat:Array; //隣接行列の情報を１次元配列で持っている
var n:int; // ノードの数
var x0:int = 20; //(0,0)の位置をずらすために使用
var y0:int = 20; //(0,0)の位置をずらすために使用
var r:ReadPoint; // ノードの座標を生成するクラス
public function Viewer() {
}
public function makeView(iinputs:Array,mmat:Array,nn:int):void //座標データ、隣接行列、n
{
n = nn;
mat = mmat;
inputs = iinputs;
/*
var back:Sprite = new Sprite(); // background
back.graphics.beginFill(0x000000);
back.graphics.drawRect(0, 0, 800, 800);
back.graphics.endFill();
addChild(back);
*/
x0 = y0 = 232;
graphics.lineStyle(4.0);
/*
var arr:Array = new Array();
arr.push(new Cir(x0 + 0, y0 + 0, 0));
arr.push(new Cir(x0 + 0, y0 + 200, 1));
arr.push(new Cir(x0 + 200, y0 + 0 , 2));
arr.push(new Cir(x0 + 100, y0 + 200,3))
var matrix:Array = new Array();
var m0:Array = [0, 0, 1, 0];
var m1:Array = [0, 0, 2, 0];
var m2:Array = [1, 2, 0, 3];
var m3:Array = [0, 0, 3, 0];
//x x 1 x
//x x 2 x
//1 2 x 3
//x x 3 x
matrix.push(m0);
matrix.push(m1);
matrix.push(m2);
matrix.push(m3);
*/
/*
var arr:Array = new Array();
// ノードのインスタンスを作成
for (var i:int = 0 ; i < points.length ; i+=2) {
arr.push(new Cir(x0 + points[i], y0 + points[i+1], i/2));
}
//隣接行列を生成
var matrix:Array = new Array();
for (var i:int = 0 ; i < n ; i++) {
var m:Array = new Array();
for (var j:int = 0 ; j < n ; j++) {
var t:int = mat[i*n + j];
if (t == INF) t = 0;
m.push(t);
}
matrix.push(m);
}
display = new Display(matrix,arr); // 隣接行列の情報とノードに関する情報をコンストラクタの引数として持つ。
display.Draw();
*/
// ボタンの生成
button1 = new Button('View',50)
button1.x = 350;
button1.y = 20;
button1.addEventListener(MouseEvent.CLICK, button1_onMouseClick);
button2 = new Button('END',50)
button2.x = 350;
button2.y = 20;
button2.addEventListener(MouseEvent.CLICK, button2_onMouseClick);
addChild(button1);
r = new ReadPoint(inputs,mat,n);
//addChild(r);
}
public function button1_onMouseClick(event:MouseEvent):void
{
//ここでグラフを生成する
var points:Array = new Array();
points = r.getArray(); // 各ノードの座標データを取得
var arr:Array = new Array();
// ノードのインスタンスを作成
for (var i:int = 0 ; i < points.length ; i+=2) {
arr.push(new Cir(x0 + points[i], y0 + points[i+1], i/2));
}
//隣接行列を生成 mat(１次配列)のデータをmatrix(２次配列)のデータに変換
var matrix:Array = new Array();
for (var i:int = 0 ; i < n ; i++) {
var m:Array = new Array();
for (var j:int = 0 ; j < n ; j++) {
var t:int = mat[i*n + j];
if (t == INF) t = 0;
m.push(t);
}
matrix.push(m);
}
display = new Display(matrix,arr); // 隣接行列の情報とノードに関する情報をコンストラクタの引数として持つ。
display.Draw();//グラフの描画を行う。
addChild(display);
removeChild(button1);
addChild(button2);
}
public function button2_onMouseClick(event:MouseEvent):void
{
removeChild(display);
removeChild(button2);
addChild(button1);
}
}
import flash.display.*;
import flash.text.*;
class Button extends SimpleButton // ボタンのクラス
{
public function Button(label:String, width:int = 0):void
{
var up:Sprite = _buildImage(label, 0xCCCCCC, width);
var over:Sprite = _buildImage(label, 0x87CEFA, width);
var down:Sprite = _buildImage(label, 0x4682B4, width);
down.y = 1;
super(up, over, down, up);
}
public function _buildImage(label:String, color:int, width:int = 0):Sprite
{
var text:TextField = new TextField();
text.defaultTextFormat = new TextFormat('Verdana', 10, 0x000000, true, null, null, null, null, TextFormatAlign.CENTER);
text.autoSize = TextFieldAutoSize.CENTER;
text.selectable = false;
text.text = label;
text.x = (width - text.width) >> 1;
text.y = 5;
var base:Shape = new Shape();
var g:Graphics = base.graphics;
g.beginFill(color);
g.drawRect(0, 0, width, text.height + 3);
g.endFill();
var sp:Sprite = new Sprite();
sp.addChild(base);
sp.addChild(text);
return sp;
}
}
import flash.display.SpreadMethod;
import flash.text.TextField;
class Cir { // ノードの情報を管理する。
private var x:Number, y:Number, r:Number, id:Number;
private var tf:TextField;
private var min_x:int = 200; // 描画する際の最小のx
private var min_y:int = 100; // 描画する際の最小のy
private var max_x:int = 600;// 描画する際の最大のx
private var max_y:int = 600;// 描画する際の最大のy
function Cir(xx:Number, yy:Number, idd:Number){ //コンストラクタ
r = 20;
xx = Math.min(xx, max_x);
xx = Math.max(xx, min_x);
x = xx;
yy = Math.min(yy, max_y);
yy = Math.max(yy, min_y);
y = yy;
id = idd;
tf = new TextField();
tf.x = x - 6;
tf.y = y - 8;
tf.selectable = false;
//tf.textColor = 0xAAAAAA;
tf.text += id;
}
public function getX():Number{
return x;
}
public function getY():Number{
return y;
}
public function setX(xx:Number):void {
xx = Math.min(xx, max_x);
xx = Math.max(xx, min_x);
x = xx;
tf.x = xx -6;
}
public function setY(yy:Number):void {
yy = Math.min(yy, max_y);
yy = Math.max(yy, min_y);
y = yy;
tf.y = y - 8;
}
public function getR():Number{
return r;
}
public function getT():TextField {
return tf;
}
}
import flash.display.Sprite
import flash.events.MouseEvent;
class Edge extends Sprite{ // エッジの情報を管理するクラス
private var line:Sprite; // ラインを描画するスプライト
private var tmp:Sprite; // lineのtemp
private var sx:Number, sy:Number, gx:Number, gy:Number,cost:Number; // 描画を始めるポイントと終えるポイント
private var tf:TextField; // コストを表示するテキストフィールド
function Edge(sxx:Number, syy:Number, gxx:Number, gyy:Number,ccost:Number) { //コンストラクタ
sx = sxx;
sy = syy;
gx = gxx;
gy = gyy;
cost = ccost;
tf = new TextField();
tf.x = 20;
tf.y = 100;
tf.text = "cost = ";
tf.text += cost;
tf.textColor = 0x000000;
}
public function drawLine():void { // エッジを描く
line = new Sprite();
line.graphics.lineStyle(6.0, 0xFFFFFF);
//line.filters = [new GlowFilter(0xFFFFFF)];
line.graphics.moveTo(sx,sy);
line.graphics.lineTo(gx,gy);
line.addEventListener(MouseEvent.MOUSE_OVER, onMouseOver);
addChild(line);
tmp = line;
}
public function onMouseOver(event:MouseEvent):void // マウスを乗せたとき色を変える
{
line = new Sprite();
line.graphics.lineStyle(6.0, 0x00FFFF);
line.graphics.moveTo(sx,sy);
line.graphics.lineTo(gx,gy);
addChild(line)
addChild(tf);
line.addEventListener(MouseEvent.MOUSE_OUT , outMouseOut);
}
public function outMouseOut(event:MouseEvent):void //マウスが離れたとき色を戻す
{
line = tmp;
addChild(line);
removeChild(tf);
}
}
import flash.display.Sprite
import flash.filters.GlowFilter;
class Display extends Sprite{ // 描画処理をまとめて行うクラス
private var matrix:Array;
private var arr:Array;
function Display(m:Array,a:Array) { //コンストラクタ
matrix = m;
arr = a;
}
function Dis(x0:int , y0:int , x1:int , y1:int) : Number{
var x2:Number, y2:Number;
x2 = x0 - x1;
y2 = y0 - y1;
return Math.sqrt(x2 * x2 + y2 * y2);
}
public function Draw():void // コレが呼び出されると描画を行う
{
var back:Sprite = new Sprite();
back.graphics.beginFill(0x000000);
back.graphics.drawRect(-500, -500, 2000, 2000);
back.graphics.endFill();
addChild(back);
var status:Sprite = new Sprite();
status.graphics.beginFill(0xFFFFFF);
status.graphics.drawRect(20,20,100,150);
status.graphics.endFill();
addChild(status);
// ノードを適当にばらつかせる処理 ///////////////////////////////////////////////////////////////////////////////////
var diff:Number = 100/arr.length;
for (var i:int = 0 ; i < arr.length ; i++) {
arr[i].setX(arr[i].getX() + diff*i);
arr[i].setY(arr[i].getY() - diff*i - 100);
diff *= -1;
}
diff = 150;
for (var ii:int = 0 ; ii < 30 ; ii++){
for (var i:int = 0 ; i < arr.length ; i++) {
for (var j:int = i+1 ; j < arr.length ; j++) {
var ang:Number = Math.atan2(arr[i].getY() - arr[j].getY() , arr[i].getX() - arr[j].getX());
ang += 0.8;
for (var k:int = 0 ; k < 30 ; k++){
if (Dis(arr[i].getX(),arr[i].getY(),arr[j].getX(),arr[j].getY()) < diff) {
arr[i].setX(arr[i].getX() + Math.cos(ang) * 8);
arr[i].setY(arr[i].getY() + Math.sin(ang) * 8);
arr[j].setX(arr[j].getX() - Math.cos(ang) * 8);
arr[j].setY(arr[j].getY() - Math.sin(ang) * 8);
}
}
}
}
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
for (var i:int = 0 ; i < arr.length ; i++) { // ノードを配置
var circle:Sprite = new Sprite();
circle.filters = [new GlowFilter(0xFFFFFF)];
circle.graphics.lineStyle(4.0, 0x000000);
circle.graphics.beginFill(0xFFFFFF);
circle.graphics.drawCircle(arr[i].getX(), arr[i].getY(), arr[i].getR());
circle.graphics.endFill();
addChild(circle);
addChild(arr[i].getT());
}
for (var i:int = 0 ; i < arr.length ; i++) { // エッジを配置
for (var j:int = i+1 ; j < arr.length ; j++) {
if (matrix[i][j] != 0) {
var line:Sprite = new Sprite();
var ang:Number = Math.atan2(arr[i].getY() - arr[j].getY() , arr[i].getX() - arr[j].getX());
var sx:Number, sy:Number, gx:Number, gy:Number;
sx = arr[i].getX() - Math.cos(ang) * arr[i].getR();
sy = arr[i].getY() - Math.sin(ang) * arr[i].getR();
gx = arr[j].getX() + Math.cos(ang) * arr[j].getR();
gy = arr[j].getY() + Math.sin(ang) * arr[j].getR();
var edge:Edge = new Edge(sx, sy, gx, gy, matrix[i][j]);
edge.drawLine();
addChild(edge);
}
}
}
}
}
import flash.display.Sprite;
import flash.events.Event;
import flash.net.URLLoader;
import flash.net.URLRequest;
import flash.text.*;
class ReadPoint extends Sprite //サーバー側のプログラムを使って座標を計算する
{
private var arr:Array = new Array();
private var mat:Array;
private var n:int;
public function ReadPoint(input:Array,matrix:Array,nn:int)
{
/* debug
var test:Sprite = new Sprite();
test.graphics.beginFill(0x0);
test.graphics.drawRect(0,0,100,100);
test.graphics.endFill();
addChild(test);
*/
mat = matrix;
n = nn;
var urlLoader:URLLoader = new URLLoader();
urlLoader.addEventListener(Event.COMPLETE, onComplete);
var message:String = new String("http://163.143.87.196:8080/entry/GraphServlet?message=");
message += makeMessage(input);
// urlLoader.load(new URLRequest("3s0.0s1.0s4.0s1.0s0.0s0.0s4.0s0.0s0.0s"));
//message += "2s1.0s1.0s1.0s1.0s"
urlLoader.load(new URLRequest(message));
var test:Sprite = new Sprite();
test.graphics.beginFill(0x0);
test.graphics.drawRect(0,0,100,100);
test.graphics.endFill();
addChild(test);
}
private function makeMessage(input:Array):String{ // サーバー側のプログラムに対応した形式に入力を加工してやる
var res:String = new String();
for (var i:int = 0 ; i < input.length ; i++) {
res += input[i].toString();
res += 's';
}
return res;
}
private function onComplete(event:Event):void // XMLの読み込みが終了したらこの関数が呼ばれる
{
var urlLoader:URLLoader = event.currentTarget as URLLoader;
var xml:XML = new XML(urlLoader.data);
var str:String = urlLoader.data as String;
var tf:TextField = new TextField();
//tf.defaultTextFormat = new TextFormat("", 12, 0x0, true);
//tf.text = "!!!!";
//addChild(tf);
var tmp:int = 0;
tf.text = str;
var i:int;
// XMLのデータを解析して配列に座標データを格納していく。
for( i = 0 ; i < str.length ; i++){
if('0' <= str.charAt(i) && str.charAt(i) <= '9'){
tmp*=10;
tmp += parseInt(str.charAt(i));
}
else {
if(tmp != 0){
arr.push(tmp);
}
tmp = 0;
}
}
/*
var viewer:Viewer = new Viewer(); // TEST
viewer.makeView(arr,mat,n); // TEST
addChild(viewer);
//tf.text = arr[5];
arr.push("!!!!!");
*/
//tf.text = "!!!!";
//addChild(tf);
}
public function getArray():Array{
return arr;
}
}
