A panel for exercises on graphs
グラフの隣接行列から、各項目の情報を計算する。
隣接行列をテキストエリアに入力し、STARTボタンを押してください。
その後に右のボタンを押すと計算された情報を見ることができます。
他のケースを試す場合はリロードしてください。
フルスクリーンモードで仕様すると、右の文字がしっかりと見ることができます。
test case:
つながっていない部分は x として入力
x 1 x x x x x
1 x 2 4 x x x
x 2 x 1 x x x
x 4 1 x 1 x x
x x x 1 x 2 3
x x x x 2 x 2
x x x x 3 2 x
/**
* Copyright WinField95 ( http://wonderfl.net/user/WinField95 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/1tNT
*/
// forked from WinField95's flash on 2011-8-16
package {
import flash.display.Sprite;
import flash.text.*;
import flash.events.MouseEvent;
[SWF(backgroundColor = 0x000000, frameRate = 40, width = 465, height = 465)]
public class main extends Sprite {
public var textArea:Sprite;
public function main() {
// write as3 code here..
textArea=new Sprite();
textArea.y=50;
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,60,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,180,0,0);
g_res4.text = "Calculation of all shortest paths";
var g_res5:TextField=setTextField(format,440,240,0,0);
g_res5.text = "summation of all shortest paths";
var g_res6:TextField=setTextField(format,380,300,0,0);
g_res6.text = "diameter";
var a1:TextField=setTextField(format,20,50,300,290,300);//(format,5,30,300,300,300)
//var test:TextField=setTextField(format,5,200,300,150,300);// test
a1.visible = true;
a1.multiline = true;
a1.backgroundColor=0xFFFFFF;
a1.text="";
var bf:Boolean = true;
var bt:Button = new Button('START',100)
bt.x = 30;
bt.y = 400;
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++)color[i] = 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(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 ---------------------------------------------------
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++){
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();
}
//-------------------------------------------------------------------------------------------------------------------------
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();
function start():void{
// a1.text = "!!!!!!!!!"; // test
if(!bf){
guide.text = "Please reload this page \nwhen you try other data case";
return;
}
bf = false;
var myPattern:RegExp = /$./sgm;
var input:Array = a1.text.split(myPattern);
n = input[0].length/2;
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')g[i][j] = INF;
else g[i][j] = parseInt(temp[i][j]);
}
}
func1();
func2();
func3();
func4();
func5();
func6();
guide.text = " Please push the button "
}
//----------------------------------------------------------------------------------------
function reset():void{
//a1.text = "";
r1str = "";
r2str = "";
r3str = "";
r4str = "";
r5str = "";
r6str = "";
//testStr = "";
var a1:TextField=setTextField(format,20,30,300,300,300);//(format,5,30,300,300,300)
//a1.visible = true;
a1.multiline = true;
// var bt1:Button = new Button('START',100);
// var bt2:Button = new Button('RESET',100);
guide.text = "Please input matrix";
}
//--------------------------------------- button function ----------------------------------------------------
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 = 200;
bt5.addEventListener(MouseEvent.CLICK, b_func3);
addChild(bt5);
var bt6:Button = new Button('button4',50)
bt6.x = 350;
bt6.y = 260;
bt6.addEventListener(MouseEvent.CLICK, b_func4);
addChild(bt6);
var bt7:Button = new Button('button5',50)
bt7.x = 350;
bt7.y = 320;
bt7.addEventListener(MouseEvent.CLICK, b_func5);
addChild(bt7);
var bt8:Button = new Button('button6',50)
bt8.x = 350;
bt8.y = 380;
bt8.addEventListener(MouseEvent.CLICK, b_func6);
addChild(bt8);
function b_func1():void{
if(bf)return;
guide.text = " Connectivity "
//var res1:TextField=setTextField(format,20,30,300,300,300);
//r1str = testStr;
a1.text = r1str;
//res1.text = testStr;
}
function b_func2():void{
if(bf)return;
guide.text = " Existence of 2 or more edges for each node "
//var res2:TextField=setTextField(format,20,30,300,300,300);
a1.text = r2str;
}
function b_func3():void{
if(bf)return;
guide.text = " absence of cutting edges and nodes "
//var res3:TextField=setTextField(format,20,30,300,300,300);
a1.text = r3str;
}
function b_func4():void{
if(bf)return;
guide.text = " Calculation of all shortest paths "
//var res4:TextField=setTextField(format,20,30,300,300,300);
a1.text = r4str;
}
function b_func5():void{
if(bf)return;
guide.text = " summation of all shortest paths "
//var res5:TextField=setTextField(format,20,30,300,300,300);
a1.text = r5str;
}
function b_func6():void{
if(bf)return;
guide.text = " diameter "
//var res6:TextField=setTextField(format,20,30,300,300,300);
a1.text = r6str;
}
//-------------------------------------- button function end ------------------------------------------------------
}
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;
}
}
}
// ------------------------------------------------ Button Class --------------------------------------------------------------
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, 0xFFCCCC, width);
var down:Sprite = _buildImage(label, 0xCC9999, width);
down.y = 1;
super(up, over, down, up);
}
private static 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 + 10);
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);
}
}