/**
* Copyright WinField95 ( http://wonderfl.net/user/WinField95 )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/hOpy
*/
// forked from WinField95's A panel for exercises on graphs ver2
// 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 flash.display.Sprite;
import flash.text.*;
import flash.events.MouseEvent;
import flash.geom.*;
//[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);
back.graphics.drawRect(-500,-500,2000,1000);
back.graphics.endFill();
addChild(back);
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,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();
}
//-------------------------------------------------------------------------------------------------------------------------
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();
//------------------------------------------------- perse ---------------------------------------------------------------
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 = true;
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;
}
*/
// ------------------------------------------ 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;
var myPattern:RegExp = /$./sgm;
var input:Array = a1.text.split(myPattern);
//n = input[0].length/2 + 1; // change from input[0].length/2 + 1;
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';
}
for(var i:int = 0 ; i < n ; i++){
for(var j:int = 0 ; j < n ; j++){
g[i][j] = 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;
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);
guide.text = " Please push the button "
}
//---------------------------------------- reset ------------------------------------------
function reset():void{
//a1.text = "";
r1str = "";
r2str = "";
r3str = "";
r4str = "";
r5str = "";
r6str = "";
r7str = "";
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";
}
}
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 dtr:Dummy = new Dummy('RESET',130)
dtr.x = 190;
dtr.y = 440;
addChild(dtr);
}
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, 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;
}
}
// ---------------------------------------------- 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);
}
}
