class CGraph extends MovieClip {
var urlToGraph;
private var data;
function CGraph() {
if (urlToGraph != undefined && this['area'] == undefined) loadGraph(urlToGraph);
}
var onGraphLoad:Function;
function loadGraph(wGraph) {
urlToGraph = wGraph;
if (urlToGraph instanceof XML) {
data = urlToGraph;
data.ignoreWhite = true;
onDataReady();
} else {
data = new XML('');
data.ignoreWhite = true;
data._parent = this;
data.onLoad = function (success) {
this._parent.onDataReady();
delete this._parent;
}
if (urlToGraph != undefined) data.load(urlToGraph);
}
}
private function onDataReady() {
data.ready = true;
trigger('onDataChange');
onGraphLoad();
}
var eventList;
private function trigger(wEvent) {
if (eventList == undefined) eventList = [ ];
for (var prop in eventList) if (eventList[prop] == wEvent) return;
eventList.push(wEvent);
onEnterFrame = function () {
delete onEnterFrame;
while (eventList.length) this[eventList.pop()]();
}
}
/*- generate */
function generate(wMinNodes, wMaxNodes, wXOffset, wYOffset, wXMLString) {
if (wMinNodes == undefined) wMinNodes = 3;
if (wMaxNodes == undefined) wMaxNodes = 5;
if (wXOffset == undefined) wXOffset = 0;
if (wYOffset == undefined) wYOffset = 0;
if (wXMLString == undefined) wXMLString = '';
//
var gphXML = new XML(wXMLString);
var nodes = gphXML.firstChild.firstChild.nextSibling, nNodes, iNode;
var links = nodes.nextSibling, nLinks, iLink, usedLink = [ ];
var i;
//
nNodes = wMinNodes + Math.floor(Math.random()*(wMaxNodes-wMinNodes+1));
for (i = 1; i <= nNodes; i++) {
var iNode = gphXML.createElement('node');
iNode.attributes.name = '' + i;
iNode.attributes.id = i;
iNode.attributes.x = Math.round(Math.sin(2*Math.PI*(i-1)/nNodes - 5*Math.PI/6)*35) +50 +wXOffset;
iNode.attributes.x += Math.round(Math.random()*15)-7;
iNode.attributes.y = Math.round(Math.cos(2*Math.PI*(i-1)/nNodes - 5*Math.PI/6)*35) +50 +wYOffset;
iNode.attributes.y += Math.round(Math.random()*15)-7;
nodes.appendChild(iNode);
}
//
nLinks = nNodes + 1 + Math.floor(Math.random()*(wMaxNodes-nNodes));
if (nLinks > nNodes*(nNodes-1)/2) nLinks = nNodes*(nNodes-1)/2;
var nLeft = [ ], nNodeX, nNodeY;
for (i = 1; i <= nNodes; i++) nLeft.push(i);
nNodeX = nLeft.splice(Math.floor(Math.random()*nLeft.length), 1)[0];
for (i = 1; i < nNodes; i++) {
var iLink = gphXML.createElement('link');
nNodeY = nLeft.splice(Math.floor(Math.random()*nLeft.length), 1)[0];
iLink.attributes.nodex = nNodeX;
iLink.attributes.nodey = nNodeY;
usedLink[(nNodeX-1)*nNodes+nNodeY-1] = true;
iLink.attributes.cost =
Math.round(Math.sqrt(
Math.pow(nodes.childNodes[nNodeX-1].attributes.x-nodes.childNodes[nNodeY-1].attributes.x, 2) +
Math.pow(nodes.childNodes[nNodeX-1].attributes.y-nodes.childNodes[nNodeY-1].attributes.y, 2)
));
if (iLink.attributes.cost > 99) iLink.attributes.cost = 99;
links.appendChild(iLink);
nNodeX = nNodeY;
}
for (/* */; i <= nLinks; i++) {
var iLink = gphXML.createElement('link');
do {
nNodeX = 1 + Math.floor(Math.random()*nNodes);
nNodeY = 1 + Math.floor(Math.random()*nNodes);
} while (usedLink[(nNodeX-1)*nNodes+nNodeY-1] || usedLink[(nNodeY-1)*nNodes+nNodeX-1] || nNodeX == nNodeY);
iLink.attributes.nodex = nNodeX;
iLink.attributes.nodey = nNodeY;
usedLink[(iLink.attributes.nodex-1)*nNodes+iLink.attributes.nodey-1] = true;
iLink.attributes.cost =
Math.round(Math.sqrt(
Math.pow(nodes.childNodes[nNodeX-1].attributes.x-nodes.childNodes[nNodeY-1].attributes.x, 2) +
Math.pow(nodes.childNodes[nNodeX-1].attributes.y-nodes.childNodes[nNodeY-1].attributes.y, 2)
));
if (iLink.attributes.cost > 99) iLink.attributes.cost = 99;
links.appendChild(iLink);
}
//
loadGraph(gphXML);
}
/*- verificare */
function isConnex() {
if (links.childNodes.length < nodes.childNodes.length-1) return false;
var nodes = data.nodes, links = data.links;
var i, ccon = [ ], min, max;
for (var iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
i = Number(iNode.attributes.id);
ccon[i] = i;
}
for (var iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
min = Math.min( ccon[iLink.attributes.nodex], ccon[iLink.attributes.nodey] );
max = Math.max( ccon[iLink.attributes.nodex], ccon[iLink.attributes.nodey] );
for (i = 1; i <= ccon.length; i++) if (ccon[i] == max) ccon[i] = min;
}
for (i = 1; i < ccon.length; ) {
if (ccon[i] == undefined) ccon.splice(i, 1);
else i++;
}
for (i = 1; i < ccon.length-1; i++) {
if (ccon[i] != ccon[i+1]) return false;
}
return true;
}
/*- get APM Kruskal */
function getAPM() {
return getAPMKruskal();
}
function getAPMKruskal() {
var errorMessage = '';
var aSubGraph = new CSubGraph(this);
var nNodes, iNode, nodes = data.nodes;
var nLinks, iLink, links = data.links;
var usedNode = new Array(), usedLink = new Object();
// count Nodes
nNodes = 0;
for (iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
nNodes++;
usedNode[iNode.attributes.id] = iNode.attributes.id;
}
if (nNodes == 0) {
errorMessage += 'Nu exista computere.';
return errorMessage;
} else if (nNodes == 1) {
errorMessage += 'Exista doar un computer.';
return errorMessage;
}
// count Links
nLinks = 0;
for (iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
nLinks++;
}
if (nLinks == 0) {
errorMessage += 'Nu exista legături.';
return errorMessage;
} else if (nLinks < nNodes-1) {
errorMessage += 'Nu toate computerele sunt legate între ele.';
return errorMessage;
}
//
var minLink, minNode;
var iSafetyBreak = 0;
while (true) {
if (++iSafetyBreak == 100000) break;
// stop condition 1
for (iNode = nodes.firstChild; iNode.nextSibling; iNode = iNode.nextSibling) {
if (usedNode[iNode.attributes.id] != usedNode[iNode.nextSibling.attributes.id]) break;
}
if (iNode.nextSibling == null) break;
// get minimum
minLink = null;
for (iLink = links.firstChild; iLink; iLink = iLink.nextSibling) {
//! trace(' » [' + iLink.attributes.nodex + ', ' + iLink.attributes.nodey + ']: ' + usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey]);
if (usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey] == true) continue;
if (minLink == null || Number(iLink.attributes.cost) < Number(minLink.attributes.cost)) {
minLink = iLink;
}
}
// stop condition 2
if (minLink == null) break;
iLink = minLink;
// mark as chosen
usedLink[iLink.attributes.nodex + '_' + iLink.attributes.nodey] = true;
// verify connexity
if (usedNode[iLink.attributes.nodex] == usedNode[iLink.attributes.nodey]) continue;
minNode = usedNode[iLink.attributes.nodex];
for (iNode = nodes.firstChild; iNode; iNode = iNode.nextSibling) {
if (usedNode[iNode.attributes.id] == minNode) usedNode[iNode.attributes.id] = usedNode[iLink.attributes.nodey];
}
// mark
aSubGraph.addLink(iLink);
}
// test conexity
for (iNode = nodes.firstChild; iNode.nextSibling; iNode = iNode.nextSibling) {
if (usedNode[iNode.attributes.id] != usedNode[iNode.nextSibling.attributes.id]) break;
}
if (iNode.nextSibling != null) {
errorMessage += 'Nu toate computerele sunt legate între ele.';
return errorMessage;
}
return aSubGraph;
}
/*- get APM Prim */
function getAPMPrim() {
var errorMessage = '';
var aSubGraph = new CSubGraph(this);
var inod, nodes = data.nodes;
var ilink, nLinks, links = data.links;
var i, n, j, ii, jj, min, ok;
var prim = new Array(), notes = new Array();
n=0;
for(inod = nodes.firstChild;inod;inod = inod.nextSibling){
prim[inod.attributes.id] = new Array();
n++;
}
if (n == 0) {
errorMessage += 'Nu exista computere.';
return errorMessage;
} else if (n == 1) {
errorMessage += 'Exista doar un computer.';
return errorMessage;
}
for (ilink = links.firstChild; ilink; ilink = ilink.nextSibling) {
nLinks++;
}
if (nLinks == 0) {
errorMessage += 'Nu exista legături.';
return errorMessage;
}
else if (nLinks < n-1) {
errorMessage += 'Nu toate computerele sunt legate între ele.';
return errorMessage;
}
for(ilink = links.firstChild;ilink;ilink = ilink.nextSibling){
prim[ilink.attributes.nodex][ilink.attributes.nodey] = Number(ilink.attributes.cost);
prim[ilink.attributes.nodey][ilink.attributes.nodex] = Number(ilink.attributes.cost);
}
notes[1] = 1;
min = 100;
ok=1;
while(ok){
ok=0;
min=100;
for(i = 1; i<=n;i++)
if(notes[i])
for(j=1; j<=n; j++)
if(!notes[j]){
if(prim[i][j] != undefined && min > prim[i][j]){
min=prim[i][j];
ii = i;
jj = j;
ok=1;
}
}
if (!ok) break;
notes[jj]=1;
for(ilink = links.firstChild;ilink;ilink = ilink.nextSibling){
if(ilink.attributes.nodex == ii && ilink.attributes.nodey == jj) aSubGraph.addLink(ilink);
else if(ilink.attributes.nodey == ii && ilink.attributes.nodex == jj) aSubGraph.addLink(ilink);
}
}
for(i=1; i<=n; i++)
if(!notes[i]){
errorMessage += 'Nu toate computerele sunt legate între ele.';
return errorMessage;
}
return aSubGraph;
}
}